以下显示部分文章预览。
网络与容许流
定义：一个网络\(N(V,E,C)\)是一个赋权有向简单弱连通图，满足：
1. V中恰有一个负度为0的结点s，称为发点（源）；
2. V中恰有一个正度为0的结点他，称为收点（汇）；
3.每条边\(v_i,v_j)\)的边权\(c_{i,j}\)是一个非负实数，称为该边的容量，\(C=(c_{i,j}\)为网络的容量函数。
定义：如果在网络\(N(V,E,C)\)的边集E上定义一个非负实值函数\(f=(f_{i,j})\)，满足一下条件：
1. 容量限制条件，\(f_{i,j}\le c_{i,j}\)；其中等号成立的边称为饱和边。
2. 平衡条件，对每个中间点v，有\(\sum\limits_{u\in N(v)} f_{u,v} = \sum\limits_{u\in N(v)} f_{v,u}.\)
设F为网络\(N(V,E,C)\)所有容许流组成的集合，称\(f_0=\arg\max w(f)\)为网络\(N(V,E,C)\)的最大流。
割切
定义：设S是网络N的结点子集，如果满足\(s\in S, t\in \bar S\)，则\(S\times \bar S\)的所有有向边组成的集合称为N的一个割切，记为\((S,\bar S)\)。其中所有边的容量之和\[C(S,\bar S)=\sum\limits_{(u,v)\in (S,\bar S)} c_{u,v}\]称为割切\((S,\bar S)\)的容量。最小容量的割切称为最小割切。
引理1. 设f是网络N的任一容许流，\((S,\bar S)\)是N的任一割切，则有\[w(f) = \sum\limits_{u\in S,v\in\bar S} f_{u,v} - \sum\limits_{u\in \bar S,v\in S} f_{u,v}\]
定理2. 设f是网络N的任一容许流，\((S,\bar S)\)是N的任一割切，则有\[w(f)\le C(S,\bar S)\]
定理3. 若f是N最大流，则f的流量等于N的最小割切的容量。
发表于2022-08-25
图的匹配问题
定义：设M是G的边子集，G是无向简单连通图（下同），M中任意两边不相邻，则称M是G的一个匹配。与M中边关联的点称为M的饱和点，其余为非饱和点。
定义：设M是G的一个匹配。如果对G的任一个匹配\(M'\)都有\(|M|\ge|M'|\)，称M是G的最大匹配。特别的，若G的结点都是饱和点，称M为完美匹配。
定义：给定G的一个匹配M，G中属于M和不属于M的边交替出现的道路称为关于M的交错道路。如果交错道路P的起点和终点都是关于M的非饱和点，称P为可增广道路。
定理1. M是G的最大匹配当且仅当G中不存在关于M的可增广道路。
证明：必要性，若P是M的可增广道路，则\(P\oplus M\)边数比M多1；充分性，取G的最大匹配\(M'\)，令\(G'=M\oplus M'\)，则\(\Delta(G')\le 2\)（因为任一个匹配中的点至多与一边关联），\(G'\)的连通分支只有2种：要么是由M和\(M'\)的边交错形成的偶回路，要么是\(M'\)与\(M\)的边交错形成的道路P。P一定有偶数条边，否则P是M或M'的可增广道路。综上可知\(|M|=|M'|\)。
利用定理1可以给出求解最大匹配的算法：反复寻找可增广道路。
二部图的匹配
定义：设M是二部图\(G=(X,Y,E)\)的匹配，若\(|M|=|X|\)，则称M是G的从X到Y的完全匹配。
引理2. 设M是G的一个匹配，\(x_0\)不是X中的饱和点。令U表示X中所有可通过以\(x_0\)为起点的交错道路到达的结点（含\(x_0\)），V表示Y中所有可通过以\(x_0\)为起点的交错道路到达的点，则有：
1. 存在以\(x_0\)为起点的可增广道路\(\Leftrightarrow\)V中存在M的非饱和点；
2. 不存在以\(x_0\)为起点的M的可增广道路\(\Leftrightarrow\)\(N(U)=|U|-1\)。
证明：结论1是显然的。对于结论2，首先说明U中除了\(x_0\)都是M的饱和点，V中的点也都是M的饱和点。必要性：由于每个V中的饱和点唯一对应一个U中除\(x_0\)外根据M的匹配唯一对应于V的点，所以\(|V|=|U|-1\)且\(N(U)=V\)。充分性：如果\(|N(U)| = |U|-1\)，若存在以\(x_0\)为起点的可增广道路，取\(M'=M\oplus P\)，则U和V的点都是\(M'\)的饱和点，\(|U|=|V|\)，矛盾。
定理3. 在二部图\(G=(X,Y,E)\)中，存在X到Y的完美匹配的充要条件是对X的任意子集\(A\subseteq X\)，恒有\(|N(A)|\ge |A|\)。
证明：必要性，设M是X到Y的完全匹配，因为A中的点一一匹配到\(N(A)\)中的点，所以\(|A|=|N(A)|\)。充分性，任取G的一个最大匹配M，若M不是完全匹配，则存在非饱和点\(x_0\in X\)，不存在以\(x_0\)为起点的M可增广道路，由引理存在\(U\subseteq X\)使得\(N(U)=|U|-1\)，矛盾。
推论4. 设k是正整数，若在二部图\(G=(X,Y,E)\)中，对任意\(x\in X, y\in Y\)都有\(d(x)\ge k, d(y)\le k\)，则存在从X到Y的完美匹配。
定理5. 令\(\epsilon(A) =\max\{|A|-|N(A)|, 0\},\epsilon(G) = \max\limits_{A\subseteq X} \epsilon(A)\)，则\(G=(X,Y,E)\)的最大匹配边数是\(|X|-\epsilon(G)\)。
证明：容易证明G的最大匹配边数不超过\(|X|-\epsilon(G)\)。下面给出构造，断言：若\(\epsilon(A)=\epsilon(G)\)，则导出子图\(G'=(X-A, Y-N(A), E')\)满足\(\epsilon(G')=0\)。否则存在\(X-A\)的子结点集B，使得\(|B| > |N(B)\cap (Y-N(A))|\)，此时计算得\(\epsilon(A\cup B) > \epsilon(G).\)下面对\(\epsilon(G)\)进行归纳。
发表于2022-08-25
割点、割边和块
定义：设v是G的结点，如果\(G-v\)的连通分支比G多，则称v是G的一个割点。类似定义割边。
如果G有割边，则G一定有割点。
定义：图G的极大的无割点连通子图称为G的块。
如果G没有割点，则G本身是一个块。
定理1. 设v是G的结点。则以下论断等价：
1. v是G的割点；
2. 存在两个不同于v的结点u，w使得任意一条u到w的道路P都经过v；
3. \(V-v\)可以划分为两个结点子集\(U,W\)，使得任意\(u\in U, w\in W\)，v都在u到w的任意一条道路上。
定理2. 设e是G的一边。则以下论断等价：
1. e是G的割边；
2. e不属于G的任何回路；
3. 存在两结点u，v，使得e属于任何u到v的道路；
4. \(G-e\)的结点集可以划分为两个结点子集\(U,W\)，使得任意\(u\in U, w\in W\)，e都在u到w的任意一条道路上。
定理3. 设G是n阶无向连通图，则G是块当且仅当G的任意两结点在同一回路上。
证明：充分性显然。必要性对\(d(u,v)\)归纳。注意利用块的性质：删去任一结点后仍连通。
定理4. 设G是阶不小于3的连通图，则以下论断等价：
1. G是块；
2. G的任何两结点同属于某回路；
3. G的任一结点和任一边同属于某回路；
4. G的任意两边同属于某回路；
5. 给定任意两结点u，v和一边e，存在一条从u到v的道路包含e；
6. 对任意三个结点u，v，w，存在从u到w的道路经过v；
7. 对任意三个结点u，v，w，存在从u到w的道路不经过v。
证明：既得1，2，3，4等价，\(3\Rightarrow5\Rightarrow6\Rightarrow7\Rightarrow1\)显然。
可以在G的边集上定义一个等价关系：\(e_1\sim e_2\)当且仅当\(e_1,e_2\)在同一回路上或\(e_1=e_2\)。\(\sim\)的等价类即G的块。
连通度
定义：若连通图G删去结点子集\(A\subseteq V\)后不连通，称A为G的一个点断集。
称\(\mu(G)=\min |A|\)为G的连通度。
定义：对于连通图G的断集B，称\(\lambda(G)=\min |B|\)为G的边连通度。
定理5. 连通图G中有\[\mu(G)\le\lambda(G)\le\delta(G)\]
定义. 设G是连通图，若\(\mu(G)\ge k,\)则称G是k连通图；若\(\lambda(G)\ge k\)，则称G是k边连通图。
定理6. 简单连通图G中，有\(\mu(G)\le [\frac{2m}{n}]\)。
证明：由握手定理显然。
用\(f(k,n)\)表示n阶k连通图的最少边数，则定理6说明\(f(k,n)\ge \lceil \frac {kn}{2}\rceil\)。
定理7. 设G是n阶简单图，k是正整数，结点度满足：\(d(v_1)\le d(v_2)\le \cdots\le d(v_n)\),且当\(1\le r\le n-1-d(v_{n-k+1})\)时有\(d(v_r)\ge r+k-1\)，则G是k连通图。
定理8. 设G是n阶简单图，若\(\delta(G)\ge \lfloor \frac n 2\rfloor\)，则\(\lambda(G)=\delta(G)\)。
证明：先证G是连通图。再取\(\lambda(G)\)边的断集，分别估计两个连通分支的边数。
定理9. 设G是n阶连通图，\(k\le n-1\)。则以下结论成立：
1. G是k连通的，当且仅当G中任意两点之间至少有k条内部不交的道路。
2. G是k边连通的，当且仅当G中任意两结点之间至少存在k条边不重复的道路。
发表于2022-08-25
图的着色
图的着色问题包括点着色，边着色，平面图的域着色。这三类问题都可以通过对偶关系转化为图的点着色问题。
定义：给定图G，满足相邻结点着不同颜色，所需的最少颜色数称为G的色数，记作\(\gamma(G)\)。
一些典型图的色数：\(\gamma(K_n)=n, \gamma(K_n-e)=n-1\)，非空二部图色数为2，奇回路色数为3，
\(\gamma(G\times H) = \max(\gamma(G),\gamma(H)).\)
定理1. 设\(u,v\)在简单图G中不相邻。记\(\bar G=G+(u,v), H=G\circ \{u,v\}\), 则\(\gamma(G)=\min\{\gamma(\bar G), \gamma (H)\}\).
证明：对于G的着色方案，若\(u,v\)颜色不同则可以相连，若颜色相同则\(u,v\)可收缩为一点。重复操作得到某完全图，其阶数即G的色数。
最优着色问题是NP-难的。可以采用贪心着色算法得到近似解。
贪心着色算法：首先随机选择一个结点着色。然后依次选择未着色的点，选择一个不会造成颜色冲突的颜色。利用贪心着色算法可得：
定理2. 任意简单图G有\(\gamma(G)\le \Delta(G)+1.\)
一个更强的版本是：
定理3. 任意简单连通图G有\(\gamma(G)\le\Delta(G)\)，除非G是完全图或者奇回路。
证明：当\(k=\Delta(G)\le 2\)时，结论成立。下设\(k\ge 3\)。基于贪心着色算法，我们的目标是将n个结点排序，使得每个结点至多有\(k-1\)个序号比它小的结点与它相邻。
当G不是k正则图时，取定一个度小于k的结点，作为\(v_n\)。因为G是连通图，从\(v_n\)出发，利用宽度优先检索算法，得到G的一颗生成树。 依照被检索顺序的倒序，得到结点序列\(v_1,v_2,\cdots, v_n\)。因此，对于\(v_1,\cdots,v_{n-1}\)中任意一点，总有一个邻点序号比它大（因为存在一条到\(v_n\)的道路），故序号比自己小的邻点至多\(k-1\)个。
当G是k-正则图时，首先若G存在割点x，则对G删去x后的每个连通分支\(V_i\)，\(V_i\cup\{x\}\)都有k着色方案，令在这几个图中x的着色相同即可。
若G无割点，只需说明存在某个结点\(v_n\), 使得\(v_n\)有两个邻点\(v_1,v_2\)满足\(v_1,v_2\)不相邻，且G删去\(v_1,v_2\)仍连通，此时我们同样可以从\(v_n\)出发得到\(G-\{v_1,v_2\}\)的排序。
情况一：删去G的任何两个不同结点后都连通，因为G不是完全图，必有两结点\(u,v\)不相邻且\(d(u,v)\ge 2\)。取\(v_1=v\)，在\(u,v\)道路上与v最近的两点分别为\(v_n,v_2\)。
情况二：存在G的两结点\(x,y\)使得\(G-\{x,y\}\)不连通。则\(G-\{x\}\)仍连通，但有割点。因为x与G-x的每个叶子块有邻点，取\(v_1,v_2\)某两个叶子块上的x邻点。因为\(k\ge 3\)，所以x还有其他邻点，故\(G-\{v_1,v_2\}\)仍连通。取\(v_n=x\)即可。
色数多项式
设\(f(t,G)\)是用t种颜色对G着色的不同方案数，则\(f(t,G)\)是关于t的多项式。
定理4. 设\(u,v\)在G中不相邻。记\(G_{u,v} = G+(u,v), H_{u,v}=G\circ \{u,v\}\)，则\(f(t,G)=f(t,G_{u,v})+f(t, H_{u,v})\)。
推论5. 设e是简单图G的一条边，则\(f(t,G) = f(t,G-e)-f(t, G\circ e)\)。
发表于2022-08-24
平面图
定义：如果能把图G画在一个平面上，使得任何两边不相交，称G是可平面图。可平面图在平面上的一个嵌入（画法）称为平面图。
定义：设G是平面图。由它的若干条边所围成的区域内如果不含任何其它边，则称该区域为G的一个面或域。包围这个域的边称为其边界。
平面图G外边的无限区域称为无限域，其他的域叫内部域。每个域的边界是一条闭路径（不一定是道路），其长度称为域的边界长度。
割边只是一个域的边界（无限域），非割边一定是两个域的公共边界。平面图的每条边对边界长度的贡献都是2，因此域的边界长度之和等于\(2|E|\)。
定理1(欧拉公式). 设G是平面连通图，则G的域个数是\(d=m-n+2\)。
证明：取G的一颗生成树T，逐一加入T的弦。
推论2(欧拉不等式). 对任意平面图（不一定连通），有\(n-m+d\ge 2.\)
推论3. 若G是阶不小于3的简单平面图，则\(m\le 3n-6\)。
证明：如果G不含回路，由连通性知\(m\le n-1\le 3n-6\)。否则，G的每个域边界数不小于3，因此\(3d\le 2m\)，带入欧拉不等式即得。
类似可以证明如果G的每个域边数不小于4，则\(m\le 2n-4\)。
定理4. \(K_5,\ K_{3,3}\)都是不可平面图。
证明：\(K_5\)边数为10，由推论3即得。\(K_{3,3}\)每个域的边界数不小于4，与\(m\le 2n-4\)推出矛盾。
\(K_5,\ K_{3,3}\)分别记作\(K^{(1)}, K^{(2)}\)图。本质上只有这两种非平面图。我们先介绍图同胚概念。
定义： 如果对图G进行如下若干操作：
1. 在图G某边中插入一个结点，使该边变成2条边；
2. 将G某个度为2的结点关联的两条边合并成一条。
得到的图\(G'\)称为与G同胚。图G可平面当且仅当G的任意同胚图可平面。
与\(K^{(1)},K^{(2)}\)所有同胚图分别称为\(K^{(1)},K^{(2)}\)型图，统称K型图。
定理5. 图G可平面的充要条件是G没有K型子图。
平面图的对偶图
定义：设G是平面图，如下定义的图\(G^*\)称为G的对偶图。
1. G的每个域\(f\)内设置一结点\(v^*\)作为\(G^*\)的结点；
2. 对G的非割边\(e\)，必为两域\(f_i, f_j\)的公共边界，取\(e^*\)连接\(v_i^*,v_j^*\)；
3. 对G的割边，必是某域\(f\)的边界，画\(G^*\)的一条自环\(e^*=(v^*,v^*)\)。
性质1. 平面图G的对偶图\(G^*\)唯一，且满足\(m^*=m,n^*=d, d^*=n\)。
性质2. \(G^*\)是连通图。
性质3. \((G^*)^*\)同构于G。
性质4. G的回路对应\(G^*\)的割集，G的割集对应\(G^*\)的回路。
发表于2022-08-24
有向树
定义：设T是有向树，如果它有一个结点的入度为0，其余结点的入度均为1，则称T为根树。入度为0的结点称为树根，出度非0的结点称为分支点，出度为0的点称为树叶。
从根结点到结点v的有向路长度称为v的层数。最大层数称为树的高度。
定义：如果T的分支点都至多有m个儿子，称T为m元树。若每个分支点都恰有m个儿子，称为正则m元树。若正则m元树的所有树叶都在同一层，称为完全m元树。
定理1. 正则二元树的分支点数i与树叶数t满足\(i=t-1\)。
定理2. 设T是一颗正则二元树，I表示各分支点的层数之和，E表示各树叶的层数之和，则\(E=I+2i\)。
最优树
定义：设二元树T有t片树叶\(v_1,\cdots, v_t\)，分别带权\(w_1,\cdots, w_t\in \mathbb R^+\)，则称T为赋权二元树，称\(w(T)=\sum\limits_{i=1}^t w_i\cdot l(v_i)\)为二元树T的权，其中\(l(v)\)是树叶v的层数。
定义：在所有含t片树叶，且叶子权重分别为\(w_1,\cdots,w_t\)的二元树中，权最小的二元树称为最优二元树。
给定正实数\(w_1,\cdots,w_t\)，构造一颗带权\(w_1,\cdots, w_t\)的最优二元树的哈夫曼算法可描述如下：
初始化\(S=\{w_1,\cdots,w_t\}, V=\{v_1,\cdots, v_t\}, E=\emptyset, w(v_i)=w_i\)；
从S中取出权最小的\(w_a,w_b\)，令\(w'=w_a+w_b\)；
更新S：删去\(w_a,w_b\)并加入\(w'\)， V中加入权为\(w'\)的结点\(v'\)，E中加入\(v'\)与\(v_a,v_b\)的连边；
当S只有一个元素时结束。
编码
定义：设\(A=\{\beta_1,\cdots, \beta_m\}\)是一个字符串集合，若对\(A\)中任意两个不同的码字\(\beta_i,\beta_j\)，都互相不是对方前缀，则称A为前缀码。
一个二元前缀码唯一对应一颗有序二元树。
给定字符集\(\{A_1,\cdots, A_t\}\)，及表示这些字符的二元前缀码\(\{\beta_1,\cdots, \beta_t\}\)，如果\(A_i\)出现的频率为\(w_i\)，码字\(\beta_i\)的长度为\(l_i\)，则用此二元前缀信息码表示信息花费的比特量是\(\sum\limits _{i=1}^t l_iw_i.\)
发表于2022-08-23
基本树变换
定义：设\(T_1,T_2\)是连通图G的一颗生成树，若\(T_1,T_2\)恰有k条边不同，则称\(T_1,T_2\)的距离为\(d(T_1,T_2)=k.\)
定义：设\(d(T_1,T_2)=1.\) 若\(T_1-T_2=e_1,T_2-T_1=e_2\)， 则\(T_2=T_1\oplus\{e_1,e_2\}\)称为\(T_1\)到\(T_2\)的基本树变换。
在基本树变换下，必有\(e_1\in C_{e_2}\)，否则\(C_{e_2}\subseteq T_2\)，矛盾。
定理1. 设\(T\)是连通图G的一颗生成树。则G的任意其它生成树都可由T经过有限次基本树变换得到。
最小生成树算法
Kruskal算法：
初始化\(T=\emptyset\)。
每次操作
选择\(E\)中不属于\(T\)的最小边e，如果e与T不形成回路则加入T中；
从E中删去e。
当\(|T|=n-1\)时终止。
证明：假设Kruskal算法得到的\(T^*\)不是最小树，其边的添加顺序为\(e_1,e_2,\cdots,e_{n-1}\)。对任何一个最小生成树\(T\)，令\(i(T)\)是首个不在T中的\(e_i\)的下标。
取\(T_0=\arg\max i(T)\)，此处的想法是找一个与\(e_1,e_2,\cdots,e_{n-1}\)的前缀重合最多的最小生成树，再利用\(T^*\)的定义找到一个前缀相同更多的最小生成树，从而得到矛盾。
设\(t=t(T_0)\)，则\(e_1,\cdots,e_{t-1}\in T_0, e_t\not\in T_0\)。根据\(T_0\)的选法，任何一颗最小生成树都不能同时包含\(e_1,\cdots,e_{t}\)。
但是，因为\(e_t\)是\(T_0\)的弦，取\(e\in C_{e_t}-T^*\)，做基本树变换\(T'=T\oplus \{e,e_t\}\)。则\(w(T')=w(T_0)-w(e)+w(e_t)\)。因为\(\{e_1,\cdots, e_{t-1}, e\}\)不包含回路，所以根据\(T^*\)的构造过程，有\(w(e)\ge w(e_t)\)。因此\(w(T')\le w(T_0)\)，即\(T'\)也是最小生成树，且包含\(e_1,\cdots,e_{t}\)，矛盾。
Prim算法：
任选结点\(v_0\)，初始化\(T=\emptyset, U=\{v_0\}\)。
每次操作
选择\(u\)为不在U中，且与U中任意点距离最短的点；
将u加入U中，并将u与原U内的最短边加入T中；
更新U中点与其它点的最短距离。
当\(|T|=n-1\)时终止。
发表于2022-08-23
树的定义及其性质
定义：不含任何回路的连通图成为树。度为1的点称为树叶，大于1的点称为分支点。
定义：设e是图G的一条边。如果\(G-e\)的连通分支多于G，称e是G的一条割边。
定理1. e是G的割边，当且仅当e不属于G的任何回路。
定理2. 设T是阶不小于2的无向简单图，则以下说法等价：
1. T连通，且无回路
2. T连通，且每条边都是割边
3. T连通，且有n-1条边
4. T有n-1条边，且无回路
5. T的任意两结点之间有唯一道路
6. T无回路，但任意加上一条边后，恰有一个回路。
证明：\(1\Leftrightarrow 2, 2\Rightarrow 3, 3\Rightarrow 4, 4\Rightarrow 5, 5\Rightarrow 6, 6\Rightarrow 1\)
推论3. 设G是结点数为n的、连通分支数为k的森林，则G的边数为\(n-k\)。
回路与割集
定义：设T是连通图G的生成树，\(e_1,\cdots, e_{m-n+1}\)是T的弦，记\(C_r\)是T加弦\(e_r\)产生的回路。称\(C_r\)为对应弦\(e_r\)的基本回路，\(\{C_1,\cdots,C_r\}\)。
定理3. 设T是连通图G的一颗生成树，\(C_k\)是对应于弦\(e_k\)的基本回路，对于任意r及序列\(1\le i_1< \cdots < i_r\le m-n+1\)，有\(e_{i_1},\cdots,e_{i_r}\)是\(C_{i_1}\oplus \cdots\oplus C_{i_r}\)的所有弦。
证明：只需注意到\(e_i\)只在\(S_i\)中出现。
下面说明G中任意回路都可由基本回路生成。
引理4. 如果图\(G_1,G_2\)的结点都是偶结点，则\(G_1\oplus G_2\)的结点也都是偶结点。
定理5. 连通图G的任何回路C均可表示为生成树T的若干基本回路的环和。
证明：设C中含T的r条弦，取\(C'\)为这r条弦对应的基本回路之环和。断言\(C=C'\)，否则\(C\oplus C'\)非空，而由定理3知\(C\oplus C'\)的边都在T中，由引理4知这些结点都是偶结点，必包含回路，矛盾。
推论6. 设连通图G的回个数为c，则\(m-n+1\le c \le 2^{m-n+1}-1\).
生成树与基本割集系统
定义：设\(S\)是图G的边集E的子集，且满足：
1. \(G'=(V,E-S)\)不连通；
2. 对任意\(S'\subsetneq S\)， \(G''=(V,E-S'')\)仍连通。
定理7. 设T是连通图G的生成树，则T的每一树枝对应G的一个割集。
证明：取e为T的一个树枝。从T中删去e得到二连通分支\(T_1,T_2\)，分别对应结点集为\(V_1,V_2\)，G中所有两端点分别在\(V_1,V_2\)的边组成集合为\(S_e\)，则\(S_e\)是仅包含T中一条边e的割集。
由定理7可以引出基本割集系统的概念。基本割集系统与基本回路系统有类似的性质。
定义：设T是连通图G的生成树，\(n-1\)个树枝对应的割集\(S_1,\cdots, S_{n-1}\)称为对应T的基本割集，称\(\{S_1,\cdots, S_{n-1}\}\)为对应T的基本割集系统。
定理8. 连通图G的每个割集必包含G中每棵生成树的至少一个树枝。
定理9. 设\(\{S_1,\cdots, S_{n-1}\}\)是G相对于生成树T的基本割集系统，则\(S_{i_1}\oplus \cdots\oplus S_{i_k}\)的所有树枝是\(e_{i_1}, \cdots, e_{i_k}\)。
证明与定理3类似。
为了说明任意割集可由基本割集生成，我们还需引入断集的概念。
定义：设G是无向图，\(V_1\)是V的非空真子集，所有两端点分别在\(V_1,\bar V_1\)中的边组成的集合记作\(E(V_1\times\bar V_1)\)，成为G的一个断集。
割集一定是断集，但断集未必是割集。
引理10. 设\(S_1,S_2\)是无向图G的两个不同断集，则\(S_1\oplus S_2\)也是G的断集。
证明：令\(V_0=(V_1\cap V_2)\cup (\bar V_1\cap \bar V_2)\)， 则\(S_1\oplus S_2=E(V_0\times\bar V_0)\)。
定理11. 连通图G的任意割集可以表示为生成树T的对应若干基本割集的环和。
证明：任取G的割集S，设S包含T的k条边，取\(S'\)为这k条边对应的基本割集之环和。如果\(S\ne S'\)，则\(S\oplus S'\)是断集，但不包含T的任何边，与定理8矛盾。
定理12. 任何一个回路与任何一个断集都有偶数条公共边。
推论13. 设T是连通图G的生成树，e是T的树枝，\(e'\)是T的弦。则\[e\in C_{e'}\Leftrightarrow e'\in S_e.\]
发表于2022-08-21
欧拉图
定义：
1. 若无向连通图G中有一条包含G中所有边的闭链，则称此链为欧拉闭链（欧拉链），G成为欧拉图
2. 若G中有一条包含G中所有边的开链，则称此开链为欧拉开链，G为半欧拉图。
注：半欧拉图一定不是欧拉图。
定理1. 无向连通图G是欧拉图的充分必要条件是G中各结点都是偶节点。
充分性证明：取G的最长链C，说明C是闭链，且G所有边在C上。
推论2: 无向连通图G是半欧拉图的充要条件是G恰有2个奇结点。
推论3: 设D是有向弱连通图，则D存在有向欧拉闭链额度充要条件是D中各节点正度和负度相等。
哈密顿图
定义：
1. 无向图G的一条过全部结点的回路（道路）成为G的哈密顿回路（道路），简记为H回路（道路）。包含H回路（道路） 的图成为哈密顿图（半哈密顿图），简称H图（半H图）。
定理4: 若无向图G是H图，则对于结点集的任意子集\(X\subseteq V(G)\)均有\[K(G-X)\le|X|\]其中\(K(\cdot)\)表示连通分支数。
证明：设C是G的一个H回路，只需证\(K(C-X)\le|X|\)。对\(|X|\)进行归纳。
下面给出H图的一个充分条件。
引理5: 对于无向简单图G的任意一条极长道路\(P=v_1\cdots v_l\)，若\(d(v_1)+d(v_l) >l-1\)，则G中存在回路C，使得\(V(C)=V(P)\)。
证明：注意极长道路的性质给出\(v_1,v_l\)的邻点都在P上。存在\(2\le s \le l\)使得\(v_s,v_1\)和\(v_{s-1}, v_l\)分别相邻。
定理6. 如果简单图G的任意两不同结点\(u,v\)都满足\(d(u)+d(v)\ge n-1\)，\(n=|V(G)|\)，则G中存在H道路。
证明：首先说明G是连通图。再取G的一条最长道路P，由引理5得G中存在回路C使得\(V(C)=V(P)\)。最后说明G中所有点在C上。
推论7. 如果简单图G的任意两不同结点\(u,v\)都满足\(d(u)+d(v)\ge n\)，则G中存在H回路。
推论8. 如果简单图G满足\(\delta(G)\ge \frac n 2\)，则G是H图。
引理9. 设G是无向简单图，u和v是G的不相邻结点且满足\(d(u)+d(v)\ge n\)。则G是H图的充要条件是\(G+(u,v)\)是H图。
定义：对无向简单图G，另\(G_0=G\)，再令\(G_{i+1}=G_i+(u_i,v_i)\)其中\(u_i,v_i\)是无向简单图\(G_i\)中的不相邻结点，且满足\(d_{G_i}(u_i)+d_{G_i}(v_i)\ge n\)，直到存在\(k\)使得\(G_k\)中不存在满足\(d(u)+d(v)\ge n\)的不相邻结点。则\(G_k\)成为G的闭合图，记作\(C(G)\)。
引理10. 无向简单图G的闭合图\(C(G)\)是唯一的，即与添加边的顺序无关。
定理11. 无向简单图G是H图，当且仅当\(C(G)\)是H图。
定义：若有向简单图D的每两个不同结点之间恰有一条边，则称D为竞赛图。
定理12. 任意竞赛图D必有H道路。
证明：对n归纳，分别取\(v_{n+1}\)的内、外邻点集的H道路，再通过\(v_{n+1}\)相连。
定理13: 任何强连通的竞赛图D是有向H图。
发表于2022-08-21
道路与回路的定义
无向图的有限点边交替序列\(P=\{v_0,e_1,v_1,\cdots, e_m,v_m\}\)称为G的一条路径，m称为P的长度。
边均不相同的路径称为链，点均不相同（或者只有\(v_0=v_m\)）的路径称为道路/路。
起点与终点相同\(v_0=v_m\)的路径/链/路称为闭路径/闭链/回路。
设C是G中含顶点数大于3的一个回路，如果\(v_i,v_j\)在C中不相邻但\(e=(v_i,v_j)\in E\). 称e为C的一条弦。
Prop1. 如果\(\delta(G)\ge 2,\)则G中存在回路；如果\(\delta(G)\ge 3,\)则G中存在带弦回路。
如果两结点u,v之间存在路径，称u和v是连通的，记作\(u\sim v\). 此时u和v之间长度最短的路径称为u和v的距离，记作\(d(u,v)\). 最大距离\(d(G)\)称为G的直径。
连通是等价关系。G的连通分支数记为\(\kappa(G).\)
k-部图：如果图G的结点集V可以划分成k个非空子集\(V_1,\cdots,V_k\)，使得G的每条边的两个结点不会出现在同一个\(V_i\)中，称G是k部图。k=2时称为二部图。
Theorem 1. 无向图G是二部图当且仅当G中不包含奇回路。
对于有向图而言，如果任意两个结点之间互相可达，称为强连通图；如果任意两个结点可达，称为单连通图；如果G的基图是连通图，称为弱连通图。
Theorem 2.
有向图D是强连通图\(\Leftrightarrow\)D中存在一条闭路径包含D的所有结点；
D是单连通图\(\Leftrightarrow\)D中存在一条路径包含D的所有结点。
图G的连通性判断：
1. 代数法，定义路径矩阵\(P=(p_{i,j})_{n\times n}\), 使得\(p_{i,j}=1\)当且仅当\(v_i\)可达\(v_j\). 在布尔基意义下, P可由邻接矩阵Aa计算得到,\[P=A\lor A^2\lor\cdots A^n.\]也可用Warshall算法在\(O(n^3)\)时间内计算：对\(k,i,j\)依次循环\[P_{i,j}\leftarrow P_{i,j}\lor(P_{i,k}\land P_{k,j})\]
2. 搜索法：从某一结点出发，寻找所有与其连通的结点集，如深度优先/广度优先。
最短道路
寻找赋权图\(G=(V,E,w)\)中任意两结点的最短路径。
1. Dijkstra算法
从\(u_0\)出发，维护探索集S并初始化为\(S=\{u_0\}\).
每次寻找S以外的点到\(u_0\)距离最短，加入S中并更新\(u_0\)到S外其他点的距离。
2. Floyd算法
初始化距离矩阵\(D=(d(i,j))_{n\times n}\)和前趋矩阵\(P=(p(i,j))_{n\times n}\)其中\(p(i,j)=i\).
对\(k=1...n\)操作\(d(i,j) = d(i,k) + d(k,j)\)若此操作可以减小\(d(i,j)\), 并更新前趋\(p(i,j) = p(k,j)\).
发表于2022-05-20