图论基础学习笔记

这里主要是我自己的一些笔记，帮助我自己快速记忆所用，可能没有定义这么完美。

1.简单图

简单图：无环无平行边的图。下图：左环右平行边

平凡图：$G=(1,0)$
零图：$G=(p,0)$
边数：$e\le C_n^2$

2.简单图的补图

补图：对于 $G=(V,E)$，有 E 1 = { u v ∣ u ≠ v 且 u , v ∈ V } E_1=\{uv|u \neq v 且 u,v\in V\} E1​={uv∣u​=v且u,v∈V}，则 $G$ 的补图为：
$$\overline{G}=H=(V,E_1\backslash E)$$ 注意：
1、简单图才有补图；
2、$n$ 阶简单图与其补图的顶点集是相同的；
3、$n$ 阶简单图任意一对顶点邻接(有边)的充要条件是这对顶点在补图中不邻接；
4、$n$ 阶简单图与其补图的边数之和等于完全图 $K_n$ 的边数。

3.图的同构

有 $G=(V,E),H=(U,F)，|V|=|U|$ $$若\exists \phi :V\to U(\phi 是双射)$$ $$且v_1{v}_2\in E\iff \phi (v_1)\phi (v_2)\in F$$ 则称 $G$ 和 $H$ 同构 ，记为 $G\cong H$（即给 $V$ 中的顶点重新命名得到新的集合 $U$）。例如下图中，第一行的两个图是相等的，只是画法不同；在第二行，左图选出两个不同颜色的点交换位置，得到右图，则左图和右图为同构。

4.完全图

完全图：是一个简单图，图中任意一个顶点都与其他顶点有且只有一条边连接。$n$ 个顶点的完全图用 $K_n$ 表示，称为 $n$ 阶完全图。例如：

从左往右依次为：1至5阶完全图，即为 $K_1,K_2,K_3,K_4,K_5$ ，完全图的边数为 $C_n^2=\frac{n(n-1)}{2}$。

5.偶图

偶图：在一个图 $G=(V,E)$ 中，顶点集 $V$ 可分解为两个非空子集 $X$ 和 $Y$，且边的两个顶点分别属于 $X$ 和 $Y$ （两个顶点不在同一个子集中），且属于同一子集的顶点不邻接，也没有环。偶图可以有平行边。如下图：

现实生活中的例子有很多，比如：老师和课程，一个老师可以教多个课程，一个课程可以有多个老师来教。

6.完全偶图

完全偶图：首先是简单偶图（简单图+偶图），其次 $X$ 中的每个顶点都与 $Y$ 中每个顶点相连。 若 $|X|=n$， $|Y|=m$，则完全偶图记为 $K_{n,m}$，边数为 $nm$；如下完全偶图 $K_{3,3}$，顶点分为两部分，蓝色集和红色集，每一个蓝色顶点都与全部红色的顶点邻接，且相同颜色的顶点不邻接。

7. $k$-正则图

$k$-正则图：设 $G=(V,E)$ 为简单图，若 $\forall v\in V$，有 $d(v)=k$（顶点度数都为 $k$，环算2度），则 $G$ 为 $k$-正则图。

8.途径-迹-路

途径： 图 $G=(V,E)$ 中的一个有限非空序列 $w=v_0{e}_1{v}_1{e}_2{v}_2\cdots e_n{v}_n$，顶点和边交替出现；途径中边数为途径的长度，$v_0$ 和 $v_n$ 分别为途径的起点与终点，其余顶点为途径的内部点。
迹： 不包含重复边的途径，可以有重复顶点。
路： 不包含重复顶点的途径（一定是迹）。
注： 起点和终点重合的途径、迹、路分别称为图的闭途径、闭迹、圈，闭迹也称为回路。长度为 $k$ 的圈称为 $k$ 圈，$k$ 为奇数时称为奇圈，$k$ 为偶数时称为偶圈。

9.邻接矩阵

邻接矩阵：表示图中各顶点之间的关系，若邻接则为1，反之为0。如下图：

邻接矩阵为： [ 0 1 1 1 1 0 1 1 1 1 0 0 1 1 0 1 ]

⎣⎢⎢⎡​0111​1011​1100​1101​⎦⎥⎥⎤​

10.关联矩阵

关联矩阵：表示图中顶点与边之间的关系，通过关联次数来表示，0，1，2（环）。如下图：

关联矩阵为： [ 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 2 ]

⎣⎢⎢⎡​1100​0110​0101​1010​1001​0002​⎦⎥⎥⎤​ 每列相加的和为2（因为一条边关联两个顶点）；每行和是对应顶点度数。

11.匹配

匹配：如果 $F$ 是图 $G=(V,E)$ 的边子集（不含环），且 $F$ 中任意两条边没有共同顶点，则称 $F$ 为 $G$ 的一个匹配或对集或边独立集。匹配是关于边的。如果图 $G$ 中的顶点是 $F$ 中某条边的端点，则称为 $F$ 饱和点，反之为 $F$ 非饱和点。

最大匹配：$F$ 是图 $G$ 的包含边数最多的匹配。

完美匹配：最大匹配包含了图 $G$ 中的所有顶点。

注意：这些匹配都不一定唯一。