反饋

補圖

圖G的補圖，通俗的來講就是完全圖K_n去除G的邊集後得到的圖K_n-G。在圖論裏面，一個圖G的補圖（complement）或者反面（inverse）是一個圖有着跟G相同的點，而且這些點之間有邊相連當且僅當在G裏面他們沒有邊相連。

補圖定義

設H是G的子圖，從G中去掉所有H的邊所得的圖稱為H關於G的相對補圖。

一個圖G的補圖是指這樣的一個圖：節點集為G的節點集，兩個節點有一條邊相連，當且僅當這兩個節點在G上不相鄰，換句話説，它是G關於K_n的相對補圖。G的補圖常記為G或

，若它的補圖與它自身同構，則稱為自補圖。^[1]

廣義意義下，補圖可以泛指operation：由已知圖產生出其他圖的方法。如此一來，就有很多例子了：

設V和E分別為圖G的節點集和邊集，V‘和E’分別為圖G‘的節點集和邊集。
圖G與G‘的並（用G∪G' 表示）是指節點集為V∪V' ，邊集為E∪E‘的圖。
圖G與G’的交（用G∩G' 表示）是指節點集為V∩V'，邊集為E∩E‘的圖。
圖G與圖G‘的聯是指節點集為V∪V'，邊集為E∪E'∪J(V, V')的圖，這裏J(V, V')表示由所有一端在V，中另一端在V'中的節點對作為邊組成的集合。
圖G與G‘的積，也稱笛卡兒積，用GX G’表示，是指這樣的圖：它的節點集為{(x, y) | x∈V, y∈V‘}，(x₁, y₁)與(x₂, y₂)有一條邊相連，當且僅當x₁=x₂且y₁與y₂在G'上相鄰，或y₁=y₂且x₁與x₂在G上相鄰。
圖G與G'的合成，或字典式積，是指這樣的圖：節點集為{(x, y) | x∈V, y∈V‘}，兩節點(x₁, y₁)與(x₂, y₂)有一條邊相連，當且僅當x₁與x₂在G上相鄰，或x₁=x₂且y₁與y₂在G'上相鄰，這個合成圖常記為G⊙G'。
圖G與G'的結合，記為G◎G'，是指這樣的圖：節點集為{(x, y) | x∈V, y∈V‘}，兩節點(x₁, y₁)與(x₂, y₂)有一條邊相連，當且僅當x₁與x₂在G上相鄰且y₁與y₂在G'上相鄰。
設圖G₁的階為k，G_2,1,… , G_2,k是k個與G₂同構的圖，把圖G₁的第i(1≤i≤k)個節點與圖G_2,_i上每一個節點相連，這樣所得的圖稱為G₁對於G₂的冠，常記為G₁○G₂。^[2]

補圖可以有很多性質，最典型的有：

（1）圖G不連通，則它的補圖必連通。

證明：如果圖G(V,E)不連通，它的頂點可以分為兩個非空集合A,B，其中對於任意在A中的點P和任意在B中的點Q都沒有PQ這條邊。

這樣的話,取其補圖G'，則對於任意在A中的點P和任意在B中的點Q都有PQ這條邊。這樣的話對於任意兩點P,Q，如果它們分別處於A,B的話，它們之間就有邊相連；否則，不失一般性設它們都在A中，由於B非空，我們可以在B中任取一點R，我們知道PR和QR這兩條邊都是存在的，所以P,Q是連在一起的。

綜上，知G'連通。

（2）無邊圖的補圖是完全圖，反之亦然。

（3）獨立集的補圖是套團，反之亦然。

參考資料

詞條統計