图论与组合：作业 / 1.2

迁移来源

旧站标题：1.2

新站标题：图论与组合：作业 / 1.2

旧站路径：/math/课程/图论与组合/exams/作业/1-2/

旧页面 ID：329

1.2 #

1.2.1 #

确定下列命题的真假.

a) 任意非连通图都有一个孤立顶点.
b) 一个图是连通的当且仅当它的某个顶点与其他所有顶点是连通的.
c) 任意闭合迹的边集可以划分成若干个环的边集.
d) 如果图中有一个极大迹不是闭合的, 则其端点的度是奇数.

note

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) 真.

note

用数学归纳法, 对迹的长度 $l$ 归纳.

当 $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$ 成立.

4) 真. {{< admonition note “证明” false >}} 用反证法, 反设端点的度数是偶数.

考虑一条极大的迹. 由于在迹中间的顶点每次出现会使得度数加 2, 所以对于端点其度数如果是偶数那么至少还会有一条不在迹上的边.

这条边要么使迹扩张, 要么使迹闭合. 均矛盾.

所以极大迹如果不是闭合的其端点度必是奇数.

1.2.3 #

令 $G$ 是顶点集为 $\{1,\ldots,15\}$ 的图, 其中 $i$ 和 $j$ 邻接当且仅当它们的最大公因数大于 1. 计算 $G$ 的分量数, 并求最长路径长度.

note

$1$ , $11$ , $13$ 三个点是孤立点, 其余节点连通, 所以共有 4 个分支.

最长路径长度为 $11$ , 考虑该路径 $7,14,12,9,6,3,15,5,10,8,4,2$ .

而由于该连通分支大小为 $12$ , 所以已经是最长路径.

1.2.8 #

确定 $m$ 和 $n$ 的值, 使得 $K_{m,n}$ 是欧拉图.

note

根据欧拉图的充要条件是至多一个连通分支且每个点的度数都是偶数. 连通条件直接满足, 每个点度数是偶数只要求 $m,n$ 均为偶数.

1.2.17 #

设 $G_n$ 是一个图, 其顶点是 $\{1,\ldots, n\}$ 的所有排列, 两个排列 $a_1,\ldots,a_n$ 和 $b_1,\ldots,b_n$ 是邻接的当且仅当他们是互换了某两个相邻位置上的元素. 证明: $G_n$ 是连通的.

note

考虑证明任一排列和 $12\cdots 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$ -顶点图含有至少一个环.

note

考虑依次加边. 初始的图是 $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$ 连通. 所以存在环.

1.2 #

1.2.1 #

1.2.3 #

1.2.8 #

1.2.17 #

1.2.38 #

评论