331 lines
16 KiB
TeX
331 lines
16 KiB
TeX
\chapter{图论}
|
||
\section{图}
|
||
\subsection{图的概念}
|
||
\begin{example}\label{图论引导问题}
|
||
证明：在奇数个人参加的聚会中，一定有人认识偶数个人。
|
||
\end{example}
|
||
|
||
\begin{wrapfigure}{r}{5cm}
|
||
\begin{center}
|
||
\begin{tikzpicture}
|
||
\draw node[circle, draw=black, minimum height=25pt] (v) at (18:2) {$v$};
|
||
\draw node[circle, draw=black, minimum height=25pt] (u) at (90:2) {$u$};
|
||
\draw node[circle, draw=black, minimum height=25pt] (y) at (162:2) {$y$};
|
||
\draw node[circle, draw=black, minimum height=25pt] (x) at (234:2) {$x$};
|
||
\draw node[circle, draw=black, minimum height=25pt] (w) at (306:2) {$w$};
|
||
\draw (u)--(y);
|
||
\draw (u)--(x);
|
||
\draw (u)--(w);
|
||
\draw (u)--(v);
|
||
\draw (y)--(w);
|
||
\draw (v)--(w);
|
||
\end{tikzpicture}
|
||
\end{center}
|
||
\caption{一个5阶图}
|
||
\label{图概念例子}
|
||
\end{wrapfigure}
|
||
|
||
为了解决这个问题，我们引入\newnoun{图}{graph}的概念。
|
||
\begin{definition}
|
||
如右是一张\newnoun{图}{graph}。也记为$G = \{V,E\}$，其中$V$代表图中顶点的集合，$E$代表图中边的集合。
|
||
|
||
其中$u, v, w, x, y$称为\newnoun{顶点}{vertex}，连接两个点的线段称为\newnoun{边}{edge}，它是一个包含了起点和终点的二元集合，如$\{u, v\}$，也简记为$uv$。
|
||
|
||
若$uv$存在，则称$u,v$相邻，$u,v$互为邻点。图中某点$v$的所有邻点组成的集合称为它的\newnoun{临域}{neighborhood}，记作$N_G(v)$。例如，右图中$N_G(v) = \{u,w\}$。
|
||
|
||
与某点$v$相关联的边的数量称为$v$的\newnoun{度}{degree}，记作$d(v)$。例如，右图中$d(v)=2$，$d(u)=4$。
|
||
|
||
一张图的顶点数称为它的阶数。
|
||
\end{definition}
|
||
|
||
有了这些概念，我们就能将例\ref{图论引导问题}中的问题简化为：奇数阶图必有一度为偶数的点。进一步我们可以把它扩展为：奇数阶图必有奇数个度为偶数的点。类似地我们应还有：偶数阶图有偶数个度为偶数的点。
|
||
|
||
将这些命题合并起来有
|
||
\begin{theorem}\label{偶数奇度点}
|
||
在任意图中，必有偶数个度为奇数的点。
|
||
\end{theorem}
|
||
|
||
要想证明这个定理，我们首先需要一个更基本的定理：
|
||
\begin{theorem}[握手定理]
|
||
任意图中所有点的度的和为图中边数的两倍，即
|
||
\[\sum_{v \in V} d(v) = 2 \lvert E \rvert\eqper\]
|
||
\end{theorem}
|
||
|
||
\begin{proof}
|
||
令
|
||
\begin{equation*}
|
||
a_{v,e}
|
||
\begin{cases}
|
||
1,\ v \in e\\
|
||
0,\ v \notin e
|
||
\end{cases}
|
||
\text{在这里，$v$是一个顶点，$e$是一条边。}
|
||
\end{equation*}
|
||
那么
|
||
\begin{align*}
|
||
\sum_{v\in V} d(v) & = \sum_{v \in V}\sum_{e \in E} a_{v,e}\\
|
||
& = \sum_{e \in E}\sum_{v \in V} a_{v,e}\\
|
||
& = 2\lvert E \rvert \eqper\qedhere
|
||
\end{align*}
|
||
\end{proof}
|
||
|
||
$\left[a_{v,e}\right]_{\lvert V \rvert \times \lvert E \rvert}$称为图的关联矩阵。例如，图\ref{图概念例子}的关联矩阵是
|
||
\[\begin{bNiceMatrix}[first-row,first-col]
|
||
& e_1 & e_2 & e_3 & e_4 & e_5 & e_6 \\
|
||
u & 1 & 1 & 1 & 1 & 0 & 0 \\
|
||
v & 1 & 0 & 0 & 0 & 1 & 0 \\
|
||
w & 0 & 1 & 0 & 0 & 1 & 1 \\
|
||
x & 0 & 0 & 1 & 0 & 0 & 0 \\
|
||
y & 0 & 0 & 0 & 1 & 0 & 1 \\
|
||
\end{bNiceMatrix}\]
|
||
|
||
由此我们可以证明定理\ref{偶数奇度点}。
|
||
\begin{proof}
|
||
已知
|
||
\[\sum_{v \in V} d(v) = 2 \lvert E \rvert\]
|
||
那么令
|
||
\begin{align*}
|
||
V_o & := \{v \in V \mid d(v)\text{为奇数}\}\\
|
||
V_e & := \{v \in V \mid d(v)\text{为偶数}\}
|
||
\end{align*}
|
||
那么有
|
||
\begin{align*}
|
||
\sum_{v \in V_o}d(v) + \sum_{v \in V_e} d(v) & = 2 \lvert E \rvert\\
|
||
\sum_{v \in V_o}d(v) & = 2 \lvert E \rvert - \sum_{v \in V_e}d(v)
|
||
\end{align*}
|
||
因此$\sum \limits_{v \in V_o}d(v)$为偶数，因此$\lvert V_o \rvert$为偶数。
|
||
\end{proof}
|
||
|
||
\subsection{特殊的图}
|
||
\begin{enumerate}
|
||
\item \newnoun{简单图}{simple graph}：不含重边和环的图称为简单图；
|
||
\item \newnoun{多重图}{multigraph}：含有重边的图称为多重图；
|
||
\item \newnoun{无边图}{edgeless graph}：只有顶点而无边的图；
|
||
\item \newnoun{完全图（团）}{complete graph or clique}：在一个简单图中，若每一对顶点间均有边相连，则称该图为完全图。有$n$个顶点的完全图记为$K_n$；
|
||
\item \newnoun{星}{star}：一个点连接另外所有$n-1$个点的图，记为$S_n$；
|
||
\item \newnoun{正则图}{regular graph}：所有顶点的度相同的图；
|
||
\item 相对于完全图的\newnoun{补图}{complement}：给定一个简单图$G$，由$G$中所有顶点和所有非边组成的图，称为$G$的相对于完全图的补图，或简称为$G$的补图，记为$\setcom{G}$或$\overline{G}$。即对$G = (V,E_1)$，$\setcom{G} = (V, E_2)$，其中$E_2 = \{uv \mid u, v \in V,\ uv \notin E_1\}$。
|
||
|
||
\begin{figure}[H]
|
||
\centering
|
||
\subfloat[完全图$K_5$]{
|
||
\begin{tikzpicture}[scale=0.8]
|
||
\draw node[circle, draw=black, minimum height=23pt] (v) at (18:2) {$v$};
|
||
\draw node[circle, draw=black, minimum height=23pt] (u) at (90:2) {$u$};
|
||
\draw node[circle, draw=black, minimum height=23pt] (y) at (162:2) {$y$};
|
||
\draw node[circle, draw=black, minimum height=23pt] (x) at (234:2) {$x$};
|
||
\draw node[circle, draw=black, minimum height=23pt] (w) at (306:2) {$w$};
|
||
\draw (u)--(y);
|
||
\draw (u)--(x);
|
||
\draw (u)--(w);
|
||
\draw (u)--(v);
|
||
\draw (y)--(w);
|
||
\draw (y)--(x);
|
||
\draw (y)--(v);
|
||
\draw (x)--(w);
|
||
\draw (x)--(v);
|
||
\draw (w)--(v);
|
||
\end{tikzpicture}
|
||
}
|
||
\hspace{1cm}
|
||
\subfloat[图$G$]{
|
||
\begin{tikzpicture}[scale=0.8]
|
||
\draw node[circle, draw=black, minimum height=23pt] (v) at (18:2) {$v$};
|
||
\draw node[circle, draw=black, minimum height=23pt] (u) at (90:2) {$u$};
|
||
\draw node[circle, draw=black, minimum height=23pt] (y) at (162:2) {$y$};
|
||
\draw node[circle, draw=black, minimum height=23pt] (x) at (234:2) {$x$};
|
||
\draw node[circle, draw=black, minimum height=23pt] (w) at (306:2) {$w$};
|
||
% \draw (u)--(y);
|
||
\draw (u)--(x);
|
||
\draw (u)--(w);
|
||
\draw (u)--(v);
|
||
% \draw (y)--(w);
|
||
% \draw (y)--(x);
|
||
\draw (y)--(v);
|
||
% \draw (x)--(w);
|
||
\draw (x)--(v);
|
||
\draw (w)--(v);
|
||
\end{tikzpicture}
|
||
}
|
||
\hspace{1cm}
|
||
\subfloat[图$G$的补图$\setcom{G}$]{
|
||
\begin{tikzpicture}[scale=0.8]
|
||
\draw node[circle, draw=black, minimum height=23pt] (v) at (18:2) {$v$};
|
||
\draw node[circle, draw=black, minimum height=23pt] (u) at (90:2) {$u$};
|
||
\draw node[circle, draw=black, minimum height=23pt] (y) at (162:2) {$y$};
|
||
\draw node[circle, draw=black, minimum height=23pt] (x) at (234:2) {$x$};
|
||
\draw node[circle, draw=black, minimum height=23pt] (w) at (306:2) {$w$};
|
||
\draw (u)--(y);
|
||
% \draw (u)--(x);
|
||
% \draw (u)--(w);
|
||
% \draw (u)--(v);
|
||
\draw (y)--(w);
|
||
\draw (y)--(x);
|
||
% \draw (y)--(v);
|
||
\draw (x)--(w);
|
||
% \draw (x)--(v);
|
||
% \draw (w)--(v);
|
||
\end{tikzpicture}
|
||
}
|
||
\end{figure}
|
||
\item \newnoun{子图}{subgraphs}设图$G = (V,E)$，如果有图$G^\prime = (V^\prime, E^\prime)$，且$V^\prime \subseteq V$，$E^\prime \subseteq E$，则称$G^\prime$为$G$的子图，记$G^\prime \subseteq G$。当$V^\prime = V$时，则称$G^\prime$为$G$的\newnoun{生成子图}{spanning subgraph}。
|
||
\end{enumerate}
|
||
|
||
\section{路、圈与连通性}
|
||
\subsection{路}
|
||
\begin{definition}
|
||
给定图$G = (V,E)$，设$v_0, v_1, \dots, v_n \in N$，$e_1, e_2, \dots, e_n \in E$，其中$e_i$是关联于顶点$v_{i-1},v_i$的边，那么交替序列$v_0 e_1 v_1 e_2 \dots e_n v_n$称为顶点$v_0$到$v_n$的\newnoun{途}{walk}。$v_0$和$v_n$分别称为途的起点和终点，边的数目$n$称为途的长度。
|
||
|
||
当$v_0 = v_n$时，这条途称作\newnoun{闭途}{closed walk}或回路。
|
||
|
||
若一条途中的所有的边$e_1, \dots, e_n$均不相同，则称为一条\newnoun{迹}{trail}。
|
||
|
||
若一条途中所有的顶点$v_0, v_1, \dots, v_n$均不相同，则称为一条\newnoun{路}{path}。
|
||
|
||
闭的路，即除$v_0 = v_n$之外，其余顶点均不相同的路，称作\newnoun{圈}{cycle}。
|
||
\end{definition}
|
||
|
||
即，途允许重复路过多个点、也允许重复经过同一边；迹允许重复通过同一个点，但不允许重复通过同一边（若两点间有多个边，可以每个边都走一次）；路则既不允许重复通过同一个点，也不允许重复通过同一个边。
|
||
|
||
\subsection{连通性}
|
||
\begin{definition}
|
||
在图$G$中，如果从顶点$u$到顶点$v$之间存在一条路，则称顶点$u$和顶点$v$是\newnoun{连通的}{connected}。
|
||
|
||
顶点之间的连通性是顶点集$V$上的定价关系。对应该等价关系，必可将$V$做出一个划分，即把$V$分成非空子集$V_1, V_2, \dots V_m$，使得两个顶点$u$和$v$是连通的当且仅当它们属于同一个$V_i$。把子图$G[V_1], G[V_2], \dots, G[V_m]$称为图$G$的\newnoun{连通分支}{connected components}。$m$为分支数，记为$c(G)$。
|
||
\end{definition}
|
||
|
||
\section{欧拉迹与哈密顿圈}
|
||
\subsection{欧拉回路}
|
||
\begin{definition}
|
||
如果无孤立顶点图$G$上有一条经过$G$的所有边一次且仅一次的迹，则称该迹为图$G$的\newnoun{Euler迹}{Eulerian walk}。
|
||
|
||
如果图$G$上有一条经过$G$的所有边一次且仅一次的回路，则称改回路为图$G$的Euler回路。
|
||
|
||
具有Euler回路的图称为Eulerian graph。
|
||
\end{definition}
|
||
|
||
\begin{theorem}
|
||
图$G$有一条Euler迹等价于图$G$连通并且有零个或两个奇数度的顶点。
|
||
\end{theorem}
|
||
|
||
\begin{corollary}
|
||
图$G$是Euler图等价于图$G$连通且所有顶点的度数皆为偶数。
|
||
\end{corollary}
|
||
|
||
\begin{proof}
|
||
先证必要性：已知$G$有Euler迹，证明$G$连通且有零个或者两个奇数度的顶点。
|
||
|
||
设$G$的Euler迹是点边序列$v_0 e_1 v_1 e_2 \dots e_k v_k$，其中的顶点可能重复但是边不重复。因为Euler迹经过了所有边，因此它一定经过了所有顶点，从而图$G$是连通的。
|
||
|
||
对于任意一个非端点的$v_i$，在Euler迹中每当$v_i$出现一次，必关联两条边（``有进必有出''），因此不论$v_i$重复出现多少次，$d(v_i)$一定是偶数。
|
||
|
||
对于一个端点，若$v_0 = v_k$，则$d(v_0)$一定是偶数，即$G$中无奇数度的顶点。
|
||
|
||
若$v_0 \neq v_k$，那么$d(v_0), d(v_k)$均为奇数，即$G$中有两个奇数项点。
|
||
|
||
再证必要性：已知$G$连通且有零个或者两个奇数度的顶点，证明$G$有Euler迹。直接找出一条欧拉迹（Hierholzer's Algorithm）。
|
||
\begin{enumerate}[label=(\arabic{*})]
|
||
\item 若有两个奇数度的顶点，则从其中一个顶点开始构造一条迹，即从$v_0$出发经关联边$e_1$进入$v_1$，若$d(v_1)$为偶数，则必可由$v_1$再经关联边$e_2$进入$v_2$，如此下去，保证每个边最多只被取一次，由于$G$是连通的，因此必可到达另一奇数度顶点停下，得到一条迹$L_1$：$v_0 e_1 v_1 e_2 \dots e_k v_k$。
|
||
|
||
若$G$中没有奇数度的顶点，则从任一顶点$v_0$出发，用上述方法一定可以回到顶点$v_0$，得到一条闭迹。
|
||
\item 若$L_1$通过了$G$的所有边，则$L_1$就是一条Euler迹。
|
||
\item 否则$G$中去掉$L_1$的边后得到的子图$G^\prime$中每个顶点的度都为偶数，因为原来的图$G$是连通的，故$L_1$与$G^\prime$至少有一个顶点$v_i$重合，在$G^\prime$中以$v_i$为起点和终点重复（1）中的方法，得到闭迹$L_2$。
|
||
\item 将$L_1$与$L_2$组合，若恰好为$G$，则找到了Euler迹；否则重复（3），可得到闭迹$L_3$，依此类推可以得到一条欧拉迹。\qedhere
|
||
\end{enumerate}
|
||
\end{proof}
|
||
|
||
\subsection{哈密顿圈}
|
||
\begin{example}
|
||
能否在正十二面体中找到一个回路，使它包含所有顶点一次且仅一次？
|
||
\end{example}
|
||
|
||
\begin{proof}[解]
|
||
哈密顿给出的解法：
|
||
\begin{figure}[H]
|
||
\centering
|
||
\begin{tikzpicture}
|
||
\draw[line width=1.5pt, color=red] (54:1)--(126:1)--(198:1)--(270:1)--(342:1);
|
||
\draw (342:1)--(54:1);
|
||
|
||
\draw[line width=1.5pt, color=red] (54:1)--(54:1.5);
|
||
\draw (126:1)--(126:1.5);
|
||
\draw (198:1)--(198:1.5);
|
||
\draw (270:1)--(270:1.5);
|
||
\draw[line width=1.5pt, color=red] (342:1)--(342:1.5);
|
||
|
||
\filldraw (54:1) circle (.1);
|
||
\filldraw (126:1) circle (.1);
|
||
\filldraw (198:1) circle (.1);
|
||
\filldraw (270:1) circle (.1);
|
||
\filldraw (342:1) circle (.1);
|
||
|
||
\draw (54:1.5)--(90:2);
|
||
\draw[line width=1.5pt, color=red] (90:2)--(126:1.5)--(162:2)--(198:1.5)--(234:2)--(270:1.5)--(306:2)--(342:1.5);
|
||
\draw (342:1.5)--(18:2);
|
||
\draw[line width=1.5pt, color=red] (18:2)--(54:1.5);
|
||
|
||
\filldraw (54:1.5) circle (.1);
|
||
\filldraw (126:1.5) circle (.1);
|
||
\filldraw (198:1.5) circle (.1);
|
||
\filldraw (270:1.5) circle (.1);
|
||
\filldraw (342:1.5) circle (.1);
|
||
|
||
\draw[line width=1.5pt, color=red] (18:2)--(18:3);
|
||
\draw[line width=1.5pt, color=red] (90:2)--(90:3);
|
||
\draw (162:2)--(162:3);
|
||
\draw (234:2)--(234:3);
|
||
\draw (306:2)--(306:3);
|
||
|
||
\filldraw (18:2) circle (.1);
|
||
\filldraw (90:2) circle (.1);
|
||
\filldraw (162:2) circle (.1);
|
||
\filldraw (234:2) circle (.1);
|
||
\filldraw (306:2) circle (.1);
|
||
|
||
\draw[line width=1.5pt, color=red] (90:3)--(162:3)--(234:3)--(306:3)--(18:3);
|
||
\draw (18:3)--(90:3);
|
||
|
||
\filldraw (18:3) circle (.1);
|
||
\filldraw (90:3) circle (.1);
|
||
\filldraw (162:3) circle (.1);
|
||
\filldraw (234:3) circle (.1);
|
||
\filldraw (306:3) circle (.1);
|
||
\end{tikzpicture}
|
||
\end{figure}
|
||
\end{proof}
|
||
|
||
\begin{definition}
|
||
给定图$G$，若存在一条经过图中的每个顶点恰好一次的路，这条路被称作Hamilton路。若存在一个圈经过图中的所有顶点，这个圈称作Hamilton圈。具有Hamilton圈的图称作Hamilton图。
|
||
\end{definition}
|
||
|
||
\begin{theorem}
|
||
若图$G = (V,E)$具有Hamilton圈，则对于顶点集$V$的每个非空子集$S$均有
|
||
\[c(G-S) \leq \lvert S \rvert\eqper\]
|
||
\end{theorem}
|
||
|
||
\begin{proof}
|
||
设$C$使$G$的一个Hamilton圈，对于$V$的任一非空子集$S$，$C$经过了$G$的所有顶点，$C$与$G$的顶点集合相同，$C-S$是$G-S$的生成子图，因此$c(G-S) \leq c(C-S)$；
|
||
再考虑$c(C-S)$与$\lvert S \rvert$的关系。可以将$C$画成下图样式：
|
||
\begin{figure}[H]
|
||
\begin{center}
|
||
\begin{tikzpicture}
|
||
\filldraw (-36:2) circle (.1);
|
||
\filldraw (0:2) circle (.1);
|
||
\filldraw (36:2) circle (.1);
|
||
\filldraw (72:2) circle (.1);
|
||
\filldraw (108:2) circle (.1);
|
||
\filldraw (144:2) circle (.1);
|
||
\filldraw (180:2) circle (.1);
|
||
\filldraw (216:2) circle (.1);
|
||
\draw (-80:2) arc (-80:260:2);
|
||
\node at(270:2) {$\dots$};
|
||
\end{tikzpicture}
|
||
\end{center}
|
||
\end{figure}
|
||
可见减去1个点最多有1个连通分支、减去2个点最多有2个连通分支……由此可得
|
||
\[c(C-S) \leq \lvert S \rvert\]
|
||
因此
|
||
\[c(G-S) \leq c(C-s) \leq \lvert S \rvert \eqper\qedhere\]
|
||
\end{proof}
|
||
|