什么是弦圖？

下面的圖我們看到后，第一感覺應(yīng)該雖然看著很酷炫，但是會(huì)感覺很復(fù)雜，感覺無所適從，不知怎么來看這個(gè)圖表。今天我們就來介紹下這個(gè)圖表是怎么用的？

這個(gè)圖表叫做弦圖，弦圖主要用于展示多個(gè)對(duì)象之間的關(guān)系，連接圓上任意兩點(diǎn)的線段叫做弦，弦（兩點(diǎn)之間的連線）就代表著兩者之間的關(guān)聯(lián)關(guān)系。弦圖雖然看起來有點(diǎn)眼花繚亂，但是它卻非常適合用戶分析復(fù)雜數(shù)據(jù)的關(guān)聯(lián)關(guān)系。弦圖主要有以下特點(diǎn)：

（1）用圓上的兩點(diǎn)的連線來表示兩者的關(guān)系。

（2）連接線的寬度可以表示兩個(gè)數(shù)據(jù)之間的關(guān)系程度或者比例關(guān)系。

（3）弧線與圓的接觸面積上的寬度也可以用來表示關(guān)系程度和比例關(guān)系。

（4）可以使用不同的顏色來區(qū)分不同的關(guān)系。

弦圖是一種特殊的圖，很多在一般圖上的 NP-Hard 問題在弦圖上都有優(yōu)秀的線性時(shí)間復(fù)雜度算法。

定義

子圖：點(diǎn)集和邊集均為原圖點(diǎn)集和邊集子集的圖。

導(dǎo)出子圖（誘導(dǎo)子圖）：點(diǎn)集為原圖點(diǎn)集子集，邊集為所有滿足兩個(gè)端點(diǎn)均在選定點(diǎn)集中的圖。

團(tuán)：完全子圖。

極大團(tuán)：不是其他團(tuán)子圖的圖。

最大團(tuán)：點(diǎn)數(shù)最大的團(tuán)。

團(tuán)數(shù)：最大團(tuán)的點(diǎn)數(shù)，記為。

最小染色：用最少的顏色給點(diǎn)染色使得所有邊連接的兩點(diǎn)顏色不同。

色數(shù)：最小染色的顏色數(shù)，記為。

最大獨(dú)立集：最大的點(diǎn)集使得點(diǎn)集中任意兩點(diǎn)都沒有邊直接相連。該集合的大小記為。

最小團(tuán)覆蓋：用最少的團(tuán)覆蓋所有的點(diǎn)。使用團(tuán)的數(shù)量記為。

弦：連接環(huán)中不相鄰兩點(diǎn)的邊。

弦圖：任意長(zhǎng)度大于3的環(huán)都有一個(gè)弦的圖稱為弦圖。