什么是弦图?

下面的图我们看到后,第一感觉应该虽然看着很酷炫,但是会感觉很复杂,感觉无所适从,不知怎么来看这个图表。今天我们就来介绍下这个图表是怎么用的?

弦图

这个图表叫做弦图,弦图主要用于展示多个对象之间的关系,连接圆上任意两点的线段叫做弦,弦(两点之间的连线)就代表着两者之间的关联关系。弦图虽然看起来有点眼花缭乱,但是它却非常适合用户分析复杂数据的关联关系。弦图主要有以下特点:

(1)用圆上的两点的连线来表示两者的关系。

(2)连接线的宽度可以表示两个数据之间的关系程度或者比例关系。

(3)弧线与圆的接触面积上的宽度也可以用来表示关系程度和比例关系。

(4)可以使用不同的颜色来区分不同的关系。

弦图是一种特殊的图,很多在一般图上的 NP-Hard 问题在弦图上都有优秀的线性时间复杂度算法。


定义

子图:点集和边集均为原图点集和边集子集的图。

导出子图(诱导子图):点集为原图点集子集,边集为所有满足两个端点均在选定点集中的图。

团:完全子图。

极大团:不是其他团子图的图。

最大团:点数最大的团。

团数:最大团的点数,记为团数

最小染色:用最少的颜色给点染色使得所有边连接的两点颜色不同。

色数:最小染色的颜色数,记为色数

最大独立集:最大的点集使得点集中任意两点都没有边直接相连。该集合的大小记为最大独立集

最小团覆盖:用最少的团覆盖所有的点。使用团的数量记为最小团覆盖

弦:连接环中不相邻两点的边。

弦图:任意长度大于3的环都有一个弦的图称为弦图。


点赞(0)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

Dotcpp在线编译      (登录可减少运行等待时间)