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

Author

祭音Myyura (assisted by GPT-5)

Description

日本語版

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

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

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

• (A) 連結グラフ が -回路を持つためには、 の全ての点の次数が偶数であることが必要十分である.
• (B) 任意の自然数 について、 個の点から成る木は 本の辺を持つ。

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

• (a) を の任意のパリティ部分グラフとするとき、 は となる -回路 を持つことを示せ。
• (b) を 上の任意の -回路とするとき， は となるパリティ部分グラフ を持つことを示せ。

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

• (a) は閉路を持たないことを示せ。
• (b) 上の最も短い -回路の長さを とするとき、 は 個の連結成分から成ることを示せ。

English Version

In this question, any graph is a finite undirected graph which may have self-loops and multiple edges. Define the folowing terms and symbols:

• For any graph , let and denote the number of vertices and edges in , respectively.
• For any graph and any vertex in , denotes the degree of in .
• For any graph and any walk on , the length of is the total number of edges that passes.
• For a graph and a closed walk on , is a 1-circuit (or an Euler circuit) if passes each edge of exactly once, and is a 2-circuit if passes each edge of once or twice.
• A subgraph of a graph is a parity subgraph if contains all vertices of and for any vertex in , and have the same odd-even parity. A parity subgraph of is a minimum parity subgraph if the number of edges in is minimum among all parity subgraphs of .

Answer the folowing questions. If necessary, the following facts (A) and (B) can be applied without proof.

• (A) A connected graph has a 1-circuit if and only if every vertex of is of even degree.
• (B) For any natural number , any tree of vertices has edges.

(1) Let be any connected graph.

• (a) Prove that for any parity subgraph of , has a 2-circuit such that .
• (b) Prove that for any 2-circuit in , has a parity subgraph such that .

(2) Let be any connected graph and be any minimum parity subgraph of .

• (a) Prove that contains no cycle.
• (b) Let denote the length of a shortest 2-circuit in . Prove that consists of connected components.

Kai

(1)

(a) From a parity subgraph to a 2-circuit and its length

Let be a parity subgraph. Form a multigraph by adding one parallel copy of every edge of to . Then for each vertex ,

so every vertex of has even degree. By (A), has an Euler circuit .

Read back in by forgetting which of two parallel copies it used.
Every edge of is used once; every edge of is used twice.
Thus we obtain a 2-circuit in with

(b) From a 2-circuit to a parity subgraph and its size

Let be any 2-circuit of . Define to be the subgraph consisting of the edges that uses twice. Then

To see is a parity subgraph, fix a vertex . In the closed walk , each visit to uses two incident edge-ends (enter/leave), and a loop at contributes two ends; hence the total number of used edge-ends at is even. Modulo , this implies the number of incident edges used exactly once at is even, i.e.

Thus is a parity subgraph and .

(2) Structure of a minimum parity subgraph

Let be a minimum parity subgraph (minimum number of edges). Let be the length of a shortest 2-circuit in .

(a) has no cycle

If contained a cycle (a loop counts as a 1-cycle), removing all edges of would decrease the degree of each vertex on by , preserving parity at every vertex. The resulting subgraph would be a parity subgraph with fewer edges, contradicting the minimality of . Hence is acyclic.

(b) Number of components of

From (1a): for any parity subgraph there exists a 2-circuit with

From (1b): for any 2-circuit there exists a parity subgraph with

Together,

Since is minimum, .

Because is a forest on vertices and edges, its number of components is

Therefore

Knowledge

The Chinese Postman Problem (CPP) and T-joins could be very useful references.