書記が数学やるだけ#624 マッチングの性質

マッチングは，人間関係の可視化や構築など幅広い応用がある。

問題

特に完全マッチングが重要。

説明

マッチングの定義について。

必要十分条件をはじめとした，様々な定理がわかっている。

解答

ホールの結婚定理は非常にシンプル。

手間はかかるが，十分条件でもあることが言える。

より一般化したものに，タットの定理がある。

ピーターセンの定理について，立方体グラフとは全ての頂点の次数が3であるグラフを指し，後に扱う彩色でよく出てくる。

以上の定理から，完全グラフが2n-1個の完全マッチングに分解できることを示す。

本記事のもくじはこちら：