概述
参考书目：《图论与网络理论》和ppt
要求：复习的时候都会证明
第一章 图的基本概念
定理1.1.1 对任何图 $ G $ ，各顶点度数之和等于边数的2倍.即 $ \sum\limits_{\nu\in V(G)}d(\nu) = 2\varepsilon. $
推论1.1.1 任何图中，奇度顶点个数为偶数.
例1.1.2 设 $ G $ 是一个简单图，若最小度 $ \delta(G) \geq 2 $，则 $ G $ 中必含有圈.
例1.1.3 设 $ G $ 是一个简单图，若最小度 $ \delta(G) \geq 3 $，则 $ G $ 中必含有偶圈.
例1.1.4 设 $ G $ 是简单图，若最小度 $ \delta(G) \geq 3 $，则 $ G $ 中各个圈长的最大公因数是1或2.
定理1.1.2 一个图是二部图当且仅当它不含有奇圈.
定理1.1.3 如果图 $ G $ 连通，$ \varepsilon(G) \geq \nu(G)-1 $.
例1.1.6 设图 $ G $ 有 $ 2n $个顶点，$ \delta(G) \geq n $，求证 $ G $ 连通.
例1.1.7 求证：若图中有且仅有2个奇度顶点，则它们必然连通.
定理1.3.1
下列命题等价
- $ G $ 是树（无圈的连通图）.
- $ G $ 无环边且 $ G $ 中任意两个顶点间有唯一的路.
- $ G $ 无圈且 $ \varepsilon = v-1 $.
- $ G $ 连通且 $ \varepsilon = v-1 $.
- $ G $ 连通且对于任意 $ e \in E(G)$，$ G-e $ 不连通.
- $ G $ 无圈且对于任意 $ e \in E(\overline{G}) $，$ G+e $ 恰有一个圈.
定理2.1.3 设 $ v $ 是树的顶点，则 $ v $ 是 $ T $ 的割点当且仅当 $ d(v)>1 $.
推论2.1.1 每个非平凡无圈连通图至少有2个顶点不是割点.
定理2.1.5 边 $ e $ 是割边当且仅当 $ e $ 不在 $ G $ 的任何一个圈上.
定理2.2.1 $ \kappa(G) \leq \kappa’(G) \leq \delta(G) $
定理2.2.2 对具有 $ v $ 个顶点 $ \varepsilon $，有$ \kappa(G) \leq \lfloor \frac{2\varepsilon}{v} \rfloor $.
定理2.2.3 设 $ G $ 是一个简单图，$ k $ 是一个自然数，若$ \delta(G) \geq \frac{v+k+2}{2} $，则 $ G $ 是连通的.
推论2.2.1 设 $ G $ 是一个简单图，若 $ \delta(G) \geq \frac{v-1}{2} $，则 $ G $ 是连通图。
定理2.2.4 设 $ G $ 是一个直径为2的简单图，则 $ \kappa’(G)=\delta(G) $.
6.
中国邮递员问题->带权最短闭途径
Edmonds-Johnson 算法（补成欧拉图）
- 找出奇度顶点，拉出来
- 画一个完全图，需要找两两之间最短路
- 找最小权匹配
- 在原来的图中添边
Fleury 算法（找欧拉闭迹）
- 沿着图的非割边前行
7.
支配集
支配数 $ \gamma(G) $
支配周围的点
极小支配集的补集也是支配集
点独立集
点独立数 $ \alpha(G) $
任二顶点有 d(u)+d(v) >= v(G)，则 a < gamma
点覆盖集
覆盖了所有的边
边覆盖集
覆盖了所有的顶点