基本介紹
- 中文名：補圖
- 外文名：Complementary Graph
- 套用學科：離散數學
- 相關術語：完全圖
- 所屬領域：數學
- 性質：圖G不連通，則它的補圖必連通。
- 類型：數學術語
定義,廣義補圖,性質,
定義
設H是G的子圖，從G中去掉所有H的邊所得的圖稱為H關於G的相對補圖。
一個圖G的補圖是指這樣的一個圖：節點集為G的節點集，兩個節點有一條邊相連，若且唯若這兩個節點在G上不相鄰，換句話說，它是G關於Kn的相對補圖。G的補圖常記為G或
，若它的補圖與它自身同構，則稱為自補圖。
廣義補圖
廣義意義下，補圖可以泛指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‘}，(x1, y1)與(x2, y2)有一條邊相連，若且唯若x1=x2且y1與y2在G'上相鄰，或y1=y2且x1與x2在G上相鄰。
- 圖G與G'的合成，或字典式積，是指這樣的圖：節點集為{(x, y) | x∈V , y∈V‘}，兩節點(x1, y1)與(x2, y2)有一條邊相連，若且唯若x1與x2在G上相鄰，或x1=x2且y1與y2在G'上相鄰，這個合成圖常記為G⊙G'。
- 圖G與G'的結合，記為G◎G'，是指這樣的圖：節點集為{(x, y) | x∈V , y∈V‘}，兩節點(x1, y1)與(x2, y2)有一條邊相連，若且唯若x1與x2在G上相鄰且y1與y2在G'上相鄰。
- 設圖G1的階為k，G2,1,… , G2,k是k個與G2同構的圖，把圖G1的第i(1≤i≤k)個節點與圖G2,i上每一個節點相連，這樣所得的圖稱為G1對於G2的冠，常記為G1○G2。
性質
補圖可以有很多性質，最典型的有：
（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'連通。
