【图论】重庆大学图论与应用课程期末复习资料2-各章考点（填空证明部分）（私人复习资料）

一、图与网络的基本概念

1. 生成子图：生成子图$G’$
2. 顶点集导出子图：$V1\subseteq V$
3. 边集导出子图：$E1\subseteq E$
4. 简单图：既无环又无重边的图为简单图
5. 完备图：任二顶点相邻的简单图,称为完备图,记为 $K_n$
6. 二部图：一个图是偶图（二部图）当且当它不包含奇圈
7. 握手定理：图$G=(V,E)$
8. 同构：顶点集之间存在一一对应关系，边也有一一对应的关系,则称图 $G$

二、树

1. 树：无圈连通图称为树
2. 树充要条件：$G$
3. 树充要条件：$G$
4. 树充要条件：$G$
5. 生成树：$G$

三、连通性

1. 点连通度：设$G$
2. 边连通度：设$G$
3. k连通图：若一个图的连通度至少为$k$
4. 点连通度、边连通度、最小度：$K(G)<=K^{\prime }(G)<=\delta （G）$
5. 割边：设e是图G的一条边，若$\omega (G-e)＞\omega (G)$
6. 割点：$v$
7. 割集：$[S,S^{\prime }]$
8. 树和图：设$v$

习题15：去掉

e

=

(

u

,

v

)

e= (u, v)

e=(u,v) ，在

G

−

e

G-e

G−e中

u

u

u所在的分支仅有一个奇度顶点，与握手定理矛盾

习题16：反证法，

e

=

(

u

,

v

)

e= (u, v)

e=(u,v) ，

G

−

e

G-e

G−e中

u

u

u所在的分支

G

1

G_1

G1​，

G

1

G_1

G1​为二部图，因为二部图所有子图均为二部图，则

Σ

（

G

1

）

=

k

∣

X

1

∣

=

k

∣

Y

1

∣

−

1

=

&gt;

k

Σ（G_1）=k|X_1|=k|Y_1|-1=&gt;k

Σ（G1​）=k∣X1​∣=k∣Y1​∣−1=&gt;k，

（

∣

X

1

∣

−

∣

Y

1

∣

）

=

1

（

k

&gt;

=

2

）

（|X_1|-|Y_1|）=1（k&gt;=2）

（∣X1​∣−∣Y1​∣）=1（k&gt;=2），不成立

四、路径算法

1. Floyd：复杂度$O（n^3）$

五、匹配

1. 边独立集（匹配）：如果$M$
2. 最大匹配：如果$M$
3. 二部图理想匹配：若$G$
4. 贝尔热定理：$G$
5. Hall定理：二分图存在完美匹配当且仅当 $\forall S\subseteq A$
6. 哥尼定理：在偶图中，最大匹配的边数等于最小覆盖的顶点数
7. 托特定理：图$G$

六、行遍性问题

1. 欧拉巡回：经过$G$
2. 欧拉图：存在欧拉巡回的图称为欧拉图或E图
3. 欧拉图的充要条件：连通、无奇度顶点
4. 欧拉道路的充要条件：连通、最多只有两个奇度顶点
5. 哈米尔顿路径：经过图$G$
6. 哈米尔顿图：经过$G$
7. H图的必要条件：$$\begin{gathered} 其\forall S\subset V，S\ne \varnothing \\ \omega (G-S)\le |S| \end{gathered}$$

七、平面图

1. 平面图：一个图若能在曲面$S$
2. 欧拉公式：设$G=(n,m)$
3. 平面图推论：$G$
4. 库拉托夫斯基定理：图$G$

代码007普通

打赏 收藏 海报 链接