簡介
任意兩個結點之間都有一個邊相連,也就是結點兩兩相連;連通圖是指任意兩個結點之間都有一個路徑相連。
當然不一樣了,n個頂點的完全圖有n(n-1)/2條邊;而連通圖則不一定,但至少有n-1條邊。舉個例子,四個頂點的完全圖有6條邊,也就是四條邊加上2條對角線;而連通圖可以隻包含周圍四條邊就可以了。
圖形理論本身以萊昂哈德歐拉于1736年在Königsberg七橋的工作開始。然而,完全圖的繪圖,其頂點放置在正多邊形的點上,已經在13世紀中出現。這樣的繪畫有時被稱為神秘玫瑰。
具體
具有n個節點的完全圖表示(n-1)複雜的邊緣。幾何形成三角形的邊緣集合,是四面體等。具有圓環拓撲的非凸多面體Császár多面體具有完整的圖形作為其骨架。四個或更多維度的每個多面體也具有完整的框架。
讨論了完全圖Kn分解成五個頂點的星和圈的存在性,給出完全圖Kn存在{S5,C5}-強制分解的充要條件是n≥9,以及完全圖Kn存在{S5,C5}-分解的充要條件是n≥5(n≠6,7)。
分類
無向
任意一個具有n個結點的無向簡單圖,其邊數小于等于n*(n-1)/2;我們把邊數恰好等于n*(n-1)/2的n個結點的無向圖稱為完全圖。
有向
在一個n個結點的有向圖中,最大邊數為n*(n-1)。