第一章 图的基本概念
1.1 概念
- 平凡图：只有一个顶点并且没有边
- 简单图：既没有环也没有重边的图
- \(n\)阶图：顶点数为\(n\)的图
- 顶点\(u\)与\(v\)相邻接\((adj)\)：顶点\(u\)与\(v\)有边相连接；其中\(u\)与\(v\)称为该边的两个端点。
- 顶点\(u\)与边\(e\)相关联：顶点\(u\)是边\(e\)的端点
- 边\(e_1\)与边\(e_2\)相邻接：边\(e_1\)与边\(e_2\)有公共端点
- 完全图：每两个不同的顶点之间都有一条边相连的简单图，记为\(K_n\)
- 完全偶图：具有二分类\((X,Y)\)的简单偶图，其中\(X\)的每个顶点于\(Y\)的每个顶点相连。若\(|X|=m, |Y|=n,\)则这样的完全偶图记为\(K_{m,n}\)
- 一个图是偶图当且仅当它不包含奇圈。
- \(G\)的顶点\(v\)的度\(d(v)\)是指\(G\)中与\(v\)关联的边的数目，每个环计算两次。\(\delta(G)\)为最小度，\(\Delta(G)\)为最大度。
- \(\displaystyle \sum^{}_{v \in V}{d(v)=2m}\) （握手定理）
- 在任何图中，奇度顶点个数为偶数
- 正则图的阶数和度数不同时为奇数
- 简单图\(G\)：\(\displaystyle \delta \leq \frac{2m}{n}\leq \Delta\)
- 简单图中每个顶点的度数都为\(k\)，则称\(k\)正则图
- 度序列：图\(G\)的各个点的度\(d_1,d_2,...,d_n\)构成的非负整数组\((d_1,d_2,...,d_n)\)称为图\(G\)的度序列
- 非负整数组\((d_1,d_2,...,d_n)\)是图的度序列的充分必要条件为\(\displaystyle \sum^{}_{}{d_i}\)为偶数
- 图序列：一个非负数组如果是某简单图的度序列，则称图序列
- 非负整数组\(\displaystyle \pi =(d_1,d_2,...,d_n),d_1\geq d_2\geq ...\geq d_n,\sum^{n}_{i=1}d_i=2m\)是图序列的充分必要条件为 \[\pi _1=(\underbrace{d_2-1,d_3-1,...,d_{d_1+1}-1}_{d_1\small个-1\small项},d_{d_1+2},...,d_n)\small 是图序列\]
- 非负整数组\(\displaystyle \pi =(d_1,d_2,...,d_n),d_1\geq d_2\geq ...\geq d_n,\sum^{n}_{i=1}d_i=2m\)是图序列的充分必要条件为 \[\pi _1=(\underbrace{d_2-1,d_3-1,...,d_{d_1+1}-1}_{d_1\small个-1\small项},d_{d_1+2},...,d_n)\small 是图序列\]
- 自补图：若\(n\)阶图\(G\)是自补的，则\(n=0,1(mod\ 4)\)
- 生成子图：如果图\(G\)的一个子图包含\(G\)的所有顶点，称该子图为\(G\)的一个生成子图。(生成子图不需要连通，生成树是连通的)
1.2 图运算
- 对称差：\(G_1 \Delta G_2=(G_1 \cup G_2)-(G_1 \cap G_2)\) 注：求\(M\)可扩路用到
- 联图：在不相交的\(G_1\)和\(G_2\)的并图\(G_1+G_2\)中，把\(G_1\)的每个顶点和\(G_2\)的每个顶点连接起来所得到的图称为\(G_1\)和\(G_2\)的联图，记为\(G_1\) V \(G_2\)。
- 联图的顶点数\(n_1+n_2\)，边数\(n_1n_2+m_1+m_2\)
- 积图：设\(G_1=(V_1,E_1),G_2=(V_2,E_2)\)是两个图，对点集\(V=V_1 \times V_2\)的任意两个点\(u=(u_1,u_2),v=(v_1,v_2)\)，当\((u_1=v_1 且 u_2\ adj\ v_2)\)或\((u_2=v_2 且 u_1\ adj\ v_1)\)时，把\(u\)和\(v\)相连，得到的新图记为\(G=G_1 \times G_2\)。
- 积图的顶点数\(n_1n_2\)，边数\(n_1m_2+n_2m_1\)
1.3 最短路
- 迹：边不重复的途径称为图的一条迹
- 路：顶点不重复的途径称为图的一条路
- Dijkstra算法
1.4 极图
- \(l\)部图：若简单图\(G\)的点集\(V\)有一个划分 \[V=\bigcup^{l}_{i=1}{V_i},V_i \cap V_j=\varnothing,i \neq j\] 且所有\(V_i\)非空，\(V_i\)内的点均不连通，则称\(G\)是一个\(l\)部图
- 完全\(l\)部图：如果在一个\(l\)部图\(G\)中，任意部\(V_i\)中的每个顶点同\(G\)中其他各部中的每个顶点均邻接，称\(G\)为完全\(l\)部图，记作\(G=K_{n_1,n_2,...,n_l},(n_i=|V_i|,1 \leq i \leq l)\)
- 完全\(l\)几乎等部图：如果在一个\(n\)个点的完全\(l\)部图\(G\)中有 \[n=kl+r,0 \leq r < l\] \[|V_1|=|V_2|=...=|V_r|=k+1\] \[|V_{r+1}|=|V_{r+2}|=...=|V_{l}|=k\] 则称\(G\)为\(n\)阶完全\(l\)几乎等部图，记为\(T_{l,n}\)
- 完全\(l\)等部图：\(|V_1|=|V_2|=...=|V_l|\)的完全\(l\)几乎等部图称为完全\(l\)等部图
- 托兰定理
- 设\(G\)和\(H\)是两个\(n\)阶图，称\(G\)度弱于\(H\)，如果存在双射\(\mu\):\(V(G)\rightarrow V(H)\)，使得\(\forall v\in V(G)\)有\(d_G(v)\leq d_H(\mu (v))\)
- 若\(n\)阶简单图\(G\)不包含\(K_{l+1}\)，则\(G\)度弱于某个完全\(l\)部图\(H\)，且若\(G\)具有与\(H\)相同的度序列，则\(G\cong H\)
- (\(Tur\acute{a}n\))若\(G\)是简单图，并且不包含\(K_{l+1}\)，则\(m(G)\leq m(T_{l,n})\)，仅当\(G\cong T_{l,n}\)时，有\(m(g)=m(T_{l,n})\)
- 应用：工兵排雷
