完整的雙分圖
| 完整的雙分圖 | |
|---|---|
 完整的二分圖，具有m = 5和n = 3
| |
| 頂點 | n + m |
| 邊緣 | Mn |
| 半徑 |  |
| 直徑 |  |
| 周長 |  |
| 自動形態 |  |
| 色數 | 2 |
| 色度指數 | max { m ， n } |
| 光譜 |  |
| 符號 | k { m ， n } |
| 圖和參數表 | |
在圖理論的數學字段中，完整的兩部分圖或雙質圖是一種特殊的二分圖，其中第一組的每個頂點都連接到第二組的每個頂點。
圖理論本身通常是從萊昂哈德·歐拉（Leonhard Euler）的1736年在科尼格斯伯格（Königsberg）的七個橋樑上的工作開始的。但是，與Athanasius Kircher編輯的Ramon Llull的作品有關，早在1669年就已經印刷了完整的兩分圖的圖紙。勞爾本人在三個世紀之前就製作了類似的圖紙。
定義
完整的雙分圖是一個圖形，其頂點可以分配到兩個子集V 1和V 2中，以使得沒有邊緣在同一子集中都具有兩個端點，並且在不同子集中可以連接頂點的每個可能的邊緣都是圖形的一部分。也就是說，它是一個兩分的圖（ v 1 ， v 2 ， e ） ，因此，對於每兩個頂點v1∈V1和v2∈V2 ， v 1 v 2是e中的邊緣。完整的兩分圖，帶有大小的分區| V 1 | = M和| V 2 | = n ，表示為k m ， n ;相同符號的每兩個圖是同構。
例子
- 對於任何k ， k 1， k都稱為恆星。樹木的所有完整二分圖都是星星。
- 圖k 3,3稱為實用程序圖。這種用法來自一個標準的數學難題，其中必須將三個公用事業與三個建築物連接。由於k 3,3的非平面度，如果沒有穿越，就無法解決。
- 作為關係挖掘的子圖被發現的最大比例稱為概念。當通過遇見和加入這些子圖的相遇形成晶格時，該關係具有誘導的概念晶格。這種關係分析稱為形式概念分析。
特性
| K 3,3 | K 4,4 | K 5,5 |
|---|---|---|
|
|
|
 3個邊緣 |
 4個邊緣色 |
 5個邊緣 |
| 形式2 {4} p的常規複雜多邊形具有完整的兩部分圖，帶有2個P頂點（紅色和藍色）和P 2 2-邊緣。它們也可以作為P邊色繪製。 | ||
- 給定雙分圖，測試它是否包含一個完整的兩部分子圖K I ， i對於參數i是NP完整問題。
- 平面圖不能包含K 3,3作為未成年人；外平面圖不能包含k 3,2作為小輔助（這些不是足夠的平面和外平麵條件，但必要的）。相反，每個非平面圖都包含k 3,3或完整的圖k 5作為輔助；這是瓦格納的定理。
- 每個完整的兩分圖。 k n ， n是摩爾圖和a （ n ，4） -籠子。
- 完整的兩分圖K N ， N和K N ， N +1具有所有無三角形圖的最大邊數，具有相同數量的頂點。這是Mantel的定理。壁架的結果被概括為k派標的圖和圖形，這些圖形避免了較大的集團作為Turán定理中的子圖形，而這兩個完整的兩部分圖是Turán圖的示例，這是此更一般問題的極端圖。
- 完整的雙分圖K M ， N具有一個頂點覆蓋最小{ M ， N }的頂點，並且一個覆蓋最大{ M ， N }的邊緣覆蓋數。
- 完整的兩分圖K M ， N具有最大尺寸的最大獨立集最大{ m ， n }。
- 完整的兩分圖K M ， N的鄰接矩陣具有特徵值為 √nm ， -√nm和0;分別具有多重性1、1和N + m -2 。
- 完整的兩分圖K m ， n的拉普拉斯矩陣具有eigenvalues n + m ， n ， m和0;分別具有多重性1， m -1 ， n -1和1。
- 完整的兩分圖K M ， N具有m n -1 n m -1跨越樹。
- 完整的雙分圖K M ， N具有最大匹配尺寸min { m ， n }。
- 完整的兩分圖K n ， N具有與拉丁正方形相對應的適當的N-邊緣色。
- 每個完整的兩分圖都是一個模塊化圖：每個三重頂點都有一個屬於每對頂點之間最短路徑的中值。