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

Author

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

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

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

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

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

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.

(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.