東北大学工学研究科電気・情報系 2018年3月実施基礎科目問題4 情報基礎2

标签：

Author

祭音Myyura (co-authored with GPT-5)

本問では、グラフとは有限無向グラフであり、自己ループ辺および多重辺が存在することは許すものとする。また、次の用語と記号を定義する。

任意のグラフ $G$ について、 $G$ の点の数を $n(G)$ 、辺の数を $m(G)$ でそれぞれ表す。
任意のグラフ $G$ とその点 $x$ について、 $G$ における $x$ の次数を $\deg(G,x)$ で表す。
グラフ $G$ 上の任意の歩道 $C$ について、 $C$ の長さ $\ell(C)$ は $C$ が通る辺の延べ総数である。
$C$ をグラフ $G$ 上の閉じた歩道とするとき、 $C$ が $1$ -回路（またはオイラー回路）であるとは、 $C$ が $G$ の各々の辺をちょうど $1$ 回ずつ通ることを言い、 $C$ が $2$ -回路であるとは、 $C$ が $G$ の各々の辺を $1$ 回または $2$ 回通ることを言う。
グラフ $G$ の部分グラフ $H$ がパリティ部分グラフであるとは、 $H$ が $G$ の全ての点を含み、かつ $G$ 上の任意の点 $x$ について、 $\deg(G,x)$ と $\deg(H,x)$ の偶奇が一致することを言う。 $G$ のパリティ部分グラフ $H$ で辺の数 $m(H)$ が最も少ないものを最小パリティ部分グラフと言う。

このとき、次の問に答えよ。ただし、必要ならば次の事実 (A)、(B) を証明なしに用いてもよい。

(A) 連結グラフ $G$ が $1$ -回路を持つためには、 $G$ の全ての点の次数が偶数であることが必要十分である。

(B) 任意の自然数 $n$ について、 $n$ 個の点から成る木は $n-1$ 本の辺を持つ。

(1) $G$ を連結グラフとする。

(a) $H$ を $G$ の任意のパリティ部分グラフとするとき、 $G$ は $\ell(C)=m(G)+m(H)$ となる $2$ -回路 $C$ を持つことを示せ。

(b) $C$ を $G$ 上の任意の $2$ -回路とするとき、 $G$ は $m(H)=\ell(C)-m(G)$ となるパリティ部分グラフ $H$ を持つことを示せ。

(2) $G$ を連結グラフ、 $H$ をその最小パリティ部分グラフとする。

(a) $H$ は閉路を持たないことを示せ。

(b) $G$ 上の最も短い $2$ -回路の長さを $\mu_2(G)$ とするとき、 $H$ は $m(G)+n(G)-\mu_2(G)$ 個の連結成分から成ることを示せ。

本题中的图均为有限无向图，允许自环和重边。记图 $G$ 的顶点数、边数为 $n(G),m(G)$ ，顶点 $x$ 的度为 $\deg(G,x)$ ，游走 $C$ 的长度 $l(C)$ 为经过边的总次数。

可以使用：连通图存在 Euler 回路当且仅当所有顶点度数为偶数； $n$ 个顶点的树有 $n-1$ 条边。

设 $G$ $G$ 连通。
- (a) 对任意奇偶子图 $H$ ，证明 $G$ 存在满足 $l(C)=m(G)+m(H)$ 的 2-回路。
- (b) 对任意 2-回路 $C$ ，证明存在满足 $m(H)=l(C)-m(G)$ 的奇偶子图。
设 $H$ $H$ 为连通图 $G$ $G$ 的最小奇偶子图。
- (a) 证明 $H$ 不含闭路。
- (b) 记最短 2-回路的长度为 $\mu_2(G)$ ，证明 $H$ 恰有 $m(G)+n(G)-\mu_2(G)$ 个连通分量。

(a) 将 $H$ 的每条边复制一份，加入 $G$ 得多重图 $G^+$ 。它仍连通，且

\deg(G^+,x)=\deg(G,x)+\deg(H,x)\equiv0\pmod2.

故 $G^+$ 存在 Euler 回路。将复制边视为原边，即得到 $G$ 的 2-回路，长度为 $\boxed{m(G)+m(H)}$ 。

(b) 取 $H$ 为由 $C$ 中经过两次的边构成的生成子图。显然

m(H)=l(C)-m(G).

闭游走在每个顶点使用的边端数为偶数（自环计两个边端），因此

\deg(G,x)+\deg(H,x)\equiv0\pmod2.

故 $H$ 是奇偶子图。

(a) 若 $H$ 含闭路，删除该闭路的全部边后，各有关顶点的度减少 $2$ ，奇偶性不变，却减少边数，与最小性矛盾。该论证同样适用于自环和两条重边构成的闭路。所以 $H$ 是森林。

(b) 由 (1) 的双向构造，最短 2-回路与最小奇偶子图满足

\mu_2(G)=m(G)+m(H).

若森林 $H$ 有 $c$ 个连通分量，逐分量使用树的边数公式得 $m(H)=n(G)-c$ 。因此

\boxed{c=n(G)-m(H)=m(G)+n(G)-\mu_2(G)}.