图论定理汇总（二）

标签：图论 定义 汇总 定理 平面图 连通 着色 顶点

第六章 平面图

(一)、平面图的概念

定义1 如果能把图 G G G画在平面上，使得除顶点外，边与边之间没有交叉，称 G G G可嵌入平面，或称 G G G是可平面图。可平面图 G G G的边不交叉的一种画法，称为 G G G的一种平面嵌入， G G G的平面嵌入表示的图称为平面图。

由定义，图 G G G 的平面嵌入只是 G G G 的一种方式，它和 G G G 实际上是同一个图

(二)、平面图性质

定义2 (1) 一个平面图 G G G把平面分成若干连通片，这些连通片称为 G G G的区域，或 G G G的一个面。 G G G的面组成的集合用 ϕ \phi ϕ表示。

(2) 面积有限的区域称为平面图 G G G的内部面，否则称为 G G G的外部面或无限面。

(3) 在 G G G中，顶点和边都与某个给定区域关联的子图，称为该面的边界。某面 f f f 的边界中含有的边数(割边计算2次)称为该面 f f f 的次数, 记为 d e g ( f ) deg ( f ) deg(f)。

1、平面图的次数公式

定理1 设 G = ( n , m ) G=(n, m) G=(n,m)是平面图，则：
∑ f ∈ ϕ deg ⁡ ( f ) = 2 m \sum_{f\in\phi}\deg(f)=2m f∈ϕ∑​deg(f)=2m

实际上就是，除了割边之外的一条边会关联两个面，而割边会计算两次。所以构建 f f f 的边的总次数，为边的两倍

定理2(欧拉公式) 设 G = ( n , m ) G=(n, m) G=(n,m)是连通平面图， ϕ \phi ϕ是 G G G的面数，则：
n − m + ϕ = 2 n-m+\phi=2 n−m+ϕ=2

一个可平面图有多种平面嵌入，但无论是何种平面嵌入，由定理 2 容易知道他们的面数是相等的。

3、欧拉公式的几个有趣推论

推论1 设 G G G是具有 ϕ \phi ϕ个面 k k k个连通分支的平面图，则：
n − m + ϕ = k + 1 n-m+\phi=k+1 n−m+ϕ=k+1

推论2 设 G G G是具有 n n n个点 m m m条边 ϕ \phi ϕ个面的连通平面图，如果对 G G G的每个面 f f f ,有： d e g ( f ) ≥ l ≥ 3 deg (f) ≥ l ≥3 deg(f)≥l≥3, 则：（ l l l 可以看做是 G G G 中的一个圈的边长，即 d e g ( f ) ≥ l deg (f) ≥ l deg(f)≥l 表示 G G G 中所有圈的边长至少为 l l l）
m ≤ l l − 2 ( n − 2 ) m\leq\frac l{l-2}(n-2) m≤l−2l​(n−2)

注：

• (1)上面推论2也可以叙述为：设 G = ( n , m ) G=(n, m) G=(n,m) 是连通图，如果： m > l l − 2 ( n − 2 ) m>\frac l{l-2}(n-2) m>l−2l​(n−2) 则G是非可平面图。
• (2) 推论2的条件是 G G G是平面图的必要条件,不是充分条件。

推论3 设 G G G是具有 n n n个点 m m m条边 ϕ \phi ϕ个面的简单平面图，若 n ≥ 3 n ≥ 3 n≥3，则：（每个面的次数一定满足 ≥ 3 ≥ 3 ≥3，因为至少 3 条边才能围成一个圈）
m ≤ 3 n − 6 m\leq3n-6 m≤3n−6

K 5 K_5 K5​ 与 K 3 , 3 K_{3, 3} K3,3​ 是极小非可平面图。

推论4 设 G G G是具有 n n n个点 m m m条边的连通平面图，若 G G G的每个圈均由长度是 l l l 的圈围成，则：
m ( l − 2 ) = l ( n − 2 ) m(l-2)=l(n-2) m(l−2)=l(n−2)

推论5 设 G G G是具有 n n n个点 m m m条边的简单平面图，则： δ ≤ 5 \delta\leq5 δ≤5

定理3 一个连通平面图是 2 2 2连通的，当且仅当它的每个面的边界是圈。（了解）

推论6 若一个平面图是 2 2 2连通的，则它的每条边恰在两个面的边界上。（了解）

(一)、特殊平面图

1、极大平面图及其性质

定义1 设 G G G是简单可平面图，如果 G G G是 K i ( 1 ≦ i ≦ 4 ) K_i (1≦i≦4) Ki​(1≦i≦4), 或者在 G G G的任意非邻接顶点间添加一条边后，得到的图均是非可平面图，则称 G G G是极大可平面图。 极大可平面图的平面嵌入称为极大平面图。

注： 只有在单图前提下才能定义极大平面图。（因为如果允许存在环，则无论在每个顶点画多少个环，都不影响其平面性）

引理 设 G G G是极大平面图，则 G G G必然连通；且若 G G G的阶数大于等于 3 3 3（ n ≥ 3 n ≥ 3 n≥3），则 G G G无割边。

定理3 一个连通平面图是 2 2 2连通的，当且仅当它的每个面的边界是圈。（了解）

推论6 若一个平面图是 2 2 2连通的，则它的每条边恰在两个面的边界上。（了解）

定义1 设 G G G是简单可平面图，如果 G G G是 K i ( 1 ≦ i ≦ 4 ) K_i (1≦i≦4) Ki​(1≦i≦4), 或者在 G G G的任意非邻接顶点间添加一条边后，得到的图均是非可平面图，则称 G G G是极大可平面图。 极大可平面图的平面嵌入称为极大平面图。

注： 只有在单图前提下才能定义极大平面图。（因为如果允许存在环，则无论在每个顶点画多少个环，都不影响其平面性）

引理 设 G G G是极大平面图，则 G G G必然连通；且若 G G G的阶数大于等于 3 3 3（ n ≥ 3 n ≥ 3 n≥3），则 G G G无割边。

定理1 设 G G G是至少有 3 3 3个顶点的平面图，则 G G G是极大平面图，当且仅当 G G G的每个面的次数是 3 3 3且为单图。

推论： 设 G G G是 n n n个点， m m m条边和 ϕ \phi ϕ个面的极大平面图，且 n ≥ 3 n≥3 n≥3.则：
(1) m = 3 n − 6 m=3n-6 m=3n−6;
(2) ϕ = 2 n − 4 \phi=2n-4 ϕ=2n−4.

注： 推论表明对一个极大平面图 G，当其点数 n 给定时，G 的边数和面数也就确定了，从而 G 的结构框架也大体确定了.

定义2 如果在不可平面图 G G G中任意删去一条边所得的图为可平面图，则称 G G G为极小不可平面图。

例如 K 5 K_5 K5​ 与 K 3 , 3 K_{3,3} K3,3​ 均为极小不可平面图

2、极大外平面图及其性质

定义3 若一个可平面图 G G G存在一种平面嵌入，使得其所有顶点均在某个面的边界上，称该图为 外可平面图。外可平面图的一种外平面嵌入，称为外平面图。

定义4 设 G G G是一个简单外可平面图，若在 G G G中任意不邻接顶点间添上一条边后， G G G成为非外可平面图，则称 G G G是极大外可平面图。极大外可平面图的外平面嵌入，称为极大外平面图。（联系到极大图，一定都是简单图，不能有环，因为环可以无限加）

引理 设 G G G是一个连通简单外可平面图，则在 G G G中存在度数至多是2的顶点。(证明略)

定理2 设 G G G是一个有 n ( n ≥ 3 ) n (n≥3) n(n≥3)个点，且所有点均在外部面上的极大外平面图，则 G G G有 n − 2 n-2 n−2个内部面。（考过这道题）

定理3 设 G G G是一个有 n ( n ≥ 3 ) n (n≥3) n(n≥3) 个点，且所有点均在外部面上的外平面图，则 G G G是极大外平面图，当且仅当其外部面的边界是圈，内部面是三角形。

定理4 每个至少有7个顶点的外可平面图的补图不是外可平面图，且7是这个数目的最小者。(了解即可)

(二)、平面图的对偶图

1、对偶图的定义

定义4 给定平面图 G G G， G G G的对偶图 G ∗ G^* G∗如下构造：

(1) 在 G G G的每个面 f i f_i fi​内取一个点 v i ∗ v_i^* vi∗​作为 G ∗ G^* G∗的一个顶点；

(2) 对 G G G的一条边 e e e, 若 e e e是面 f i f_i fi​ 与 f j f_j fj​ 的公共边，则连接 v i ∗ v_i^* vi∗​与 v j ∗ v_j^* vj∗​，得 G ∗ G^* G∗ 的边 v i ∗ v j ∗ v_i^*v_j^* vi∗​vj∗​ , 且 v i ∗ v j ∗ v_i^*v_j^* vi∗​vj∗​ 与 e e e 相交；若 e e e 是面 f i f_i fi​ 中的割边（若 e e e 只在一个面 f i f_i fi​ 上时），则以 v i ∗ v_i^* vi∗​ 为顶点作环，得 G ∗ G^* G∗ 的边 v i ∗ v i ∗ v_i^*v_i^* vi∗​vi∗​，且让它与 e e e相交。（相当于考虑原图的每个边，如果这条边在两个面上，则连接这两个面，如果这个边仅在一个面上，则形成环，仅在一个面上的边通常是割边）

对偶图的性质
(1)、 G G G与 G ∗ G^* G∗的对应关系

1. G ∗ G^* G∗的顶点数等于 G G G的面数；
2. G ∗ G^* G∗的边数等于 G G G的边数；（因为每条边都考虑了在 G ∗ G^* G∗ 中与之对应的每条边）
3. G ∗ G^* G∗的面数等于 G G G的顶点数；
4. d ( v ∗ ) = d e g ( f ) d (v^*)=deg( f ) d(v∗)=deg(f)

定理5 平面图 G G G的对偶图必然连通

(2) G G G是平面图，则 ( G ∗ ) ∗ ≅ G (G^*)^*\cong G (G∗)∗≅G 当且仅当 G G G是连通的。(习题第26题)

(3) 同构的平面图可以有不同构的对偶图。

(一)、平面图的判定

平面图的判定：
(1) 观察出一个平面嵌入

(2) 设 G G G是 ( n , m ) (n,m) (n,m)简单图 ( n > 3 ) (n>3) (n>3)，若 m > 3 n − 6 m>3n-6 m>3n−6，则 G G G 是非可平面图。

(3) 设 G = ( n , m ) G=(n,m) G=(n,m)是连通图，如果： m > l l − 2 ( n − 2 ) m > \frac{l}{l-2}(n - 2) m>l−2l​(n−2) 则 G G G 是非可平面图

我们已经明确：对于 3 3 3阶以上的具有 m m m条边的单图 G G G来说，如果 G G G满足如下条件之一： (1) m > 3 n − 6 m>3n-6 m>3n−6; (2) K 5 K_5 K5​是 G G G的一个子图；(3) K 3 , 3 K_{3,3} K3,3​是 G G G的一个子图，那么， G G G是非可平面图。

但上面的条件仅为 G G G 是非可平面图的充分条件。

定义1 在图 G G G的边上插入一个新的 2 2 2 度顶点，使一条边分成两条边，称将图在 2 2 2 度顶点内扩充；去掉一个图的 2 2 2 度顶点，使关联它们的两条边合并成一条边，称将图 G G G 在 2 2 2 度顶点内收缩。

定义2 两个图 G 1 G_1 G1​与 G 2 G_2 G2​说是同胚的，如果 G 1 ≅ G 2 G_1\cong G_2 G1​≅G2​，或者通过反复在 2 2 2 度顶点内扩充和收缩后能够变成一对同构的图。（或称为 G 1 G_1 G1​与 G 2 G_2 G2​在 2 2 2 度顶点内是同构的，同胚的两个图点数和边数可能都不一样）

扩充和收缩不会改变这个图是否可平面，即一个图本身是可平面的，扩充 2 2 2 度顶点，仍然可平面，本身不是，扩充了仍然不是可平面的。收缩同理

定理1 (库拉托斯基定理) 图 G G G是可平面的，当且仅当它不含 K 5 K_5 K5​和 K 3 , 3 K_{3,3} K3,3​同胚的子图。（只介绍此定理的结论与运用，证明不要求）

定义3 给定图 G G G, 去掉 G G G中的环，用单边代替平行边（重边）而得到的图称为 G G G的基础简单图。

定理2 (1) 图 G G G是可平面的，当且仅当它的基础简单图是可平面的；（实际上就是说环和重边或叫平行边并不影响其平面性）
(2) 图 G G G是可平面图当且仅当 G G G的每个块是可平面图。（没有割点的图就是一个块）

意味着如果图 G G G 有割点，可以将图 G G G 分为多个块，分别对块进行平面性检查

定义3 设 u v uv uv 是简单图 G G G 的一条边。去掉该边，重合其端点，再删去由此产生的环和平行边（重边）。这一过程称为图 G G G的初等收缩或图的边收缩运算。并记为 G / u v G/uv G/uv

称 G G G可收缩到 H H H,是指对 G G G通过一系列边收缩后可得到图 H H H。

定理2 (瓦格纳定理)： 简单图 G G G是可平面图当且仅当它不含有可收缩到 K 5 K_5 K5​或 K 3 , 3 K_{3,3} K3,3​的子图。

定理3 至少有 9 9 9个顶点的简单可平面图的补图是不可平面的，而 9 9 9是这个数目中的最小的一个。(了解即可)

(二) 平面性算法

关于图的平面性问题，我们已经建立了一些平面性判定方法：

(1) 对于简单图 G = ( n , m ) G=(n, m) G=(n,m)，如果 m > 3 n − 6 m>3n-6 m>3n−6，则 G G G是非可平面的；

(2) 对于简单连通图 G = ( n , m ) G=(n, m) G=(n,m)，如果每个面次数至少为 l ≥ 3 l≥3 l≥3,且 m > ( n − 2 ) l ( l − 2 ) m>\frac{(n-2)l}{(l-2)} m>(l−2)(n−2)l​，则 G G G是非可平面的；

(3) 库拉托斯基定理： G G G是可平面的当且仅当 G G G不含有与 K 5 K_5 K5​和 K 3 , 3 K_{3,3} K3,3​同胚的子图；

(4) 瓦格纳定理： G G G是可平面的当且仅当 G G G不含有能够收缩成 K 5 K_5 K5​和 K 3 , 3 K_{3,3} K3,3​的子图；

上面的判定方法，局限性很大。这次课我们将给出一个算法，其作用是：如果 G G G非可平面，通过算法可以得到判定；如果 G G G是可平面图，通过算法，可以给出一种平面嵌入形式。

定义1 设 H H H是 G G G的一个子图，在 E ( G ) − E ( H ) E(G)-E(H) E(G)−E(H)中定义一个二元关系 “~”:

∀ e 1 , e 2 ∈ E ( G ) − E ( H ) , e 1 ∼ e 2 当且仅当存在一条途径 W ,  使得 : \forall e_1,e_2\in E(G)-E(H),e_1\thicksim e_2\text{当且仅当存在一条途径} W,\text{ 使得}: ∀e1​,e2​∈E(G)−E(H),e1​∼e2​当且仅当存在一条途径W, 使得:

(1) e 1 e_1 e1​与 e 2 e_2 e2​分别是 W W W的始边和终边，且

(2) W W W的内点与 H H H不能相交。（即 W W W 的内部顶点，均不是 H H H 的顶点）

定义2 设 B B B是 E ( G ) − E ( H ) E(G)-E(H) E(G)−E(H)关于二元关系“ ~” 的等价类在 G G G中的边导出子图，则称 B B B是 G G G关于子图 H H H的一座桥。桥与 H H H的公共顶点称为桥 B B B在 H H H中的附着顶点。

定义3 设 H H H是图 G G G的可平面子图， H ~ \tilde{H} H~ 是 H H H的一种平面嵌入。若 G G G也是可平面图，且存在 G G G的一个平面嵌入 G ~ \tilde{G} G~，使得： H ~ ⊆ G ~ \tilde{H}\subseteq\tilde{G} H~⊆G~ ，称 H ~ \tilde{H} H~是 G G G容许的。

定义4 设 B B B 是 G G G 中子图 H H H 的任意一座桥，若 B B B 对 H H H 的所有附着顶点都位于 H ~ \tilde{H} H~ 的某个面 f f f 的边界上，则称 B B B 在面 f f f 内可画入，否则，称 B B B在面 f f f 内不可画入。

对于 G G G的桥 B B B,令： F ( B , H ~ ) = { f ∣ f 是 H ~ 的面,且 B 在 f 内可画入 } \color{red} F(B,\tilde{H})=\left\{\left.f\right|f\text{是}\tilde{H}\text{的面,且}B\text{在}f\text{内可画入}\right\} F(B,H~)={f∣f是H~的面,且B在f内可画入}

定理1 设 H ~ \tilde{H} H~ 是 G G G 容许的，则对于 H H H 的每座桥 B B B： F ( B , H ~ ) ≠ Φ F(B,\tilde{H})\neq\Phi F(B,H~)=Φ

第七章 图的着色

(一)、相关概念

定义1 给定图 G = ( V , E ) G=(V,E) G=(V,E)，称映射 π : E → { 1 , 2 , 3 , . . . , k } \pi : E \to \{1, 2, 3, ..., k\} π:E→{1,2,3,...,k} 为 G G G 的一个 k k k 边着色，简称边着色，称 { 1 , 2 , 3 , . . . , k } \{1, 2, 3, ..., k\} {1,2,3,...,k} 为色集。若 π \pi π 为 G G G 的边着色且 ∀ e ′ , e ′ ′ ∈ E \forall e{'}, e{''} \in E ∀e′,e′′∈E，当 e ′ 与 e ′ ′ e{'} 与 e{''} e′与e′′ 相邻时， π ( e ′ ) ≠ π ( e ′ ′ ) \pi(e') ≠ \pi(e'') π(e′)=π(e′′)，则称该着色是正常的。图 G G G 的正常 k k k 边着色的最小值 k k k 称为 G G G 的边色数。（ π ( e ) \pi(e) π(e) 为图 G G G 的边着色， e e e 为 G G G 的边）

即 G G G 是图，对 G G G的边进行染色，若相邻边染不同颜色，则称对 G G G进行正常边着色；

如果能用 k k k种颜色对图 G G G进行正常边着色，称 G G G是 k k k边可着色的。

定义2 设 G G G是图，对 G G G进行正常边着色需要的最少颜色数，称为 G G G的边色数，记为： χ ′ ( G ) \chi^{\prime}(G) χ′(G) ( χ \chi χ 读为 kappa)

(二)、几类特殊图的边色数

定理 1 χ ′ ( K m , n ) = Δ \chi^{\prime}(K_{m,n})=\Delta χ′(Km,n​)=Δ （完全偶图的边色数 = 最大度）

完全偶图的最大度为，当 m > n，最大度为 m， 当 n > m，最大度为 n

且任何正常边着色中和任何一个顶点关联得各边必须着不同色，因此 χ ′ ≥ Δ \chi^{\prime} ≥ \Delta χ′≥Δ

定义3 设 π \pi π是 G G G的一种正常边着色，若点 u u u关联的边的着色没有用到色 i i i，则称点 u u u缺 i i i色。

定理2 (哥尼，1916) 若 G G G是偶图，则 χ ′ ( G ) = Δ \chi^{\prime}(G)=\Delta χ′(G)=Δ

引理： 设 G G G是简单图， x x x与 y 1 y_1 y1​是 G G G中不相邻的两个顶点， π \pi π是 G G G的一个正常 k k k边着色。若对该着色 π , x , y 1 \pi, x,y_1 π,x,y1​以及与 x x x 相邻点均至少缺少一种颜色，则 G + x y 1 G+xy_1 G+xy1​ 是 k k k边可着色的。

定理3 (维津定理，1964) 若 G G G是单图，则： χ ′ ( G ) = Δ 或  χ ′ ( G ) = Δ + 1 \chi^{\prime}(G)=\Delta\text{或 }\chi^{\prime}(G)=\Delta+1 χ′(G)=Δ或 χ′(G)=Δ+1

定理4 设 G G G是单图且 Δ ( G ) > 0 Δ(G)>0 Δ(G)>0。若 G G G中只有一个最大度点或恰有两个相邻的最大度点，则： χ ′ ( G ) = Δ ( G ) \chi^{\prime}(G)=\Delta(G) χ′(G)=Δ(G)

定理5 设 G G G是单图。若点数 n = 2 k + 1 n=2k+1 n=2k+1 且边数 m > k Δ m>kΔ m>kΔ, 则： χ ′ ( G ) = Δ ( G ) + 1 \chi^{\prime}(G)=\Delta(G)+1 χ′(G)=Δ(G)+1

定理6 设 G G G是奇数阶 Δ Δ Δ正则单图, 若 Δ > 0 Δ>0 Δ>0,则： χ ′ ( G ) = Δ ( G ) + 1 \chi^{\prime}(G)=\Delta(G)+1 χ′(G)=Δ(G)+1

定义1 设 G G G是一个图，对 G G G的每个顶点着色，使得相邻顶点着不同颜色，称为对 G G G的正常顶点着色；

超立方体 Q n Q_n Qn​ 的边色数为 n n n.

(一)、相关概念

定义1 给定图 G = ( V , E ) G=(V,E) G=(V,E)，称映射 π : V → { 1 , 2 , 3 , . . . , k } \pi : V \to \{1, 2, 3, ..., k\} π:V→{1,2,3,...,k} 为 G G G 的一个 k k k 点着色，简称着色，称 { 1 , 2 , 3 , . . . , k } \{1, 2, 3, ..., k\} {1,2,3,...,k} 为色集。若 π \pi π 为 G G G 的点着色且 ∀ u , v ∈ E \forall u, v \in E ∀u,v∈E，当
u 与 v u 与 v u与v 相邻时， π ( u ) ≠ π ( v ) \pi(u) ≠ \pi(v) π(u)=π(v)，则称该着色是正常的。图 G G G 的正常 k k k 着色的最小值 k k k 称为 G G G 的色数。（ π ( u ) \pi(u) π(u) 为图 G G G 的点着色， u u u 为 G G G 的顶点）

如果用 k k k种颜色可以对 G G G进行正常顶点着色，称 G G G可 k k k正常顶点着色；

对图 G G G正常顶点着色需要的最少颜色数，称为图 G G G的点色数。图 G G G的点色数用 χ ( G ) \chi\left(G\right) χ(G) 表示。

注： 对图的正常顶点着色，带来的是图的顶点集合的一种划分方式。所以，对应的实际问题也是分类问题。属于同一种颜色的顶点集合称为一个 色组，它们彼此不相邻接，所以又称为点独立集。用点色数种颜色对图 G G G正常着色，称为对图 G G G的最优点着色。（一个色组就是一个点独立集）

定义2 色数为 k k k的图称为 k k k色图。

(二)、图的点色数的几个结论（了解性学习）

定理1 对任意的图 G G G，有： χ ( G ) ≤ Δ ( G ) + 1 \left.\chi\left(G\right.\right)\leq\Delta\left(G\right.)+1 χ(G)≤Δ(G)+1

定理3 设 G G G是非空简单图，则： χ ( G ) ≤ Δ 2 ( G ) + 1 \chi(G)\leq\Delta_2(G)+1 χ(G)≤Δ2​(G)+1

n n n 阶完全图的点色数为 n n n

彼得森图的点色数是 3，边色数是 4

定理 31：若 G 是连通的简单图，并且它既不是奇圈又不是完全图，则 χ ( G ) ≤ ∆ ( G ) χ(G) ≤ ∆(G) χ(G)≤∆(G).

对任意的简单平面图,均有 χ ≤ 5 \chi\leq5 χ≤5.

所有 k k k 正则图是 2 可着色的

(三)、四色与五色定理

定理4 (希伍德) 每个平面图是 5 5 5可着色的。

所谓色计数，就是给定标定图 G G G和颜色数 k k k,求出正常顶点着色的方式数。方式数用 P k ( G ) P_k(G) Pk​(G)表示。

(一)、色多项式概念

可以证明： P k ( G ) P_k(G) Pk​(G)是 k k k 的多项式，称为图 G G G 的色多项式。

由点色数 χ ( G ) \chi(G) χ(G) 和色多项式 P k ( G ) P_k(G) Pk​(G) 的定义可得：

(1) 若 k < χ ( G ) k<\chi(G) k<χ(G)，则 P k ( G ) = 0 P_k(G) = 0 Pk​(G)=0; χ ( G ) = min ⁡ { k ∣ P k ( G ) ≥ 1 } \chi(G)=\min\left\{k|P_k(G)\geq1\right\} χ(G)=min{k∣Pk​(G)≥1}

(2) 若 G G G 为 n n n 阶空图，则 P k ( G ) = k n P_k(G)=k^n Pk​(G)=kn。

(3) P k ( K n ) = k ( k − 1 ) … ( k − n + 1 ) P_k(K^n)=k(k-1)…(k-n+1) Pk​(Kn)=k(k−1)…(k−n+1)。

(二)、色多项式的两种求法

1、递推计数法
定理1 设 G G G为简单图，则对任意 e ∈ E ( G ) e\in E(G) e∈E(G) 有：
P k ( G ) = P k ( G − e ) − P k ( G • e ) P_k(G)=P_k(G-e)-P_k(G•e) Pk​(G)=Pk​(G−e)−Pk​(G•e)

推论： 设 G G G是单图， e = u v e=uv e=uv 是 G G G 的一条边，且 d ( u ) = 1 d(u)=1 d(u)=1,则：
P k ( G ) = ( k − 1 ) P k ( G − u ) P_k(G)=(\text{k}-1)P_k(G-u) Pk​(G)=(k−1)Pk​(G−u)

通过加边变为完全图，加边规则为：任意连接两个顶点 + 将两个顶点收缩；通过减边变为空图，减边规则为：任意删掉某条边 - 将这条边的两点收缩

注意： 在变换的过程中，出现环则去掉，出现平行边则合并为一条边

定义1： 设 H H H是图 G G G的生成子图（包含所有顶点）。若 H H H的每个分支均为完全图，则称 H H H是 G G G的一个理想子图。用 N r ( G ) N_r (G) Nr​(G)表示 G G G的具有 r r r 个分支的理想子图的个数。（有 n n n 个顶点就对应 n n n 个 N r ( G ) N_r (G) Nr​(G)）

定理2 设 q r ( G ) q_r(G) qr​(G)表示将单图 G G G的顶点集合 V V V划分为 r r r 个不同色组的色划分个数，则：

q r ( G ) = N r ( G ‾ ) . . . . . ( 1 ≤ r ≤ ∣ V ∣ ) q_r(G){=}N_r(\overline{G}).....(1{\leq}r{\leq}|V|) qr​(G)=Nr​(G).....(1≤r≤∣V∣)

上面定理2实际上给我们提供了色多项式的求法：用 k k k种颜色对单图 G G G正常着色，可以这样来计算着色方式数：色组为1的方式数+色组为2的方式数+…+色组为 n n n的方式数。即有如下计数公式： P k ( G ) = ∑ i = 1 n N i ( G ˉ ) [ k ] i , 其中, [ k ] i = k ( k − 1 ) ( k − 2 ) . . . ( k − i + 1 ) P_k(G)=\sum_{i=1}^nN_i(\bar{G})[k]_i,\text{其中,}[k]_i=k(k-1)(k-2)...(k-i+1) Pk​(G)=i=1∑n​Ni​(Gˉ)[k]i​,其中,[k]i​=k(k−1)(k−2)...(k−i+1)

定义2 ： 设 G G G是单图，令 N i ( G ˉ ) = r i , [ k ] i = x i N_i(\bar{G})=r_i , [k]_i=x^i Ni​(Gˉ)=ri​,[k]i​=xi 。称
h ( G , x ) = ∑ i = 1 n r i x i h(G,x)=\sum_{i=1}^nr_ix^i h(G,x)=i=1∑n​ri​xi

为图 G G G的伴随多项式。

于是，求 P k ( G ) P_k(G) Pk​(G)就是要求出 G ‾ \overline{G} G 的伴随多项式。

定理3 若 G G G有 t t t个分支 H 1 , H 2 , … H t H_1,H_2,…H_t H1​,H2​,…Ht​, 且 H i H_i Hi​的伴随多项式为 h ( H i , x ) , i = 1 , 2 , … , t h(H_i, x), i=1,2,…,t h(Hi​,x),i=1,2,…,t, 则：
h ( G , x ) = ∏ i = 1 t h ( H i , x ) h\left(G,x\right)=\prod_{i=1}^{t}h\left(H_{i},x\right) h(G,x)=i=1∏t​h(Hi​,x)

该定理说明，在求 G ‾ \overline G G 的伴随多项式时，可以分别求出它的每个分支的伴随多项式，然后将它们作乘积。

第八章 Ramsey 定理

(一)、独立集与覆盖

定义1 设 G = ( V , E ) G=(V ,E) G=(V,E)是一个图。 V V V的一个顶点子集 V 1 V_1 V1​称为 G G G的一个点独立集, 如果 V 1 V_1 V1​中的顶点互不邻接；

G G G的一个包含顶点数最多的独立集称为 G G G的最大独立集。最大独立集包含的顶点数，称为 G G G的点独立数，记为 α ( G ) α(G) α(G)。

定义2 设 G = ( V , E ) G=(V ,E) G=(V,E)是一个图。 V V V的一个顶点子集 K K K称为 G G G的一个点覆盖, 如果 E E E中的每条边至少有一个端点在 K K K中。

G G G的一个包含顶点数最少的点覆盖称为 G G G的最小点覆盖。最小点覆盖包含的顶点数，称为 G G G的点覆盖数，记为 β ( G ) β(G) β(G)。

定理1 (加莱) 对任意不含孤立点的 n n n阶图 G G G，有：
α ( G ) + β ( G ) = n α(G)+ β(G)= n α(G)+β(G)=n

(二)、边独立集与边覆盖

定义3 设 G = ( V , E ) G=(V ,E) G=(V,E)是一个图。 E E E的一个边子集 E 1 E_1 E1​称为 G G G的一个边独立集, 如果 E 1 E_1 E1​中的边互不邻接；

G G G的一个包含边数最多的边独立集称为 G G G的最大边独立集。最大边独立集包含的边数，称为 G G G的边独立数，记为 α ′ ( G ) α'(G) α′(G) 。

注： 单图的一个边独立集实际上就是图的一个匹配，一个最大边独立集就是其一个最大匹配。

定义4 设 G = ( V , E ) G=(V ,E) G=(V,E)是一个图。 E E E的一个边子集 L L L 称为 G G G的一个边覆盖, 如果 G G G中的每个顶点均是 L L L中某条边的端点。

G G G的一个包含边数最少的边覆盖称为 G G G的最小边覆盖。最小边覆盖包含的边数，称为 G G G的边覆盖数，记为 β ′ ( G ) β'(G) β′(G)。

定理2 (加莱) 对任意不含孤立点的 n n n阶单图 G G G，有：
α ′ ( G ) + β ′ ( G ) = n α'(G)+ β'(G)= n α′(G)+β′(G)=n

定理3 设 G G G是无孤立点的偶图，则 G G G中最大点独立集包含的顶点数等于最小边覆盖所包含的边数。

定义5 设 G = ( V , E ) G=(V ,E) G=(V,E)是一个图。 v v v是 G G G的一个顶点， e e e是 G G G的一条边。若 β ( G − v ) < β ( G ) β(G-v) < β(G) β(G−v)<β(G)（删掉这个顶点后，点覆盖数减小） , 称 v v v是 G G G的 β β β临界点；若 β ( G − e ) < β ( G ) β(G-e) < β(G) β(G−e)<β(G) , 称 e e e是 G G G的 β β β临界边。

容易知道：若 v v v是 G G G的一个 β β β临界点，则：
β ( G − v ) = β ( G ) − 1 \beta(G-v)=\beta(G)-1 β(G−v)=β(G)−1

定理4 点 v v v是图 G G G的 β β β临界点当且仅当 v v v含于 G G G的某个最小点覆盖中。

定义6 设 G = ( V , E ) G=(V ,E) G=(V,E)是一个图。若 G G G的每个顶点是 G G G的 β β β临界点，称该图是 β β β 点临界图；若 G G G的每条边均是 G G G的 β β β临界边，称该图是 β β β 边临界图。

定义7 设 m m m和 n n n是两个正整数，如果存在最小的 r ( m , n ) r(m ,n) r(m,n)阶的图 G G G, 使得 G G G中或者有 K m K_m Km​或者有 n n n个顶点的独立集，则称正整数 r ( m , n ) r(m, n) r(m,n)为 ( m , n ) (m, n) (m,n)拉姆齐数。

如果用定义直接求 r ( m , n ) r(m, n) r(m,n), 一般是先恰当找出一个 k k k阶图 G 1 G_1 G1​,说明它既不含 K m K_m Km​，也不含 n n n点独立集，得到 r ( m , n ) > k r(m, n)>k r(m,n)>k; 然后再找到一个 k + 1 k+1 k+1阶图 G 2 G_2 G2​, 说明它或者包含 K m K_m Km​或者含有 n n n点独立集，得到 r ( m , n ) ≤ k + 1 r(m, n)≤k+1 r(m,n)≤k+1.

通过上面的方法，得到： r ( m , n ) = k + 1 r(m, n)=k+1 r(m,n)=k+1。

第九章 有向图

定义1 一个有向图 D D D是指一个三元组 ( V ( D ) , E ( D ) , ϕ D ) (V(D) , E(D), \phi_D) (V(D),E(D),ϕD​)。其中， V ( D ) V(D) V(D)是非空的顶点集合， E ( D ) E(D) E(D)是不与 V ( D ) V(D) V(D)相交的边集合，而 ϕ D \phi_D ϕD​ 是关联函数，它使 D D D的每条边对应 D D D的有序顶点对 (不必相异即点对中的点允许相同)。

如果 e e e是 D D D的一条边，而 u u u与 v v v是使得 ϕ D ( u , v ) = e \phi_D(u,v)=e ϕD​(u,v)=e的顶点，那么称 e e e是由 u u u连接到 v v v，记为 e = < u , v > e=<u, v> e=<u,v>。同时，称 u u u为 e e e的弧尾(起点), v v v为 e e e的弧头(终点)。

定义2 在一个有向图 D D D中，具有相同起点和终点的边称为平行边。两点间平行边的条数称为该两点间的重数。

定义3 在一个有向图 D D D中，如果没有有向环和平行边，则称该图为简单有向图。

定义4 设 D D D是有向图，去掉 D D D中边的方向后得到的无向图 G G G，称为 D D D的基础图。又若 G G G是无向图，给 G G G的每条边加上方向后得到的有向图 D D D称为 G G G的一个定向图。（一个有向图的基础图唯一，而一个图的定向图不唯一，有方向）

定义5 设 D D D是有向图， v v v是 D D D中顶点。以 v v v为始点的边的条数称为点 v v v的出度，以 v v v为端点的一个自环算 1 1 1度。点 v v v的出度记为 d + ( v ) d^+(v) d+(v); 以 v v v为终点的边的条数称为点 v v v的入度，以 v v v为端点的一个自环算 1 1 1度。点 v v v的入度记为 d − ( v ) d^-(v) d−(v);

点 v v v的出度与入度之和称为点 v v v的度，记为 d ( v ) d(v) d(v)。

定理1 设 D = ( V , E ) D=(V, E) D=(V,E)是有向图，则：
∑ v ∈ V ( D ) d + ( v ) = ∑ v ∈ V ( D ) d − ( v ) = m ( D ) \sum_{v\in V(D)}d^+(v)=\sum_{v\in V(D)}d^-(v)=m(D) v∈V(D)∑​d+(v)=v∈V(D)∑​d−(v)=m(D)

定义6 设 D = ( V , E ) D=(V,E) D=(V,E)是有向图，其中 V = { v 1 , v 2 , … , v n } , E = { e 1 , e 2 , … , e m } V=\{v_1, v_2,…, v_n\}, E=\{e_1, e_2,…, e_m\} V={v1​,v2​,…,vn​},E={e1​,e2​,…,em​}

(1) 称 A ( D ) = ( a i j ) n × n A(D)=(a_{ij})_{n×n} A(D)=(aij​)n×n​是 D D D的邻接矩阵，其中 a i j a_{ij} aij​是 v i v_i vi​为始点， v j v_j vj​为终点的边的条数， 1 ≤ i ≤ n , 1 ≤ j ≤ n 1 ≤ i ≤ n,1 ≤ j ≤ n 1≤i≤n,1≤j≤n。

(2) 若 D D D无环。称矩阵 M = ( m i j ) n × m M=(m_{ij})_{n×m} M=(mij​)n×m​是 D D D的关联矩阵，其中

定义7 设 D = ( V , E ) D=(V, E) D=(V,E)是有向图， u u u与 v v v是 D D D中两个顶点。

1) 若 D D D中存在一条 ( u ， v ) (u，v) (u，v)路，则称 u u u可达 v v v, 记为 u → v u→v u→v。规定 u → u u →u u→u。
2) 若 D D D中存在一条 ( u ， v ) (u，v) (u，v)路或 ( v , u ) (v, u) (v,u)路，则称 u u u与 v v v是单向连通的。
3) 若 D D D中存在一条 ( u ， v ) (u，v) (u，v)路和一条 ( v , u ) (v, u) (v,u)路，则称 u u u与 v v v是双向连通的或强连通的。

定义8 设 D = ( V , E ) D=(V, E) D=(V,E)是有向图。
1) 若 D D D的基础图是连通的，称 D D D是弱连通图；
2) 若 D D D的中任意两点是单向连通的，称 D D D是单向连通图；
3) 若 D D D的中任意两点是双向连通的，称 D D D是强连通图；

强连通一定是单向连通，弱连通，单向连通一定是弱连通

关于强连通图，我们有如下结论：
定理1： 有向图 D = ( V , E ) D=(V,E) D=(V,E)是强连通的，当且仅当 D D D中存在包含 D D D中所有顶点的回路。

定义9 设 D D D是有向图 D = ( V , E ) D=(V, E) D=(V,E)的一个子图。如果 D D D是强连通的(单向连通的、弱连通的),且 D D D中不存在真包含 D D D的子图是强连通的(单向连通的、弱连通的), 则称 D D D是 D D D的一个强连通分支(单向连通分支、弱连通分支)。

强连通分支： 一个极大的强连通子图
单向连通分支： 一个极大的单向连通子图
弱连通分支： 一个极大的弱连通子图

定理2： 有向图 D = ( V , E ) D=(V,E) D=(V,E)的每个点位于且仅位于 D D D的某个强(弱)连通分支中。

标签：图论,定义,汇总,定理,平面图,连通,着色,顶点
From： https://blog.csdn.net/qq_46450354/article/details/138991517