192 lines
11 KiB
TeX
192 lines
11 KiB
TeX
\documentclass[全部作业]{subfiles}
|
||
|
||
\pagestyle{fancyplain}
|
||
\fancyhead{}
|
||
\fancyhead[C]{\mysignature}
|
||
\setcounter{chapter}{7}
|
||
\setcounter{section}{2}
|
||
|
||
\begin{document}
|
||
\section{图的连通性}
|
||
\begin{enumerate}
|
||
\item 设简单无向图$G=(V,E)$，若$\delta (G)\geqslant k (k\geqslant 1)$。请证明：$G$有长度为$k$的基本通路。
|
||
\begin{proof}
|
||
\begin{zhongwen}
|
||
|
||
使用数学归纳法，
|
||
|
||
由于$\delta (G)\geqslant k\geqslant 1$，所以$G$中存在边，从而$G$不是零图，因此必定有长度为1的基本通路。
|
||
|
||
假设$G$中存在长度为$m-1$的基本通路$\alpha $ $(m\leqslant k)$，则$\alpha $中的顶点总数为$m$（基本通路的顶点互不相同）。那么对于$\alpha $两端的其中一个端点$v$，$\alpha $去除$v$后的顶点总数为$m-1$。由于$d(v)\geqslant \delta (G)\geqslant k\geqslant m>m-1$，即$v$的度数大于$\alpha $中去除$v$后的顶点总数，所以与$v$相连的边中必定存在一条边$e$连接了不在$\alpha $中的顶点$v'$，于是将边$e$和顶点$v'$加入到$\alpha $中，就构成了长度为$m$的基本通路。
|
||
|
||
所以$\forall m \in \mathbb{N}, 1\leqslant m\leqslant k$，$G$有长度为$m$的基本通路。自然地，$G$有长度为$k$的基本通路。
|
||
|
||
\end{zhongwen}
|
||
\end{proof}
|
||
|
||
\item 证明：若无向图$G$没有长度为奇数的基本回路，则$G$没有任何长度为奇数的回路。
|
||
|
||
\begin{proof}
|
||
\begin{zhongwen}
|
||
|
||
证明原命题的逆否命题“若$G$中存在一条长度为奇数的回路，则$G$中必定存在长度为奇数的基本回路。”
|
||
|
||
若$G$中存在一条长度为奇数的回路$\alpha $，则可以设$\alpha =v_0e_1v_1e_2\cdots e_k v_k$，$\alpha $的长度$k$为奇数。若$\alpha $是基本回路，则$G$中存在长度为奇数的基本回路。
|
||
|
||
若$\alpha $不是基本回路，则其中存在相同的顶点，不妨设$v_i=v_j$, $0\leqslant i<j\leqslant k$，于是$\alpha $的子序列$v_i e_{i+1} v_{i+1} e_{i+2}\cdots e_j v_j$构成一个回路，记为$\alpha '$，并且从$\alpha $中删除$\alpha '$后（保留顶点$v_i$）仍然是一个回路，记为$\alpha ''$，并且$\alpha '$和$\alpha ''$的长度之和为原始回路$\alpha $的长度$k$。因为$k$为正奇数，所以将其拆分成两个正整数之和后其中必定有一个正整数为奇数，即$\alpha '$和$\alpha ''$中必定有一个长度为奇数。取这个长度为奇数的回路，记为$\alpha_1$，则可以对$\alpha_1$重复上述拆分回路的过程，得到长度为奇数的回路$\alpha_2, \cdots \cdots$。注意到$\alpha $的有限性，上述拆分回路的过程不可能无限进行，最后一次拆分过程结束后，所得到的回路就是长度为奇数的基本回路。
|
||
|
||
总之，$G$中必定存在长度为奇数的基本回路。
|
||
|
||
\end{zhongwen}
|
||
\end{proof}
|
||
|
||
\item 证明：在任何无向图中，任何奇数度的顶点都有通路到某个其他的奇数度顶点。
|
||
|
||
\begin{proof}
|
||
\begin{zhongwen}
|
||
|
||
对于任何一个无向图$G$，在其中任取一个奇数度的顶点$v$，使用反证法。
|
||
|
||
假设对于所有以$v$为一端的通路，通路的另一端的顶点都是偶数度的，那么将$v$与这些顶点以及与它们相连的边全部取出，即构成$G$的一个连通分量$G'$。在$G'$中，只有$v$是奇数度的，其它所有顶点都是偶数度的，那么$G'$的度数之和为奇数，不满足握手定理，因此这种情况不可能发生。
|
||
|
||
所以$v$必定有通路到某个其他的奇数度顶点。
|
||
|
||
\end{zhongwen}
|
||
\end{proof}
|
||
|
||
\item 分别求出下列三个无向图的各个连通分量。
|
||
\begin{center}
|
||
\includegraphics[width=0.8\linewidth]{imgs/2023-12-24-08-27-46.png}
|
||
\end{center}
|
||
|
||
\begin{proof}[解]
|
||
|
||
\begin{center}
|
||
\includexopp[0.7]{7.3.4}
|
||
\end{center}
|
||
\end{proof}
|
||
|
||
\end{enumerate}
|
||
|
||
\section{最短通路和Dijkstra算法}
|
||
\section{图着色}
|
||
\begin{enumerate}
|
||
\item 无向图的色数为1意味着什么？
|
||
|
||
\begin{zhongwen}
|
||
图中不存在边。
|
||
\end{zhongwen}
|
||
|
||
\item 一大学有5个专业委员会：物理、化学、数学、生物、计算机，6位院士：B、C、D、G、S、W。专业委员会由院士组成，物理委员会有院士：C、S和W，化学委员会有院士：C、D和W；数学委员会有院士：B、C、G和S；生物委员会有院士：B和G；计算机委员会有院士：D和G。每个专业委员会每周开一小时例会，所有成员都不能缺席。如果某院士同时是两个专业委员会的成员，那么这两个专业委员会的例会就不能安排在同一个时间。现要为这些例会安排时间，希望它们的时间尽可能集中。问最少需要几个开会时间？请给出一种安排。
|
||
|
||
\begin{proof}[解]
|
||
\begin{zhongwen}
|
||
|
||
首先将专业委员会和院士的关系整理成如下表格：
|
||
|
||
\begin{center}
|
||
\begin{tabular}{cc} % tabular里用\centering会导致一直在编译停不下来
|
||
\toprule
|
||
专业委员会 & 院士\\
|
||
\midrule
|
||
物理&C、S、W\\
|
||
化学&C、D、W\\
|
||
数学&B、C、G、S\\
|
||
生物&B、G\\
|
||
计算机&D、G\\
|
||
\bottomrule
|
||
\end{tabular}
|
||
\end{center}
|
||
|
||
之后根据“如果某院士同时是两个专业委员会的成员，那么这两个专业委员会的例会就不能安排在同一个时间”构造图，将专业委员会作为顶点，如果这两个专业委员会有相同的院士，那么就在这两个顶点之间连一条边，问题即可转化为图着色问题。于是构造出下方左图：
|
||
|
||
\begin{center}
|
||
\includesvgpdf[0.45]{7.5.2.drawio}
|
||
\hfill
|
||
\includesvgpdf[0.45]{7.5.2-colour.drawio}
|
||
\end{center}
|
||
|
||
设此图为$G$，由于存在$C_3$的结构，因此$\chi (G)\geqslant 3$，又因为此图不是完全图也不是奇圈，所以根据Brooks定理，$\chi (G)\leqslant \Delta (G)=4$。
|
||
|
||
那么尝试找到色数为3的着色方案，即上方右图。
|
||
|
||
因此最少需要3个开会时间，即物理和计算机同一时间开会，化学和生物同一时间开会，数学单独时间开会。
|
||
|
||
\end{zhongwen}
|
||
\end{proof}
|
||
\end{enumerate}
|
||
\pagebreak[1]
|
||
|
||
\section{图的同构}
|
||
\begin{enumerate}
|
||
\item 有3个顶点的不同构的简单无向图有多少个？
|
||
|
||
\begin{zhongwen}
|
||
3个。（分别为一条边、两条边、三条边的情况）
|
||
\end{zhongwen}
|
||
|
||
\item 证明：若无向图G不是连通图，则其补图必为连通图。
|
||
|
||
\begin{proof}
|
||
\begin{zhongwen}
|
||
|
||
设$G$的补图为$G'$，下证$G'$是连通图。
|
||
|
||
在$G'$中任取两个顶点，若这两个顶点在$G$中不相邻，那么根据补图的定义，它们在$G'$中必定相邻，从而是连通的。
|
||
|
||
若这两个顶点（设为$v_1,v_2$）在$G$中相邻，即它们在$G$中是连通的，而$G$不是连通图，所以必定存在另一个顶点$v_3$，使得$v_1$与$v_3$不连通，$v_2$与$v_3$不连通，从而$v_1$与$v_3$不相邻，$v_2$与$v_3$不相邻。那么根据补图的定义，在$G'$中$v_1$与$v_3$相邻，$v_2$与$v_3$相邻，所以$v_1$与$v_2$在$G'$中连通。
|
||
|
||
所以在$G'$中任取两个顶点，它们都是连通的，因此$G'$是连通图。
|
||
|
||
\end{zhongwen}
|
||
\end{proof}
|
||
\end{enumerate}
|
||
|
||
\chapter{具有特殊性质的图}
|
||
\section{欧拉图}
|
||
\begin{enumerate}
|
||
\item 一房子的平面图如图。问能否从前门进去，最后从后门出去，走过所有的门且每扇门只经过一次？
|
||
\begin{center}
|
||
\includegraphics[width=0.3\linewidth]{imgs/2023-12-24-10-01-59.png}
|
||
\end{center}
|
||
|
||
\begin{proof}[解]
|
||
\begin{zhongwen}
|
||
|
||
将每个房间作为一个顶点，如果两个房间之间有门，则在这两个房间之间连一条边，同时将前门外的空间也作为一个顶点，后门外的空间也作为一个顶点，则可以构造出图如下：
|
||
|
||
\begin{center}
|
||
\includexopp[0.8]{8.1.1}
|
||
\end{center}
|
||
|
||
对于该图，只有前门外的顶点和后门外的顶点度数为1，是奇数，其它顶点的度数都是偶数，因此存在从前门外顶点到后门外顶点的欧拉通路，因为门与图中的边对应，所以能从前门进去，最后从后门出去，走过所有的门且每扇门只经过一次。
|
||
|
||
\end{zhongwen}
|
||
\end{proof}
|
||
|
||
\item 对于有16个扇区和4个探测器的磁鼓，给出一种合理的0-1赋值。
|
||
|
||
\begin{zhongwen}
|
||
% 虽然可以借助欧拉图来做，但是比较复杂，这里使用一个比较简便的方法。
|
||
\begin{proof}[解]
|
||
|
||
% 首先，4个探测器探测出的0-1序列最多有$2^{4}=16$种情况，也即4位二进制串的数量。要区分16个扇区，则必定这16种情况要和16个扇区一一对应，也即每个4位二进制串都对应了一个扇区。因此必定有一个扇区与1111对应，也有一个扇区与0000对应，好吧这样还是很麻烦，还是用欧拉图来做吧。
|
||
|
||
以所有的3位二进制串为顶点，对于两个二进制串，如果前一个二进制串的后2位等于后一个二进制串的前2位，则从前一个二进制串到后一个二进制串连一条有向边。可以构造出图如下：
|
||
|
||
\begin{center}
|
||
\includesvgpdf[0.5]{8.1.2.drawio}
|
||
\end{center}
|
||
|
||
值得注意的是，上图也可以看成是数字逻辑电路中3位移位寄存器的状态转换图。
|
||
|
||
% 在上图中寻找到一条欧拉回路：$000\to 001\to 010\to 101\to 011\to 111\to 110\to 100\to 000$，这个好像是经过了所有顶点但没有经过所有的边？那个把图中的所有顶点换成边，所有边换成顶点的操作叫什么？好像这样操作之后就是欧拉通路，而且是3位的欧拉通路，但是这个本来能解决4位的问题转换后只能解决3位了，感觉好像和米利模型、摩尔模型也有关系，因为米利模型比摩尔模型可以用更少的状态。
|
||
|
||
在上图中寻找到一条欧拉回路：$110\to 100\to 000\to 000\to 001\to 011\to 111\to 111\to 110\to 101\to 010\to 100\to 001\to 010\to 101\to 011\to 110 $。
|
||
|
||
依次选取这条欧拉回路所经过的每个节点（终点除外）的最后一位，则可得到一个满足要求的0-1赋值为$0000111101001011$。
|
||
|
||
\end{proof}
|
||
\end{zhongwen}
|
||
\end{enumerate}
|
||
\end{document} |