完全圖

出自維基百科,自由嘅百科全書
完全圖

完全圖英文complete graph)係圖論中嘅一個術語攞來表示一個簡單圖嘅,其中每粒都透過一條連接到其他每一粒綟。完整嘅綟圖係唯一確定嘅(除開同構),得由指定。

若果係隻綟集畀成幅圖,係噉隻檠集 即係隻集畀啲檠啲喺成孖嘅嘸同頂點之間嘅:

一隻完全圖同時亦都係佢嘅最大團

特徵[編輯]

完全圖平面嘅(即可以轉成檠冇交叉嘅形式)。根據 Kuratowski定理,所有其他完全圖都嘸係平面圖,因為佢哋包含有作為子圖。

完全圖裏頭嘅檠數對應三角形數

.

完全圖係一隻 正則圖:每粒綟都有鄰舍。因此,每隻上色畀啲圖都有隻色。另外,完全圖帶奇數嘅係畫得一筆畫嘅而帶偶數嘅嘸係。

完全圖帶嘅係Hamiltonian圖(睇Hamiltonian路徑問題)。完全圖包括條嘸同嘅Hamiltonian迴路。

推廣[編輯]

惗法畀完全圖可以推廣到-分圖上。如果一柵分柵嘅每粒綟都連接到所有其他分柵嘅所有綟,係噉啲圖就係完全嘅。完全嘅多分圖帶柵集、啲集裏頭包含有 粒綟嘅,着表示為

有方向嘅完全圖,就變成競賽圖

軟件[編輯]

可以創建完全圖喺免費嘅PythonNetworkX嘅幫助下。例子:

import networkx as nx
import matplotlib.pyplot as plt

G = nx.complete_graph(15)

nx.draw_circular(G, with_labels=True, font_weight='bold')
plt.show()

文獻[編輯]

連出去[編輯]