1.4
1.4.6
画出 de Bruijin 图 $D_2$ 和 $D_4$.
={Stealth[length=3mm, width=2mm]}, % 設定預設箭頭樣式
node_dist/.style={auto, font=\small, midway}, % 設定邊權重標籤的樣式
v/.style={
circle, % 圓形節點
draw=blue!50, % 邊框顏色
fill=blue!10, % 填充顏色
thick, % 邊框粗細
minimum size=0.7cm % 最小尺寸
}] \node[v] (v0) at (7, 2.5) {0};
\node[v] (v1) at (7, -2.5) {1}; \path[->] (v0) edge [loop left] node[node_dist] {0} (v0) % 邊 00 (自環)
(v0) edge [bend left=30] node[node_dist] {1} (v1) % 邊 01 (曲線) (v1) edge [bend left=30] node[node_dist] {0} (v0) % 邊 10 (曲線)
(v1) edge [loop right] node[node_dist] {1} (v1); % 邊 11 (自環) \node[v] (v000) at ( 0:4cm) {000};
\node[v] (v001) at ( 45:4cm) {001};
\node[v] (v011) at ( 90:4cm) {011};
\node[v] (v010) at (135:4cm) {010};
\node[v] (v100) at (225:4cm) {100};
\node[v] (v101) at (270:4cm) {101};
\node[v] (v111) at (315:4cm) {111};
\node[v] (v110) at (180:4cm) {110}; % 為了讓線條交叉較少，調整了位置 \path[->] (v000) edge [loop above] node[node_dist] {0} (v000);
\path[->] (v000) edge [bend left=10] node[node_dist] {1} (v001); \path[->] (v001) edge [bend left=10] node[node_dist, swap] {0} (v010);
\path[->] (v001) edge [bend left=10] node[node_dist] {1} (v011); \path[->] (v010) edge [bend left=10] node[node_dist] {0} (v100);
\path[->] (v010) edge [bend left=10] node[node_dist] {1} (v101); \path[->] (v011) edge [bend left=10] node[node_dist, swap] {0} (v110);
\path[->] (v011) edge [bend left=10] node[node_dist] {1} (v111); \path[->] (v100) edge [bend left=10] node[node_dist] {0} (v000);
\path[->] (v100) edge [bend left=10] node[node_dist, swap] {1} (v001); \path[->] (v101) edge [bend left=10] node[node_dist] {0} (v010);
\path[->] (v101) edge [bend left=10] node[node_dist, swap] {1} (v011); \path[->] (v110) edge [bend left=10] node[node_dist, swap] {0} (v100);
\path[->] (v110) edge [bend left=10] node[node_dist] {1} (v101); \path[->] (v111) edge [loop above] node[node_dist] {1} (v111);
\path[->] (v111) edge [bend left=10] node[node_dist, swap] {0} (v110); \end{tikzpicture}
答案
1.4.8
证明: 存在一个 $n$-顶点的竞赛图使得其中每个顶点的入度等于出度当且仅当 $n$ 是奇数.
"$\Leftarrow$": 用 $0,\ldots,n-1$ 表示节点编号, 以如下方式定向
$$
i\to (i+\lfloor \frac n 2\rfloor)\bmod n
$$
如此, 每个点出边指向比其大的一半点, 入边由比其小的一半点指来.
证明
1.4.10
证明: 一个有向图强连通当且仅当将顶点集任意划分成非空集合 $S$ 和 $T$ 后, 均存在一条从 $S$ 到 $T$ 的边.
"$\Leftarrow$": 对任意两个点 $u,v\in V(G)$, 考虑初始划分 $S=\{u\}, T=V(G)-\{u\}$, 存在一条 $S$ 到 $T$ 的边.
- (1) 这条边的另一个端点不是 $v$, 记作 $u_1$, 那么将 $u_1$ 加入 $S$ 中, 并从 $T$ 删去.
- (2) 这条边的另一个端点是 $v$, 那么我们就找到了一条 $u,v$-walk, 从而有 $u,v$-path, 即 $u$ 可达 $v$. 我们只需反复进行 (1) 操作直到 (2) 成立, 并且 (2) 一定会成立, 因为每次 (1) 都会使得 $T$ 中顶点数量减一, 至多 $n-2$ 次操作就会得到 $v$.
证明
1.4.14
令 $G$ 是一个无环的 $n$-顶点有向图. 证明: $G$ 的顶点可以被排序为 $v_1,\ldots,v_n$ 使得如果 $v_iv_j\in E(G)$ 则必有 $i<j$.
那么我们就将这个入度为 $0$ 的点加入最终序列里, 并删除这个点及其出边. 注意到, 删除这样的点和边后, 剩余的图仍是有向无环图, 所以可以重复上述操作直到所有点被取出. 下证上述操作得到的序列满足条件. 对于边 $v_iv_j\in E(G)$, 考虑这条边什么时候被删除, 当且仅当删除点 $v_i$ 的时候删除这条边, 而将点 $v_i$ 加入序列后 $v_j$ 仍在图中, 所以 $v_i$ 的位置一定在 $v_j$ 前面, 故满足 $i<j$.
证明
1.4.19
用引理对边数归纳来证明 一个有向图是欧拉图当且仅当 $d^+(v)=d^-(v)$ 对每个顶点 $v$ 成立, 并且其底图最多有一个非平凡的连通分量.
"$\Leftarrow$": 考虑数学归纳法, 对边数 $l$ 归纳. $l=0$ 时, 显然成立. 设 $l\leqslant k$ 时成立. 当 $l=k+1$ 时, 考虑底图非平凡的连通分支, 由 $d^+(v)=d^-(v)$, 可推出 $d^+(v)\geqslant 1$, 从而根据引理可以找到一个环. 如果这个环就是欧拉回路那么成立, 否则将这个环上的边删去, 剩下的图的每个连通分支根据归纳假设存在欧拉回路, 再用这个环将若干欧拉回路有向拼接就可得到整体的欧拉回路.
证明