<离散数学> DM3 图论

DM3 图论

DM3.1 图

• 无序积

  $A\&B= \{$$\{ x,y\} \mid x\in A∧ y\in B\}$

  其中，记 $\{ x,y\} =(x,y)$，允许 $x=y$，且 $(x,y)=(y,x)$

• 无向图

  $V(G)$ 是顶点集，$E(G)$ 是边集，且 $V\not=Ø$、$E\subseteq V\&V$

  则无向图 $G=⟨ V,E⟩$

  比如：无向图 $G=\lang V,E\rang\quad V=\{ a,b,c,d\} \quad E=\{ (a,b),(b,c),(b,c),(b,d)\}$ 的样子如下所示

  graph LR
  A((a))---B((b))---C((c))
  B---C
  B---D((d))

• 有向图

  $V(D)$ 是顶点集，$E(D)$ 是边集，且 $V\not=Ø$、$E\subseteq V\times V$

  则有向图 $D=⟨ V,E⟩$

  比如：有向图 $D=⟨ V,E⟩\quad V=\{ a,b,c,d\} \quad E=\{ ⟨ a,b⟩,⟨ a,c⟩,⟨ b,c⟩,⟨ b,d⟩\}$ 的样子如下所示

  graph LR
  A((a))-->B((b))-->C((c))
  C-->B
  B-->D((d))

• n 阶图

  $\quad\mid V(G)\mid =n$

  当 $n<∞$ 时称为 有限图。当 $E=Ø$ 时称为 零图。当 $V=E=Ø$ 时称为 空图

  1 阶的零图 $N_1$ 称为平凡图

  下面是一些例子

  graph BT
  subgraph 1阶图
  l1(( ))
  end
  subgraph N4
  n41(( ))
  n42(( ))
  n43(( ))
  n4(( ))
  end
  subgraph N1
  n1(( ))
  end
  subgraph 2阶图
  direction LR
  l2(( ))---l21(( ))
  end
  subgraph 3阶图
  direction LR
  l3(( ))---l31(( ))
  l32(( ))---l32
  l3
  end

• 标定图、非标定图、底图

  标定图：顶点或边 带标记的图

  非标定图：顶点和边 不带标记的图

  底图（基图）：有向图去掉边的方向后得到的无向图

• 相邻、邻接、关联

  有边相连的两个顶点是 相邻 的，有公共顶点的两条边是 相邻 的

  在有向图中，有向边的起点 邻接到 终点，终点 邻接于 起点

  一条边的端点与该边是关联的

  关联次数：

  graph TB
  A1((1))---A2((1))
  B1((2))---B1
  C1((+1))-->C2(( -1))
  D1((?))--无法表示-->D1

• 环、孤立点、平行边

  两边是同一顶点的边称为 环

  没有边相连的顶点称为 孤立点

  两端顶点相同的边称为 平行边，在有向图中，平行边的方向必须相同

• 邻域、闭邻域、关联集

  邻域：一个点的相邻点构成的集合称为 邻域（开邻域）

  $\quad N_G(v)=\{ u\in V(G)\mid (u,v)\in E(G)∧ u\not=v\}$

  闭邻域：一个点及其相邻点构成的集合称为 闭邻域

  $\quad\overline{ N_G(v)} =N_G(v)\cup\{ v\}$

  关联集：一个点关联的边构成 关联集

  $\quad I_G(v)=\{ e\mid e\,与\,v\,关联\}$

  后继：在有向图中，一个点的后继点构成的集合

  $\quad{ \Gamma_D} ^+(v)=\{ u\in V(D)\mid ⟨ v,u⟩\in E(D)∧ u\not= v\}$

  前驱：在有向图中，一个点的前驱点构成的集合

  $\quad{ \Gamma_D} ^-(v)=\{ u\in V(D)\mid ⟨ u,v⟩\in E(D)∧ u\not= v\}$

  有向图的开邻域：$N_D(v)={ \Gamma_D} ^+(v)\cup{ \Gamma_D} ^-(v)$

  有向图的闭邻域：$\overline{ N_D(v)} =N_D(v)\cup\{ v\}$

• 顶点的度

  度：$d_G(v)=与\,v\,关联的边的次数之和$

  出度：${ d_D} ^+(v)=与\,v\,关联的出边的次数之和$

  入度：${ d_D} ^-(v)=与\,v\,关联的入边的次数之和$

  最大度：$\Delta(G)=\operatorname{ max} \{ d_G(v)\mid v\in V(G)\}$

  最小度：$\delta(G)=\operatorname{ min} \{ d_G(v)\mid v\in V(G)\}$

  最大出度、最大入度、最小出度、最小入度

• 握手定理

  设 $G=⟨ V,E⟩$ 是无向图，$V=\{ v_1,v_2,\dots,v_n\} ,\,\mid E\mid =m$

  则 $d(v_1)+d(v_2)+\dots+d(v_n)=2m$

  推论：任何图中，奇数度顶点的个数是偶数

• 简单图

  没有环和平行边的图称为 简单图

  对于简单图，其最大度 $0\le\Delta(G)\le n-1$

• 正则图

  所有顶点的度相等的图称为 正则图，度为 $k$ 则称为 $k\,正则图$

• 度数列、可图化

  由所有顶点的度构成的数列称为 度数列

  $\quad d=(d(v_1),d(v_2),\dots,d(v_n))$

  若存在图 $G$ 使得 $G$ 的度数列是 $d$，则称 $d$ 是 可图化 的

  $\quad d\,可图化⇔ d_1+d_2+\dots+d_n\equiv 0(\operatorname{ mod} 2)$

  若存在简单图 $G$ 使得 $G$ 的度数列是 $d$，则称 $d$ 是 可简单图化 的

  $\quad d\,可简单图化$
  $⇔d'=(d_2-1,d_3-1,\dots,d_n-1)\,可简单图化$
  $⇔∀ r(r\ge1∧ r\le n-1)→ d_1+d_2+\dots+d_r\le r(r-1)+\min \{ r,d_{ r+1} \} +\min \{ r,d_{ r+2} \} +\dots+\min \{ r,d_{ n} \}$
  $⇔n-1\ge d_1\ge d_2\ge\dots\ge d_n\ge 0⇒ d_1+d_2+\dots+d_n\le n(n-1)$

• 同构

  对于图 $G_1,G_2$

  如果存在双射 $f:V(G_1)→ V(G_2)$ 使得 $∀ a,b\in V(G_1),\,(a,b)\in E(G_1)↔ (f(a),f(b))\in E(G_2)$ 就称 $G_1$ 与 $G_2$ 同构。记为 $G_1\cong G_2$

  同构的图，其图论性质完全一致

  对于有向图 $D_1,D_2$ 同理，存在双射 $f:V(D_1)→ V(D_2)$ 使得 $∀ a,b\in V(D_1),\,⟨ a,b⟩\in E(D_1)↔ ⟨ f(a),f(b)⟩\in E(D_2)$ 就称 $D_1$ 与 $D_2$ 同构，记为 $D_1\cong D_2$

  • NAUTY 算法

    一种计算两个图是否是同构的算法

    详见 这个网站

• 一些图族

  完全图：无向图的每个顶点都与所有其他顶点相邻。n 阶的完全图记为 $K_n$

  竞赛图：完全图的每条边都是有向边

  r 部图：该图的顶点可以分为 r 组，每条边的两个端点位于不同的组

• 子图、生成子图

  对于图 $G,G'$，若有 $V'\subseteq V∧ E'\subseteq E$，则 $G'$ 是 $G$ 的子图，记为 $G'\subseteq G$

  若 $G'\subseteq G∧(V'\subset V∧ E'\subset E)$，则 $G'$ 是 $G$ 的真子图，记为 $G'\subset G$

  若 $G'\subseteq G∧ V'=V$，则 $G'$ 是 $G$ 的生成子图

• 导出子图

  若 $V_1\subset V,\, E_1=E\cap V_1\&V_1$ 则称 $G[V_1]=⟨ V_1,E_1⟩$ 是由 $V_1$ 导出的子图

  若 $Ø\not=E_1\subset E,\, V_1=\{ v\mid v\,与\,E_1\,中的边关联\}$ 则称 $G[E_1]=⟨ V_1,E_1⟩$ 是由 $E_1$ 导出的子图

• 补图

  对于图 $G=⟨ V,E⟩$，其补图 $\overline G=⟨ V,E(K_n)-E⟩$

  如果 $G\cong\overline G$，则称其为 自补图

• 删除

  删除边 $e$：$G-e=⟨ V,E-\{ e\} ⟩$

  删除边集 $E'$：$G-E'=⟨ V,E-E'⟩$

  删除顶点 $v$ 及其关联的所有边：$G-v=⟨ V-\{ v\} ,E-I_G(v)⟩$

  删除顶点集 $V'$ 及关联的所有边：$G-V'=⟨ V-V',E-I_G(V')⟩$

• 收缩、加边

  删除 $e$，合并 $u$ 与 $v$：$G{ \setminus} e:e=(i,v)$

  在 $u,v$ 间增加新边：$G\cup(u,v)=⟨ V,E\cup\{ (u,v)\} ⟩$，也可以写为 $G+(u,v)$

• 不交

  对于 $G_1,G_2$

  $\quad G_1\,与\,G_2\,不交⇔ V_1\cap V_2=Ø$

  $\quad G_1\,与\,G_2\,边不交⇔ E_1\cap E_2=Ø$

• 并图、交图、差图、环和

  对于无孤立点的图 $G_1,G_2$

  并图：$G_1\cup G_2=⟨ V(E_1\cup E_2),E_1\cup E_2⟩$

  交图：$G_1\cap G_2=⟨ V(E_1\cap E_2),E_1\cap E_2⟩$

  差图：$G_1-G_2=⟨ V(E_1-E_2),E_1-E_2⟩$

  环和：$G_1\oplus G_2=⟨ V(E_1\oplus E_2),E_1\oplus E_2⟩$

• 联图

  $G_1,G_2$ 是不交的无向图

  其联图 $G_1+G_2=⟨ V_1\cup V_2,E_1\cup E_2\cup(V_1\&V_2)⟩$

  $\quad K_r+K_s=K_{ r+s} \quad N_r+N_s=K_{ r,s} \quad n=n_1+n_2,\,m=m_1+m_2+n_1n_2$

DM3.2 通路、回路

• 通路、回路

  图中邻接的点与边的交替序列构成 通路

  $\quad\Gamma =v_1,e_1,v_2,e_2,\dots,v_n$

  通路的起止都是顶点。通路中边的数量称为通路的 长度

  如果通路的起止点是同一顶点，则称该通路为 回路

  没有重复边的通路（回路）称为 简单通路（简单回路）

  有重复边的通路（回路）称为 复杂通路（复杂回路）

  没有重复顶点的通路（回路）称为 初级通路/路径（初级回路/圈）

  可以只用边的序列来表示通路。简单图可以只用顶点的序列表示通路。

  图中最长圈的长度称为图的 周长。不含圈时，长度为 $0$ 或 $∞$

  有以下定理：

  • 在 $n$ 阶图 $G$ 中，若从不同顶点 $v_i$ 到 $v_j$ 有通路，则从 $v_i$ 到 $v_j$ 有长度小于等于 $n-1$ 的通路

    推论：在 $n$ 阶图 $G$ 中，若从不同顶点 $v_i$ 到 $v_j$ 有通路，则从 $v_i$ 到 $v_j$ 有长度小于等于 $n-1$ 的路径

  • $G\,是二部图⇔ G\,中无奇圈$

  • 若无向图 $G$ 是连通图，则 $G$ 的边数 $m\ge n-1$

• 极大路径

  在无向简单图中，路径的两个端点不与路径本身以外的顶点相邻，这样的路径称为 极大路径

  在有向图中，路径起点的前驱、终点的后继，都在路径本身上，这样的路径称为 极大路径

• 连通图、分离图

  图中的两个顶点 $u,v$ 间存在通路，则称 $u$ 与 $v$ 连通。记作：$u\sim v$

  每个顶点都与自身连通。即 $u\sim u$

  连通关系是 自反、对称、传递 的。连通关系是等价关系。彼此联通的顶点集合构成 连通分支。记为 $G[v_i]$

  设 $V/\sim=\{ V_i\mid i=1,\dots,k\}$，则连通分支数 $p(G)=\mid V/\sim\mid$

  连通分支数为 1 的图称为 连通图

  连通分支大于 1 的图称为 分离图

  $u,v$ 间最短的通路称为 短程线（测地线）

• 距离、直径

  $u,v$ 间短程线的长度称为其 距离，记为 $d_G(u,v)$

  图中所有距离的最大值称为图的 直径。$d(G)=\max(d_G(u,v)\mid u,v\in V(G))$

  有 $d(K_n)=1(n\ge2),\,d(C_n)=n/2$，并且约定零图的直径：$d(N_i)=\begin{cases}0,\quad i=1\\∞,\quad i>1\end{cases}$

• 距离函数

  距离函数具有三个特征

  • 非负性：$d(u,v)\ge0∧ d(u,v)=0⇔ u=v$
  • 对称性：$d(u,v)=d(v,u)$
  • $\Delta$不等式：$d(u,v)+d(v,w)\ge d(u,w)$

  任何函数只要满足上述三条特征就能作为距离函数使用。

• 可达、弱连通

  对于有向图 $D=⟨ V,E⟩$，若从 $u$ 到 $v$ 有有向通路，则称从 $u$ 可达 $v$，记作 $u→ v$

  规定 $u→ u$。可达关系是 自反、传递的。可达关系的导出子图是 单向连通分支

  若 $u→ v∧ v→ u$ 则称 $u,v$ 双向可达，记作 $u↔ v$

  双向可达关系是等价关系。其等价类的导出子图称为 强连通分支（双向连通分支）

  若有向图的基图是连通图，则称其为 弱连通，其导出子图称为 弱连通分支

  有如下定理：

  • 对于竞赛图，一定有一条路经过每一个点恰好一次

  • $有向图\,D\,强连通⇔ D\,中有回路经过每个点至少一次$

    这个回路不一定是简单回路

  • $有向图\,D\,单向连通⇔ D\,中有通路经过每个顶点至少一次$

    这个通路不一定是简单通路

DM3.3 连通度

• 点割集、边割集

  设有图 $G⟨ V,E⟩$，非空点集 $V'\subset V$，非空边集 $E'\subset E$

  若满足 $p(G-V')>p(G)$，且 $∀ V''\subset V',\,p(G-V'')=p(G)$ 则称 $V'$ 是 $G$ 的一个 点割集。

  若满足 $p(G-E')>p(G)$，且 $∀ E''\subset E',\,p(G-E'')=p(G)$ 则称 $E'$ 是 $G$ 的一个 边割集。

  对于边割集，有引理：$p(G-E')=p(G)+1$

  若 $E'\subseteq I_G(v)$ 则称其为 扇形割集

• 割点、割边（桥）

  $\quad v\,是割点⇔\{ v\} \,是割集$

  $\quad (u,v)\,是割边⇔\{ (u,v)\} \,是割集$

  $I_G(v)$ 不一定是边割集（不一定极小）。当且仅当 $v$ 不是割点时，$I_G(v)$ 是边割集

  有如下引理：

  • 设 $E'$ 是非完全图 $G$ 的最小边割集。若 $G-E'$ 的两个连通分支是 $G_1,G_2$，则存在 $u\in V(G_1),v\in V(G_2)$ 使得 $(u,v)\not\in E(G)$

• 点连通度、边连通度

  点连通度：为了破坏连通性（$p(G-V')>p(G)$），至少要破坏多少个顶点

  边连通度：为了破坏连通性（$p(G-E')>p(G)$），至少要破坏多少条边

  设 $G$ 是无向连通非完全图

  点连通度 $\kappa(G)=\min\{ \mid V'\mid \,\mid V'\,是\,G\,的点割集\}$

  边连通度 $\lambda (G)=\min\{ \mid E'\mid \,\mid E'\,是\,G\,的边割集\}$

  规定：$\kappa(K_n)=n-1$，若 $G$ 非联通则 $\kappa(G)=0,\,\lambda(G)=0$

• K-（边）连通图

  k-连通图：$\kappa(G)\ge k$

  k-边连通图：$\lambda(G)\ge k$

  有定理：

  • 对于 3-正则图 $G$，必定有 $\kappa(G)=\lambda(G)$
  • 对于任意 $G$，都有 $\kappa(G)\le\lambda(G)\le\delta(G)$，也就是说 k-连通图 一定是 k-边连通图

• x-y 割、独立路径、边不交路径

  设 $x,y$ 是 $G$ 中的不相邻顶点

  若存在 $S\subseteq V(G)-\{ x,y\}$，使得在 $G-S$ 中 $x,y$ 不连通，则称 $S$ 为 $G$ 中的 x-y 割。

  两条除起点与终点外无其他公共顶点的路径称为 独立路径

  两条无公共边（但可能有公共顶点）的路径称为 边不交路径

  有如下定理：

  • 最小的 x-y 割包含的定点数，等于最大的 x-y 独立路径的条数

  • 2-连通图 的充要条件

    $\quad 3\,阶以上无向图是\,2-连通图$
    $⇔图中任意两点都共圈$
    $⇔图中任意两顶点间都有\,2\,条以上独立路径$

  • 2-边连通图 的充要条件

    $\quad 3\,阶以上无向图是\,2-边连通图$
    $⇔图中任意两点都共简单回路$
    $⇔图中任意两顶点间都有\,2\,条以上边不交路径$

  • k-连通图 的充要条件

    $\quad 3\,阶以上无向图是k-连通图$
    $\quad ⇔图中任意两顶点间都有\,k\,条以上独立路径$

  • k-边连通图 的充要条件

    $\quad 3\,阶以上无向图是k-边连通图$
    $⇔图中任意两顶点间都有\,k\,条以上边不交$

  • 割点 的充要条件

    $\quad 无向连通图中顶点\,v\,是割点$
    $⇔存在\,u,w\in V(G)-\{ v\} ，使得\,u,w\,间的路径都经过\,v$

  • 桥 的充要条件

    $\quad 无向连通图中边\,e\,是桥$
    $⇔图中任意圈都不经过\,e$
    $⇔可把\,V(G)\,划分为\,V_1,V_2，任意\,u\in V_1\,和\,v\in V_2\,间的路径都经过\,e$

• 块

  极大无割点的连通子图称为一个 块

  有如下定理：

  • 块 的充要条件

    $\quad 3\,阶以上无向图是块$
    $⇔图中任意两顶点都共圈$
    $⇔图中任意顶点与任意边都共圈$
    $⇔图中任意两边都共圈$
    $⇔对于任意边，图中任意两点间都存在经过该边的路径$
    $⇔对于图中任意三点，都存在路径连接其中两点，并经过第三点$
    $⇔对于图中任意三点，都存在路径连接其中两点，且不经过第三点$

  • n 阶简单连通图的 $\kappa,\lambda,\delta$ 间有且仅有三种可能：

    • $\kappa=\lambda=\delta=n-1$（完全图）
    • $1\le2\delta-n+2\le\kappa\le\lambda=\delta\le n-2$（即 $\delta\ge n/2$ 时）
    • $0\le\kappa\le\lambda\le\delta<n/2$

DM3.4 欧拉图、哈密顿图

• 欧拉图

  经过图中所有边的简单通路称为 欧拉通路

  有欧拉通路的图称为 半欧拉图

  经过图中所有边的简单回路称为 欧拉回路

  有欧拉回路的图称为 欧拉图

  有如下定理：

  • 无向欧拉图 的充要条件

    $\quad 无向图连通图是欧拉图$$$⇔图中所有顶点的度都是偶数$$⇔图是若干边不交的圈的并$

  • 无向半欧拉图 的充要条件

    $\quad 无向图连通图是半欧拉图$
    $⇔图中恰有两个奇数度顶点$

  • 有向欧拉图 的充要条件

    $\quad 有向图连通图是欧拉图$
    $⇔∀ v\in V(G),\,d^+(v)=d^-(v)$
    $⇔图是若干边不交的有向圈的并$

  • 有向半欧拉图 的充要条件

    $\quad 有向图连通图是半欧拉图$
    $⇔恰有一个顶点入度=出度+1，另一个顶点入度=出度-1，其余顶点入度=出度$

• 计算欧拉图的方法

  • 避桥法

    从任意一顶点起，沿没有走过的边（优先选择非桥边）到达下一顶点。最终能得到欧拉回路，或宣布该图不是欧拉图。

  • 逐步插入回路法

    每次求出一个简单回路。把新求出的回路插入老回路，合并成更大回路，直到得到欧拉回路，或宣布该图不是欧拉图。

• 哈密顿图

  经过图中所有顶点的初级通路称为 哈密顿通路

  有哈密顿通路的图称为 半哈密顿图

  经过图中所有顶点的初级回路称为 哈密顿回路

  有哈密顿回路的图称为 哈密顿图

  有如下定理：

  • 无向哈密顿图 的必要条件（不是充分条件）

    设无向哈密顿图图 $G=⟨ V,E⟩$，则有 $∀ V_1(V_1\not=Ø∧ V_1\subset V)→ p(G-V_1)\le\mid V_1\mid$

  • 无向半哈密顿图 的必要条件（不是充分条件）

    设无向半哈密顿图 $G=⟨ V,E⟩$，则有 $∀ V_1(V_1\not=Ø∧ V_1\subset V)→ p(G-V_1)\le\mid V_1\mid +1$

  • 无向哈密顿图 的充分条件（不是必要条件）

    对于 $n(n\ge3)$ 阶无向简单图，若其中任意不相邻顶点 $u,v$ 都有 $d(u)+d(v)\ge n$，则该图是哈密顿图

  • 无向半哈密顿图 的充分条件（不是必要条件）

    对于 $n(n\ge2)$ 阶无向简单图，若其中任意不相邻顶点 $u,v$ 都有 $d(u)+d(v)\ge n-1$，则该图是半哈密顿图

  • 有向半哈密顿图 的充分条件（不是必要条件）

    $n(n\ge2)$ 阶竞赛图是有向半哈密顿图

  • 有向哈密顿图 的充分条件（不是必要条件）

    强连通的竞赛图是有向半哈密顿图

  • 完全图 $K_{ 2n+1}$ 必定同时包含 $n$ 组边不重的哈密顿回路，且这些哈密顿回路包含所有边。

    对 $i=1,2,\dots,k$，令 $P_i=v_i,v_{ i-1} ,v_{ i+1} ,v_{ i-2} ,v_{ i+2} ,\dots,v_{ i-(k-1)} ,v_{ i+(k-1)} ,v_{ i-k}$

    将 $P_i$ 中的下标 $\operatorname{ mod} { 2k}$ 后转换到 $\{ 1,2,\dots,2k+1\}$

    则所有 $C_i=v_{ 2k+1} ,P_i,v_{ 2k+1}$ 都是哈密顿回路

    推论：

    完全图 $K_{ 2n}$ 必定同时包含 $n-1$ 组边不重的哈密顿回路，此外剩余 $n$ 条彼此不相邻的边。

DM3.5 树

• 树

  连通无回路的图称为 树，记作 $T$

  平凡图也称 平凡树。平凡树外，树中度为 1 的顶点称为 树叶，2 以上的顶点称为 分支点

  每个连通分支都是树的无回路图称为 森林

  有如下定理：

  • 对于 $n$ 阶 $m$ 边无向图 $G$，树的等价定义：

    \quadG\,是树
    $⇔G\,中任何两个顶点间有唯一的路径$
    $⇔G\,无圈∧ m=n-1$
    $⇔G\,连通∧ m=n-1$
    $⇔G\,极小连通$
    $⇔G\,极大无回$

    极小连通：连通且所有边都是桥

    极大无回：无圈且新增任何边都会产生唯一的圈

  • 任何非平凡树都至少有 2 个树叶

• 无向树的计数

  用 $t_n$ 来表示 $n(n\ge1)$ 阶非同构无向树的个数

  除了一个点外，其他顶点都是树叶的树称为 星。记作 $S_n=K_{ 1,n-1}$

• 生成树

  对于图 $G$，若其子图 $T$ 是树，且包含 $G$ 中所有顶点，则称 $T$ 是 $G$ 的 生成树

  $T$ 中的边 $e\in E(T)$ 称为 树枝

  不在 $T$ 中的边 $e\in E(G)-E(T)$ 称为 弦

  由弦构成的图称为 余树，记为 $G[E(G)-E(T)]=\overline{ T}$

  有如下定理

  • $无向图\,G\,连通⇔ G\,有生成树$

    若 $G$ 是 $n$ 阶 $m$ 边的无向连通图，则 $m\ge n-1$

    若 $T$ 是 $n$ 阶 $m$ 边无向连通图的生成树，则 $\mid \overline{ E(T)} \mid =m-n+1$

    若 $T$ 是无向连通图 $G$ 的生成树，$C$ 是 $G$ 中的圈，则 $C$ 中必定有弦

  • 设 $T$ 是连通图 $G$ 的生成树，$S$ 是 $G$ 中的割集，则 $S$ 中必有树枝

  • 设 $T$ 是连通图 $G$ 的生成树，$e$ 是 $G$ 的弦，则在 $T\cup e$ 中存在包含 $e$ 的圈，且不同的 $e$ 对应不同的圈

• 基本回路

  设 $G$ 是 $n$ 阶 $m$ 边的无向连通图，$T$ 是其生成树，$\overline{ T} =\{ e'_1,e'_2,\dots,e'_{ m-n+1} \}$ 是余树

  则 $T\cup e'_r$ 中的唯一回路 $C_r$ 称为 基本回路

  由所有 $C_r$ 构成的集合 $\{ C_1,C_2,\dots,C_{ m-n+1} \}$ 称为 基本回路系统

  基本回路系统包含的圈的个数称为 圈秩：$\xi(G)=m-n+1$

  有如下定理

  • 设 $T$ 是连通图 $G$ 的生成树，$e$ 是其树枝，则 $G$ 中存在由树枝 $e$ 和其他弦组成的割集，且不同树枝对应不同的割集

• 基本割集

  设 $G$ 是 $n$ 阶 $m$ 边的无向连通图，$T=\{ e_1,e_2,\dots,e_{ n-1} \}$ 是其生成树

  则 $e_r$ 对应的唯一割集 $S_r$ 称为 基本割集

  由所有 $S_r$ 构成的集合称为 基本割集系统

  割集的秩：$\eta(G)=n-1$

• 生成树的计数

  对于标定图，其生成树的计数记为 $\tau(G)$。$T_1\not= T_2:E(T_1)\not=E(T_2)$

  删除边记为 $G-e$，收缩记为 $G\setminus e$

  有如下定理：

  • $\tau(G)=\tau(G-e)+\tau(G\setminus e)$

    即，$\tau(G)$ 是所有不过边 $e$ 的生成树，加上过边 $e$ 的生成树

  • $n\ge 2⇒\tau(K_n)=n^{ n-2}$

DM3.6 图的矩阵表示

• 有向图关联矩阵

  设 $D=⟨ V,E⟩$ 是无环有向图，$V=\{ v_1,v_2,\dots,v_n\} ,\,E=\{ e_1,e_2,\dots,e_m\}$

  则关联矩阵 $M(D)=[m_{ ij} ]_{ n\times m}$ 有 $m_{ ij} =\begin{cases} 1,\quad v_i\,是\,e_j\,的起点\\0,\quad v_i\,与\,e_j\,不关联\\-1\,\quad v_i\,是\,e_j\,的终点\end{cases}$

  示范一个关联矩阵：$M(D)= \begin{bmatrix} -1&-1&1&0&0&0\\1&1&0&1&0&0\\0&0&-1&-1&1&-1\\0&0&0&0&-1&1\end{bmatrix}$，可见每条边都有一个起点和终点

  有向图关联矩阵的性质如下：

  • 每列和为零：$\sum^n_{ i=1} m_{ ij} =0$

  • 每一行的绝对值的和为 $d(v)$：$d(v_i)=\sum^m_{ j=1} m_{ ij}$

    其中 $1$ 的个数为 $d^+(v)$，$-1$ 的个数为 $d^-(v)$

  • 握手定理（矩阵和为零）：$\sum^n_{ i=1} \sum^m_{ j=1} m_{ ij} =0$

  • 相同的两列是平行边

• 无向图的关联矩阵

  设 $G=⟨ V,E⟩$ 是无环无向图，$V=\{ v_1,v_2,\dots,v_n\} ,\,E=\{ e_1,e_2,\dots,e_m\}$

  则关联矩阵 $M(G)=[m_{ ij} ]_{ n\times m}$ 有 $m_{ ij} =\begin{cases} 1,\quad v_i\,与\,e_j\,关联\\0,\quad v_i\,与\,e_j\,不关联\end{cases}$

  无向图关联矩阵有如下性质：

  • 每列和为 $2$：$\sum^n_{ i=1} m_{ ij} =2$

  • 每一行的绝对值的和为 $d(v)$：$d(v_i)=\sum^m_{ j=1} m_{ ij}$

  • 平行所有 $1$ 对应的边构成 断集：$[\{ v_i\} ,\overline{ \{ v_i\} } ]$

  • 相同的两列是平行边

  • 在非连通图中，连通分支能形成对角块，这样的矩阵叫做 伪对角阵

    $\quad M(G)=\begin{bmatrix} M(G_1)\\&M(G_2)\\&&\ddots\\&&&M(G_i)\end{bmatrix}$

  • 无向连通图的图关联矩阵的秩是 $n-1$：$G\,连通⇒ r(M(G))=n-1$

    有关矩阵的秩

    若矩阵的某一行（列）的元素都是 $0$，则该行（列）称为 零行（列）

    对矩阵进行如下变换称为 初等变换

    • 对调两行
    • 将一行的元素全部乘 $k\,(k\not=0)$
    • 把某一行元素的 $k\,(k\not=0)$ 倍加到另一行上

    对一个矩阵进行初等变换后，矩阵中非零行（列）的个数就是该矩阵的 秩，记为 $r(A)$

    对于矩阵 $A_{ m\times n}$，若 $r(A)=m$ 则称为行满秩矩阵，若 $r(A)=n$ 则称为列满秩矩阵

    可知，删除任意顶点后，该关联矩阵变为满秩。那个删除的顶点称为 参考点，得到的矩阵称为 基本关联矩阵，记作 $M_f(G)$

    有以下推论：

    $\quad G,有\,p\,个连通分支⇒ r(M_f(G))=n-p$

    $\quad G\,连通⇔ r(M(G))=r(M_f(G))=n-1$

  • 对于连通图 $G$，设 $M'_f$ 是 $M(G)$ 中任意 $n-1$ 列（$M(G)$ 本就有 $n-1$ 行）组成的方阵

    $M'_f=\{ e_{ i1} ,e_{ i2} ,\dots,e_{ i(n-1)} \}$ ，导出子图 $T=G[\{ e_{ i1} ,e_{ i2} ,\dots,e_{ i(n-1)} \} ]$

    则 $M'_f\,的行列式\,\mid M'_f\mid \not=0⇔ T\,是\,G\,的生成树$

    有关方阵的行列式

    行列式是由 $n\times n$ 的方阵，所有取自不同行不同列的 $n$ 个元素的不同取法各自乘积的代数和

    $\quad { \sum_{ j_1j_2\dots j_n} \\} (-1)^{ \tau(j_1j_2\dots j_n)} a_{ 1j_1} a_{ 1j_2} \dots a_{ 1j_n}$

    其中 $\tau(j_1j_2\dots j_n)$ 是排列 $j_1j_2\dots j_n$ 的逆序数。逆序数 是从一个排列中任取两个元素，其组合为逆序的取法的数量。如排列 $1423$ 中，逆序组合有 $42、43$，故逆序数为 $2$

    举例来说，对于三阶方阵 $\begin{bmatrix} a_{ 11} &a_{ 12} &a_{ 13} \\a_{ 21} &a_{ 22} &a_{ 23} \\a_{ 31} &a_{ 32} &a_{ 33} \end{bmatrix}$，其取法有六种（$123,132,213,231,312,321$）

    故其行列式为：$a_{ 11} a_{ 22} a_{ 33} -a_{ 11} a_{ 23} a_{ 32} -a_{ 12} a_{ 21} a_{ 33} +a_{ 12} a_{ 23} a_{ 31} +a_{ 13} a_{ 21} a_{ 32} -a_{ 13} a_{ 22} a_{ 31}$

    对于三阶以上的行列式，正常情况只能通过定义来求解

    于是就能用关联矩阵求生成树：

    1. 忽略环，求关联矩阵
    2. 任选参考点，求出基本关联矩阵
    3. 求所有 $n-1$ 阶的子方阵，行列式非零的是生成树

• 有向图邻接矩阵

  设 $D=⟨ V,E⟩$ 是无环有向图，$V=\{ v_1,v_2,\dots,v_n\} ,E=\{ e_1,e_2,\dots,e_m\}$

  邻接矩阵 $A(D)=[a_{ ij} ]_{ n\times n}$ 有 $a_{ ij} =从\,v_i\,到\,v_j\,的边数$

  有向图邻接矩阵有如下性质：

  • 每一行的和为点的出度：$\sum^n_{ j=1} a_{ ij} =d^+(v_i)$

  • 每一列的和为点的入度：$\sum^n_{ i=1} a_{ ij} =d^-(v_j)$

  • 握手定理（矩阵和等于边数）：$\sum^n_{ i=1} \sum^n_{ j=1} a_{ ij} =\sum^n_{ i=1} d^-(v_j)=m$

  • 环的个数为：$\sum^n_{ i=1} a_{ ii}$

  • 若 $A^r=A^{ r-1} • A,\,(r\ge2),\,A^r=[a^r_{ ij} ]_{ n\times n}$，$B^r=A+A^2+\dots+A^r=[b^r_{ ij} ]_{ n\times n}$

    则 $a^r_{ ij}$ 表示从 $v_i$ 到 $v_j$ 的长度为 $r$ 的通路总数

    $\sum^n_{ i=1} \sum^n_{ j=1} a^r_{ ij}$ 即长度为 $r$ 的通路总数，$\sum^n_{ i=1} a^r_{ ii}$ 是长度为 $r$ 的回路总数

    另外 $b^r_{ ij}$ 表示从 $v_i$ 到 $v_j$ 的长度不超过 $r$ 的通路总数

    $\sum^n_{ i=1} \sum^n_{ j=1} b^r_{ ij}$ 即这样的通路总数，$\sum^n_{ i=1} b^r_{ ii}$ 是这样的回路总数

• 有向图可达矩阵

  设 $D=⟨ V,E⟩$ 是有向图 $V=\{ v_1,v_2,\dots,v_n\}$

  则可达矩阵 $P(D)=[p_{ ij} ]_{ n\times n}$ 有 $p_{ ij} =\begin{cases} 1,&从\,v_i\,可达\,v_j\\0,&从\,v_i\,不可达\,v_j\end{cases}$

  可达矩阵的性质：

  • 主对角线都是 $1$
  • 对于强连通图，所有元素都是 $1$
  • 对角块是连通分支的可达矩阵称为伪对角阵
  • $∀ i\not=j,\,p_{ ij} =1⇔ b^{ n-1} _{ ij} >0$

• 无向图相邻矩阵

  设 $G=⟨ V,E⟩$ 是无环无向图，$V=\{ v_1,v_2,\dots,v_n\} ,E=\{ e_1,e_2,\dots,e_m\}$

  相邻矩阵 $A(G)=[a_{ ij} ]_{ n\times n} ,\,a_{ ii} =0$ 有 $a_{ ij} =\begin{cases} 1,&v_i\,与\,v_j\,相邻且\,i\not=j\\0,&v_i\,与\,v_j\,不相邻\end{cases}$

  相邻矩阵的性质：

  • $A(G)$ 对称：$a_{ ij} =a_{ ji}$

  • 每行（列）的和为顶点的度：$\sum^n_{ i=1} a_{ ij} =d(v_j)$

  • 握手定理：$\sum^n_{ i=1} \sum^n_{ j=1} a_{ ij} =\sum^n_{ i=1} d(v_j)=2m$

  • 设 $A^r=A^{ r-1} • A,\,(r\ge2),\,A^r=[a^r_{ ij} ]_{ n\times n}$，$B^r=A+A^2+\dots+A^r=[b^r_{ ij} ]_{ n\times n}$

    则 $a^r_{ ij}$ 是从 $v_i$ 到 $v_j$ 的长度为 $r$ 的通路总数，$\sum^n_{ i=1} a^r_{ ii}$ 即长度为 $r$ 的回路总数

    有 $a^2_{ ii} =d(v_i)$

    两点间的最小距离有：$G\,连通⇒ 距离\,d(v_i,v_j)=\min\{ r\mid a^r_{ ij} \not=0\}$

• 连通矩阵

  设 $G=⟨ V,E⟩$ 是无向简单图，$V=\{ v_1,v_2,\dots,v_n\} ,E=\{ e_1,e_2,\dots,e_m\}$

  连通矩阵 $P(G)=[p_{ ij} ]_{ n\times n}$ 有 $p_{ ij} =\begin{cases} 1,&若\,v_i\,与\,v_j\,连通\\0,&若\,v_i\,与\,v_j\,不连通\end{cases}$

  连通矩阵的性质：

  • 主对角线都是 $1$
  • 连通图的所有元素都是 $1$
  • 对角块是连通分支的连通矩阵称为伪对角阵
  • 若 $B^r=A+A^2+\dots+A^r=[b^r_{ ij} ]_{ n\times n}$，则 $∀ i\not= j,\,p_{ ij} =1⇔ b^{ n-1} _{ ij} >0$

DM3.7 平面图

• 平面图

  边与边不在非顶点处相交（简称不相交）的图称为 平面图。

  可以画在平面上，使得边与边不在非顶点处相交的图称为 可平面图。这样的一种画法称为该图的一个 平面嵌入（平面表示）

  相对的，画在曲面上，使得边与边不相交的画法称为 曲面嵌入；在球面上的画法称为 球面嵌入

  有：$可平面嵌入⇔ 可球面嵌入$。让球面嵌入对平面投影，就能得到一个平面嵌入。

• 面

  在平面图中，不含顶点与边的极大连通曲面 $R$ 称为 区域。面积无限的区域称为 外部区域

  与 $R$ 关联的边和顶点构成的子图称为 区域边界。区域及该区域边界构成 面

  面中区域边界的长度 $\deg(R)$ 称为 面的次数。显然 $\sum^r_{ i=1} \deg(R_i)=2m$

  另外，任何平面嵌入的内部面，都可能成为另一种平面嵌入的外部面。

• 极大平面图、极小非平面图

  添加任意一条边后变成非平面图的平面图称为 极大平面图。$K_5$ 去掉一条边后就是极大平面图

  $n(n\ge 3)$ 阶简单连通平面图是极大平面图的充要条件是：$∀ R,\,\deg(R)=3$

  删除任意一条边后变成平面图的非平面图称为 极小非平面图。$K_5,\,K_{ 3,3}$ 就是极小非平面图

• 欧拉公式

  若 $G$ 是平面图，则 $n-m+r=2$，其中 $r$ 是 $G$ 的面数

  欧拉公式的推广形式：若 $G$ 是平面图，则 $n-m+r=1+p$，其中 $r$ 是 $G$ 的面数，$p$ 是 $G$ 的连通分支数

  于是有以下定理

  • 若 $G$ 是连通平面图 ，且各面次数至少是 $\ell(\ell\ge3)$，则 $m\le\dfrac{ (n-2)\ell} { \ell-2}$

  • 若 $G$ 是有 $p$ 个连通分支的连通平面图 ，各面次数至少是 $\ell(\ell\ge3)$，则 $m\le\dfrac{ (n-p-1)\ell} { \ell-2}$

  • 若 $n(n\ge 3)$ 阶简单平面图 $G$ 有 $m$ 条边，则 $m\le 3n-6$

    若 $G$ 是简单极大平面图，则 $m=3n-6$

  • 若 $G$ 是简单平面图，则 $\delta(G)\le 5$

• 同胚

  插入 $2$ 度顶点：把 $(u,v)$ 变成 $(u,w),\,(w,v)$

  删除 $2$ 度顶点：$\deg(w)=2$，把 $(u,w),\,(w,v)$ 变成 $(u,v)$

  反复删除或插入 $2$ 度顶点后同构，则称两个平面图 同胚

  有如下定理：

  • $图\,G\,是平面图⇔ G\,没有与\,K_5\,或\,K_{ 3,3} \,同胚的子图$
  • $图\,G\,是平面图⇔ G\,没有可以边收缩到\,K_5\,或\,K_{ 3,3} \,的子图$

• 对偶图

  设平面图 $G=⟨ V,E⟩$ ，其面集合是 $R$

  另有 $G^*=⟨ V^*,E^*⟩$，面集合为 $R^*$，若 $V^*$ 与 $R$、$E^*$ 与 $E$ 可以一一对应，则 $G^*$ 与 $G$ 是 对偶图

  对偶图有如下性质：

  • 对偶图必定是连通平面图
  • 环与桥相互对偶
  • 平行边对偶于 2 个面之间的多条边界
  • $n^*=r,\,m^*=m$
  • $r*=n-p+1$
  • $d_{ G^*} (v_i^*)=\deg_G(R_i)$
  • 即使 $G_1\cong G_2$ 也不能得出 $G_1^*\cong G_2^*$
  • $G\,连通⇔ G\cong G^{ **}$

• 外（可）平面图

  若平面图所有的顶点都在一个面的边界上，则称其为 外平面图

  • 充要条件：$G\,是外平面图⇔ G\,不含与\,K_4\,或\,K_{ 2,3} \,同构的子图$

• 极大外平面图

  加入任意边后不是外平面图的简单外平面图称为 极大外平面图

  • 充要条件：

    对于 $n(n\ge3)$ 阶外平面图 $G$，其所有顶点在外部面边界上，则

    $\quad G\,是极大外平面图$
    $⇔G\,外部面边界是\,n-圈、内部面边界是\,3-圈$

  • 必要条件

    对于 $n(n\ge3)$ 阶外平面图 $G$，其所有顶点在外部面边界上，则其具有以下性质

    • $G$ 有 $n-2$ 个内部面
    • $m=2n-3$
    • 至少有 $3$ 个顶点的度数 $\le3$
    • 至少有 $2$ 个顶点的度数 $=2$
    • $\kappa=2$

• 平面哈密顿图

  有如下定理：

  • $4$ 连通平面图是哈密顿图

  • 对于 $n$ 阶简单平面哈密顿图，哈密顿回路内部次数为 $i$ 的面数 $r_i'$，外部为 $r_i''$，则有

    $\quad\sum^n_{ i=3} (i-2)(r_i'-r_i'')=0$

DM3.8 着色

• 点着色

  给无环图的每个顶点指定一种颜色，使得所有相邻顶点拥有不同颜色。

  颜色集记为 $C=\{ 1,2\dots,k\}$，则着色 $f:V→ C,\,∀ u∀ v(u,v\in V∧ u\,与\,v\,相邻→ f(u)\not= f(v))$

  颜色集的大小 $\mid C\mid =k$ 则称为 k-着色

  可以 k-着色 但不能 k-1着色的图称为 k-色图，着色所需的最少颜色数称为 色数

  点色数记为 $\chi(G)$，边色数 $\chi'(G)$，面色数 $\chi^*(G)$

  点色数的性质：

  • $\chi(G)=1⇔ G\,是零图$

  • $\chi(K_n)=n$

  • $\chi(G)=2⇔ G\,是非零图的二部图$

  • $G\,可以\,2\frac{ } { } 着色⇔ G\,是二部图⇔ G\,无奇圈$

  • $\chi(C_n)=\begin{cases} 2,&n\,是偶数\\3,&n\,是奇数\end{cases}$

  • $\chi(W_n)=\begin{cases} 4,&n\,是偶数\\3,&n\,是奇数\end{cases}$

  • $\chi(G)\le\Delta(G)+1$

  • $n(n\ge3)阶非完全图\,G\,非奇圈⇒\chi(G)\le\Delta(G)$

  • 对图 $G$ 进行着色，设 $V_i=\{ v\mid v\in V(G)∧ v\,着同色\,i\} ,\,i=1,2,\dots,\chi(G)$

    则 $\Pi=\{ V_1\,V_2\,\dots\,V_{ \chi(G)} \}$ 是 $V(G)$ 的划分。$V_i$ 中的点构成独立集

    设 $R=\{ (u,v)\mid u,v\in V(G)∧ u,v\,着同色\}$，则 $R$ 是 $V(G)$ 上的等价关系

• 色多项式

  若标定图中至少有一个顶点着色不同，我们认为其是不同的着色

  色多项式 $f(G,k)=图\,G\,的不同的\,k\frac{ } { } 着色的总数$

  对于完全图：$f(K_n,k)=k(k-1)\dots(k-n+1)=f(K_{ n-1} ,k)(k-n+1)$

  对于零图：$f(N_n,k)=k^n$

  色多项式的递推公式：

  • 若 $e$ 是 $G$ 中的边，则 $f(G,k)=f(G-e,k)-f(G\setminus e,k)$

  • 若 $e$ 不是 $G$ 中的边，则 $f(G,k)=f(G\cup e,k)+f(G\setminus e,k)$

    以此法多次递推后，最终能得到一群完全图。故有

    $f(G,k)=f(K_{ n1} ,k)+f(K_{ n2} ,k)+\dots+f(K_{ nr} ,k)$，$\chi(G)=\min(n1,n2,\dots,nr)$

  色多项式的性质：

  • $f(G,k)$ 是 $n$ 次多项式，系数正负号交替

    $k^n$ 系数为 $1$，$k^{ n-1}$ 系数为 $-m$，$m$ 为边数，常数项为 $0$

    最低非零项为 $k^p$，$p$ 是连通分支数。

    不同的连通分支相乘

  • $T\,是\,n\,阶树⇔ f(T,k)=k(k-1)^{ n-1}$

    $C\,是\,n\,阶圈⇒ f(C,k)=(k-1)^n+(-1)*n(k-1)$

  • 设 $V_1$ 是 $G$ 的点割集，且 $G[V_1]$ 是 $G$ 的完全子图 $K_{ \mid V1\mid }$

    若 $G-V_1$ 有 $p$ 个连通分支 $G_1,G_2,\dots,G_p(p\ge2)$，且 $H_i=G[V_1\cup V(G_i)]$

    则 $f(G,k)=\dfrac{ \Pi^p_{ i=1} f(H_i,k)} { f(G[V_1],k)^{ p-1} }$

• 地图

  连通无桥平面图的平面嵌入及其所有的面称为 地图。平面地图的面称为 国家。

  若两个国家的公共边界至少有一条公共边，称两个国家 相邻

  有：$地图\,G\,能\,k\frac{ } { } 面着色⇔ 对偶图\,G^*\,能\,k\frac{ } { } 点着色$

  以及：$连通无环平面图\,G\,能\,k\frac{ } { } 面着色⇔ 对偶图\,G^*\,能\,k\frac{ } { } 点着色$

  五色定理：任何平面图都可以 5-着色

• 边着色

  给无环图的每条边指定一种颜色，使得所有相邻边拥有不同颜色。

  有以下定理：

  • $G\,是简单图⇒ \Delta(G)\le\chi'(G)\le\Delta(G)+1$

  • $G\,是二部图⇒ \Delta(G)=\chi'(G)$

  • 对于完全图：$\chi'(K_n)=\begin{cases} n,&n\,为奇数\\n-1&n\,为偶数\end{cases}$

  • 对图 $G$ 进行 k-边着色，$k\ge\chi'(G)$

    令 $R=\{ (e_i,e_j)\mid e_i\,与\,e_j\,着同色\,i\}$，则 $R$ 是 $V(G)$ 上的等价关系

    商集合 $E/R=\{ E_1,E_2,\dots,E_k\}$ 是 $E$ 的划分，划分块中的元素着同色。同色边构成边独立集

DM3.9 支配集、点覆盖集、点独立集

• 支配集

  对于 $G=⟨ V,E⟩$，存在 $e=(u,v)\in E$，则称 $u$ 支配 $v$（$v$ 支配 $u$）

  若 $V^*\subseteq V$ 有 $∀ u\in V-V^*→ ∃ v\in V^*,\,u\,支配\,v$，则称 $V^*$ 是 支配集

  真子集都非支配集的支配集称为 极小支配集

  顶点数最少的支配集称为 最小支配集。最小支配集的顶点数 $\gamma_0(G)$ 为 支配数

  有如下定理：

  • 若无向图 $G$ 无孤立点，$V^*_1$ 是极小支配集，则存在极小支配集 $V_2^*$，且 $V_1^*\cap V_2^*=Ø$

• 独立集

  对于 $G=⟨ V,E⟩$，若 $V^*\subseteq V,\,∀ u,v\in V^*,\,u\,与\,v\,不相邻$，则称 $V^*$ 是 独立集

  真母集都非独立集的独立集称为 极大独立集

  顶点数最多的独立集称为 最大独立集，最大独立集的顶点数 $\beta_0(G)$ 为 点独立数

  有如下定理：

  • 对于无向图 $G$，$V^*\,是极大独立集⇒ V^*\,是极小支配集$
  • 对于无向图 $G$，$\gamma_0(G)\le \beta_0(G)$

• 团

  对于 $G=⟨ V,E⟩$，若 $V^*\subseteq V$，且 $G[V^*]$ 是完全子图，则称 $V^*$ 是 团

  真母集都不是团的团称为 极大团

  顶点数最多的团称为 最大团，最大团的顶点数 $\nu_0(G)$ 为 团数

  有如下定理：

  • 对于无向图 $G$，$V^*\,是\,G\,的团⇔ V^*\,是\,\overline{ G} \,的独立集$

  • 对于无向图 $G$，$\nu_0(G)=\beta_0(\overline{ G} )$

    $V^*\,是\,G\,的极大(最大)团⇔ V^*\,是\,\overline{ G} \,的极大(最大)独立集$

• 点覆盖

  对于 $G=⟨ V,E⟩$，若 $V^*\subseteq V$，且 $∀ e\in E$，都有 $∃ v\in V^*,\,v\,关联\,e$，则称 $V^*$ 是 点覆盖

  真子集都非点覆盖的点覆盖称为 极小点覆盖

  顶点数最小的点覆盖称为 最小点覆盖，其顶点数 $\alpha_0(G)$ 为 点覆盖数

  有如下定理：

  • 对于无向图 $G$，若其无孤立点，则其点覆盖是支配集。否则，点覆盖加所有孤立点就是支配集

    有 $\gamma_0(G)\le\alpha_0(G)$

  • 对于无向图 $G$，若其无孤立点，则 $V^*\,是点覆盖⇔ V-V^*\,是独立集$

    且 $V^*\,是最小(极小)点覆盖⇔ V-V^*\,是最小(极小)独立集$

    此时 $\alpha_0+\beta_0=n$

  • $\alpha_0,\beta_0,\nu_0,\gamma_0$ 之间的关系：

    • $\alpha_0+\beta_0=n$（无孤立点时）
    • $\gamma_0\le\beta_0$
    • $\gamma_0\le\alpha_0$（无孤立点时）
    • $\nu_0(G)=\beta_0(\overline{ G} )$
    • $\alpha_0,\beta_0,\nu_0$ 都是难解的

DM3.10 边覆盖、匹配

• 边覆盖

  对于 $G=⟨ V,E⟩$，若 $E^*\subseteq E$，且 $∀ v\in V$ 都有 $∃ e\in E,\,e\,关联\,v$，则 $E^*$ 是 边覆盖

  真子集都非边覆盖的边覆盖称为 极小边覆盖

  边数最小的边覆盖称为 最小边覆盖，其边数 $\alpha_1(G)$ 为 边覆盖数

• 匹配

  对于无向图 $G=⟨ V,E⟩$，$E^*\subseteq E$，若 $∀ e,f\in E^*$ 且 $e,f$ 不相邻，则 $E^*$ 是 匹配

  真母集都非匹配的匹配称为 极大匹配

  边数最多的匹配称为 最大匹配，其边数 $\beta_1(G)$ 称为 匹配数

  匹配中关联的顶点称为 饱和点，此外的顶点称为 非饱和点

  没有非饱和点的匹配称为 完美匹配

  有如下定理：

  • $G\,有完美匹配⇔∀ V'\subset V(G),p_奇(G-V')\le\mid V'\mid$

    其中 $p_奇$ 是奇数阶的连通分支数

    （推论）无桥的 3-正则图 有完美匹配

  • 对于无孤立点的无向图 $G$，定有 $\alpha_1+\beta_1=n$

    设 $M$ 是其最大匹配，其所有非饱和点 $v$ 各取一条关联边组成边集 $N$，则 $W=M\cup N$ 是最小边覆盖

    设 $W_1$ 是其最小边覆盖，若 $W_1$ 中有邻边即删除其中一边，直至无邻边。设那些删除的边为 $N_1$，则 $M_1=W_1-N_1$ 为最大匹配

  • 若无向图 $G$ 无孤立点，$M$ 是其匹配，$N$ 是其点覆盖，$Y$ 是独立集，$W$ 是边覆盖，则

    • $\mid M\mid \le\mid W\mid$。若 $\mid M\mid =\mid W\mid$，则 $M$ 是完美匹配，$W$ 是最小边覆盖
    • $\mid M\mid \le\mid N\mid$。若 $\mid M\mid =\mid N\mid$，则 $M$ 是最大匹配，$N$ 是最小点覆盖
    • $\mid Y\mid \le\mid W\mid$。若 $\mid Y\mid =\mid W\mid$，则 $Y$ 是最大独立集，$W$ 是最小边覆盖
    • $\beta_1\le\alpha_0$，$\beta_0\le\alpha_1$

  • $\alpha_0,\beta_0,\nu_0,\gamma_0,\alpha_1,\beta_1$ 之间的关系：

    • $\gamma_0\le\alpha_0\quad\gamma_0\le\beta_0\quad n=\alpha_0+\beta_0$
    • $\nu_0(\overline{ G} )=\beta_0(G)\le\alpha_1\quad\alpha_1+\beta_1=n$
    • $\beta_1\le\alpha_1\quad \beta_1\le\alpha_0$
    • $\alpha_1,\beta_1$ 是容易计算的

• 交错路径

  在匹配中和匹配外交替选取边的路径称为 交错路径

  两个端点都是非饱和点的交错路径称为 可增广（交错）路径

  有如下定理：

  • 设 $M_1,M_2$ 是 $G$ 中的不同匹配，则 $G[M_1\oplus M_2]$ 的每个连通分支是 $M_1,M_2$ 中的边组成的交错圈或交错路径

  • 设 $M$ 是 $G$ 中的匹配，$\Gamma$ 是 $M$ 的可增广路径，则 $M'=M\oplus E(\Gamma)$ 也是匹配，且 $\mid M'\mid =\mid M\mid +1$

    这个定理可以求出最大匹配

    $M\,是\,G\,中的最大匹配⇔ G\,中无\,M\,的可增广路径$

• 二部图的匹配

  对于二部图 $G=⟨ V_1,V_2,E⟩,\,\mid V_1\mid \le\mid V_2\mid$，若匹配 $M$ 有 $\mid M\mid =\mid V_1\mid$ 则称其为 完备匹配

  有如下定理：

  • $二部图\,G\,有完美匹配⇔ G\,满足霍尔条件$

    霍尔条件（相异性条件）：$∀ S\subseteq V_1,\,\mid S\mid \le\mid N(S)\mid$。$N(S)=\{ u\mid ∃ v\in S,(v,u)\in E\} =\bigcup_{ v\in S} \Gamma(v)$

    换句话说，对于较少顶点侧的任意点集，其对应的另一侧点集大小不少于该点集大小

  • $二部图\,G\,有完美匹配⇒ G\,满足\,t\frac{ } { } 条件$

    t-条件：二部图 $G=⟨ V_1,V_2,E⟩,\,t\ge1$。$V_1$ 的每个顶点至少关联 t 条边，且 $V_2$ 的每个顶点至多关联 t 条边

  • k-正则二部图存在 k 个边不重的完备匹配

  • 二部图 $G=⟨ V_1,V_2,E⟩$ 无孤立点，则 $\alpha_0=\beta_1$

DM3.11 带权图

• 带权图

  对于图 $G=⟨ V,E,W⟩,\,W:E→ R$。其中 $W(e)$ 称为图的 权

• 有效算法

  复杂度是多项式函数的算法称为 有效算法

  如 O(n)、O(n³)、O(n㏒n) 等复杂度都是有效算法。O(2ⁿ) 等不是有效算法

  有多项式复杂度算法的问题称为 易解问题，否则称为 难解问题

• 中国邮递员问题

  对于一个带权图，求经过所有边的最短回路

  中国邮递员问题是一个易解问题。方法如下：

  1. 求该带权图 $G$ 的所有奇数度顶点间的短程线。这些顶点和短程线构成带权完全图 $K$
  2. 求出 $K$ 的最小完美匹配 $M$
  3. 用 $M$ 给 $G$ 沿短程线加边得到 $G^*$，$G^*$ 的欧拉回路 $\Gamma$ 就是答案

• 货郎问题

  对于一个带权图，求经过所有顶点的最短回路

  货郎问题是一个难解问题