広島大学 先進理工系科学研究科 情報科学プログラム 2019年8月実施 専門科目I 問題4

Author

祭音Myyura

Description

グラフ の辺集合 は、任意の が互いに端点を共有しないときマッチングと呼ばれる。 またそれ以上辺を追加できないマッチングを極大マッチングと呼ぶ。

(1) 図 1 に示すグラフの極大マッチングを二つ示せ。

(2) グラフ の任意の極大マッチング に対して が成立することを証明せよ。 ここで であり、 は集合 の濃度（cardinality）を表すものとする。

(3) 上の証明と関係 を利用して、 であることを証明せよ。

(4) であるような極大マッチング を持つグラフの例を示せ。

---

Given graph , a subset of edges is called a matching if any two edges share no end vertex. A matching is said to be maximal if any superset of is not a matching.

(1) Show two maximal matchings of the graph shown in Figure 1.

(2) Prove holds for any maximal matchings and of a given graph . Here, is defined as and denotes the cardinality of set .

(3) Prove by using the above statement and equation .

(4) Show an example of graph to have maximal matchings and satisfying .

Kai

(1)

(2)

Note that each edge in can be adjacent to at most edges in since is a matching; and each edge in is adjacent to an edge in by maximality of , hence we have

(3)

(4)

matchings