[图论]哈尔滨工业大学（哈工大 HIT）学习笔记16-22

视频来源：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）定义：设  , 则  的补图  , 其中  （所有顶点关联边二元集不包含的子集）

（3）推论：和它的补图有可能同构，即

（4）例题：六个人的团体中，或有三个人互相认识，或有三个人互相不认识。可用图和补图来做。

（5）拉姆齐定理：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识

2. 双图

2.1. 双图定理

（1）只用一刀切开所有边就好了，看边的两边是否在不同子图中。

（2）定理1：双图也称2部图，其中圈的度数一定为偶数（充分必要条件）。

证明：圈可以表示成  ，若  ，则 。因此单数顶点都属于 ， 偶数顶点都属于 

（2）定理2：有  ，，，，为偶数，则图中一定有圈

3. 图兰定理/托兰定理

（1）定理：设  是一个 图，如其中没有三角形，则  。其中中括号为求整符号

（2）证明：显然，对于p=1,2,3时结论都成立。则分别证明p为奇数（p=2n-1）和偶数（p=2n）的情况；

假设p=2n-1时成立，则需证p=2n+1时成立

设p=2n-1的图G’，p=2n+1的图为G，有G-u-v=G';（u和v为两个顶点，若u,v连接，则它们一定没有公共邻接点，否则构成三角形；若它们不邻接，则可能存在公共邻接点。视频中老师应该是使他们邻接的，这样可以使第一个顶点u的邻接边假设到最大）

知G'是一个(2n-1,q')图，知 ;

 （u和v邻接，且无公共邻接点的情况）

4. 极图理论

（1）找到边最多的图，但不含

5. 欧拉图

5.1. 欧拉迹

（1）定义：包含图的每一条边的迹

5.2. 欧拉闭迹

（1）定义：包含图的所有顶点的闭迹

5.3. 欧拉图

（1）定义：包含欧拉闭迹的图称为欧拉图

5.4. 欧拉定理

（1）定理1：G是欧拉图⇔G连通且每个顶点度为偶数

（2）定理2：图中有一条欧拉开迹⇔G中恰有2个奇度顶点

（3）定理3：设G有2n个奇度顶点，则G至少有n条迹

5.5. 伪图

（1）多重图定义：两个顶点可以之间有多条边

（2）带环图定义：存在顶点到自身的边

（3）伪图：包含多重图和带环图