1.2
1.2.1
确定下列命题的真假. - a) 任意非连通图都有一个孤立顶点. - b) 一个图是连通的当且仅当它的某个顶点与其他所有顶点是连通的. - c) 任意闭合迹的边集可以划分成若干个环的边集. - d) 如果图中有一个极大迹不是闭合的, 则其端点的度是奇数.
{{< admonition note "答案" false >}}\ - a) 假. 如下图非连通, 但没有孤立点
\begin{tikzpicture} \graph[nodes={draw,circle,inner sep=0mm,minimum size=2.5mm}]{ 1--{2}; 3--{4}; }; \end{tikzpicture} - b) 假. 如下图, 不存在这种点.
\begin{tikzpicture} \graph[nodes={draw,circle,inner sep=0mm,minimum size=2.5mm}]{ 1--2--3--4; }; \end{tikzpicture} - c) 真.
当 $l=1$ 时, 该迹是一个自环. 假设 $l\leqslant k-1$ 时成立. 当 $l=k$ 时, 如果迹中的点不重复, 那么这个迹就是一个环. 否则这个迹有如下形式. $w$ 可以与 $u,v$ 相同. \begin{tikzpicture}
\graph[nodes={inner sep=2mm,minimum size=6mm,as=}]{
1--2--3--4--5--6--7;
};
\node at(1){$u$};
\node at(2){$\cdots$};
\node at(3){$w$};
\node at(4){$\cdots$};
\node at(5){$w$};
\node at(6){$\cdots$};
\node at(7){$v$};
\end{tikzpicture} 那么从 $w$ 到 $w$ 中间的边也构成一个闭合的迹, 将这个部分迹取出, 剩余部分也能拼成一个闭合的迹, 而这两个部分长度均小于 $k$, 根据归纳假设, 各自均可分为若干环. 所以 $l=k$ 成立. 考虑一条极大的迹. 由于在迹中间的顶点每次出现会使得度数加 2, 所以对于端点其度数如果是偶数那么至少还会有一条不在迹上的边. 这条边要么使迹扩张, 要么使迹闭合. 均矛盾. 所以极大迹如果不是闭合的其端点度必是奇数.
证明
证明
@@ADMONITION_END@@
1.2.3
令 $G$ 是顶点集为 $\{1,\ldots,15\}$ 的图, 其中 $i$ 和 $j$ 邻接当且仅当它们的最大公因数大于 1. 计算 $G$ 的分量数, 并求最长路径长度.
最长路径长度为 $11$, 考虑该路径 $7,14,12,9,6,3,15,5,10,8,4,2$. 而由于该连通分支大小为 $12$, 所以已经是最长路径.
答案
1.2.8
确定 $m$ 和 $n$ 的值, 使得 $K_{m,n}$ 是欧拉图.
答案
1.2.17
设 $G_n$ 是一个图, 其顶点是 $\{1,\ldots, n\}$ 的所有排列, 两个排列 $a_1,\ldots,a_n$ 和 $b_1,\ldots,b_n$ 是邻接的当且仅当他们是互换了某两个相邻位置上的元素. 证明: $G_n$ 是连通的.
对任意排列 $a_1,\ldots,a_n$, 找到第一个 $i$ 满足 $a_i\neq i$, 由于是排列, 故能找到 $j$ 满足 $a_j=i$ 并由 $i$ 的最小性得到 $j>i$. 那么我们就存在一条路径 $a_1,\ldots,a_i,\ldots,a_{j-1}, a_j,\ldots,a_n\to a_1,\ldots,a_i,\ldots,a_j,a_{j-1},\ldots,a_n\to\cdots\to a_1,\ldots,a_j,a_i,\ldots,a_{j-2},a_{j-1},\ldots,a_n$. 即依次将 $a_j$ 往前交换, 交换 $j-i$ 次后新的排列就满足 $a'_i=i$. 于是反复上述操作, 每次寻找第一个满足 $a_i\neq i$ 的位置并调整该位置相同, 经过不超过 $n-1$ 次调整就可以得到 $12\cdots n$. 而将每次操作的路径连起来就得到任意排列和 $12\cdots n$ 连通, 从而 $G_n$ 连通.
证明
1.2.38
证明: 具有至少 $n$ 条边的 $n$-顶点图含有至少一个环.
我们以任意顺序依次加入 $n$ 条边. 并记连通分支数量为 $d$, 初始 $d=n$. 设当前边的两个端点为 $x,y$. 如果 $x,y$ 不连通, 那么加入该边会使得 $x,y$ 各自所属的连通分支连通, 即连通分支数量减一. 而如果 $x,y$ 已经连通, 那么存在一条 $x,y$-path, 从而在加入这条边后变成一条闭合的 $x,y$-walk, 进而存在一个环. 而对于第一种情况, 当我们加入 $n-1$ 条边的时候如果之前每条边都不构成环, 那么 $x_n,y_n$ 必定连通, 因为之前 $n-1$ 条边使连通分支数量减少 $n-1$, 故此时只剩下 $n-(n-1)=1$ 个连通分支, 即 $x,y$ 连通. 所以存在环.
证明