視頻來源：2.7.1 補圖_嗶哩嗶哩_bilibili

目錄

1. 補圖

1.1. 補圖

2. 雙圖

2.1. 雙圖定理

3. 圖蘭定理/托蘭定理

4. 極圖理論

5. 歐拉圖

5.1. 歐拉跡

5.2. 歐拉閉跡

5.3. 歐拉圖

5.4. 歐拉定理

5.5. 偽圖

---

1. 補圖

1.1. 補圖

（1）補圖示例：其中G為母圖，G'為其補圖

（2）定義：設(shè)??, 則??的補圖??, 其中??（所有頂點關(guān)聯(lián)邊二元集不包含的子集）

（3）推論：和它的補圖有可能同構(gòu)，即

（4）例題：六個人的團體中，或有三個人互相認識，或有三個人互相不認識?？捎脠D和補圖來做。

（5）拉姆齊定理：要找這樣一個最小的數(shù)n，使得n個人中必定有k個人相識或l個人互不相識

2. 雙圖

2.1. 雙圖定理

（1）只用一刀切開所有邊就好了，看邊的兩邊是否在不同子圖中。

（2）定理1：雙圖也稱2部圖，其中圈的度數(shù)一定為偶數(shù)（充分必要條件）。

證明：圈可以表示成??，若??，則?。因此單數(shù)頂點都屬于?， 偶數(shù)頂點都屬于?

（2）定理2：有??，，，，為偶數(shù)，則圖中一定有圈

3. 圖蘭定理/托蘭定理

（1）定理：設(shè)??是一個?圖，如其中沒有三角形，則??。其中中括號為求整符號

（2）證明：顯然，對于p=1,2,3時結(jié)論都成立。則分別證明p為奇數(shù)（p=2n-1）和偶數(shù)（p=2n）的情況；

假設(shè)p=2n-1時成立，則需證p=2n+1時成立

設(shè)p=2n-1的圖G’，p=2n+1的圖為G，有G-u-v=G';（u和v為兩個頂點，若u,v連接，則它們一定沒有公共鄰接點，否則構(gòu)成三角形；若它們不鄰接，則可能存在公共鄰接點。視頻中老師應(yīng)該是使他們鄰接的，這樣可以使第一個頂點u的鄰接邊假設(shè)到最大）

知G'是一個(2n-1,q')圖，知?;

?（u和v鄰接，且無公共鄰接點的情況）

4. 極圖理論

（1）找到邊最多的圖，但不含

5. 歐拉圖

5.1. 歐拉跡

（1）定義：包含圖的每一條邊的跡

5.2. 歐拉閉跡

（1）定義：包含圖的所有頂點的閉跡

5.3. 歐拉圖

（1）定義：包含歐拉閉跡的圖稱為歐拉圖

5.4. 歐拉定理

（1）定理1：G是歐拉圖?G連通且每個頂點度為偶數(shù)

（2）定理2：圖中有一條歐拉開跡?G中恰有2個奇度頂點

（3）定理3：設(shè)G有2n個奇度頂點，則G至少有n條跡

5.5. 偽圖

（1）多重圖定義：兩個頂點可以之間有多條邊

（2）帶環(huán)圖定義：存在頂點到自身的邊

（3）偽圖：包含多重圖和帶環(huán)圖