-
完全圖
鎖定
在圖論的數學領域,完全圖是一個簡單的無向圖,其中每對不同的頂點之間都恰連有一條邊相連。完整的有向圖又是一個有向圖,其中每對不同的頂點通過一對唯一的邊緣(每個方向一個)連接。n個端點的完全圖有n個端點以及n(n − 1) / 2條邊,以Kn表示。它是(k − 1)-正則圖。所有完全圖都是它本身的團(clique)。
圖形理論本身以萊昂哈德歐拉於1736年在Königsberg七橋的工作開始。 然而,完全圖的繪圖,其頂點放置在正多邊形的點上,已經在13世紀中出現。這樣的繪畫有時被稱為神秘玫瑰。
- 中文名
- 完全圖
- 外文名
- complete graph
- 領 域
- 數學
- 概 念
- 每對頂點之間都恰連有一條邊的圖
- 分 類
- 有向完全圖,無向完全圖
- 相關名詞
- 無向圖
完全圖簡介
在圖論的數學領域,完全圖是一個簡單的無向圖,其中每對不同的頂點之間都恰連有一條邊相連。完整的有向圖又是一個有向圖,其中每對不同的頂點通過一對唯一的邊緣(每個方向一個)連接。n個端點的完全圖有n個端點以及n(n − 1) / 2條邊,以Kn表示。它是(k − 1)-正則圖。所有完全圖都是它本身的團(clique)。
完全圖屬性
n個頂點的完全圖表示為
。 一些消息來源稱,這個符號中的字母K代表德語單詞komplett,但完全圖的德文名稱vollständigerGraph不包含字母K,其他來源則表示符號表示 Kazimierz Kuratowski圖論。
如果一個完全圖的邊緣都被賦予一個方向,那麼所得的有向圖就被稱為比賽。
完全圖的匹配數由電話號碼給出:
1,1,2,4,10,26,76,232,764,2620,9496,35696,140152,568504,2390480,10349536,46206736,...(OEIS中的序列A000085)。
這些數字給出了n頂點圖的Hosoya索引的最大可能值。完全圖
(n均勻)完美匹配的數量由雙因子
給出。
0,0,0,0,1,3,9,29,36,62,102,153,229,324,447,603,798,1029,1318,1657,2055,2528,3077,3699,4430,5250,6180,...(OEIS中的序列A014540)。
完全圖幾何和拓撲
具有n個節點的完全圖表示(n-1) - 複雜的邊緣。 幾何
形成三角形的邊緣集合,
是四面體等。具有圓環拓撲的非凸多面體Császár多面體具有完整的圖形
作為其骨架。 四個或更多維度的每個多面體也具有完整的框架。
完全圖舉例
n頂點的完全圖,在n從1到12之間,與邊緣數量一起顯示如下:
完全圖無向完全圖
無向完全圖是用n表示圖中頂點數目的一種圖,一張圖中每條邊都是無方向的。
完全圖定義
完全圖解釋
直觀來説,若一個圖中每條邊都是無方向的,則稱為無向圖。
(1)無向邊的表示
無向圖中的邊均是頂點的無序對,無序對通常用圓括號表示。
【例】無序對(vi,vj)和(vj,vi)表示同一條邊。
(2)無向圖的表示
【例】下面(b)圖中的G2和(c)圖中的G3均是無向圖,它們的頂點集和邊集分別為:
V(G2)={v1,v2,v3,v4}
E(G2)={(vl,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4),(v3,v4)}
V(G3)={v1,v2,v3,v4,v5,v6,v7}
E(G3)={(v1,v2),(vl,v3),(v2,v4),(v2,v5),(v3,v6),(v3,v7)}
完全圖注意
在以下討論中,不考慮頂點到其自身的邊。即若(v1,v2)或是E(G)中的一條邊,則要求v1≠v2。此外,不允許一條邊在圖中重複出現,即只討論簡單的圖。
3.圖G的頂點數n和邊數e的關係
(1)若G是無向圖,則0≤e≤n(n-1)/2
恰有n(n-1)/2條邊的無向圖稱無向完全圖(Undirected Complete Graph)
(2)若G是有向圖,則0≤e≤n(n-1)。
恰有n(n-1)條邊的有向圖稱為有向完全圖(Directed Complete Graph)。
注意:
完全圖具有最多的邊數。任意一對頂點間均有邊相連。
【例】上面(b)圖的G2就是具有4個頂點的無向完全圖。