まえがき
この記事では,グラフ理論における線形代数の応用例を紹介します.
閉路空間を用いてPILAME杯第1部問2の構成を自然に見つける方法の紹介と一般のグラフへの一般化を行います.
前提知識としてグラフ理論と線形代数の基本的な知識を要求しています.
また,この記事を書くに当たって[1]を参考にしました.
問題
今回議論するのは,以下の問題です.
N を 3 以上の整数とする.N 人の人がおり,最初はどの 2 人も互いに友人ではないとする.以 下のようなイベントを何回か起こすことで,どの 2 人も互いに友人であるようにできるような N をすべて求めよ.
- N 人のうちの 3 人を選び,A, B, C とする.2 人組 (A, B), (B, C), (C, A) それぞれ について,互いに友人である場合は互いに友人でなくなり,互いに友人でない場合は 互いに友人になる.
これを言い換えると,次のようになります.
グラフで言い換え
頂点集合を ,辺集合を とするグラフ がある.以下の操作を何回か起こすことで,(完全グラフ)とできるような を全て求めよ.
- 相異なる を選び, を にする( は集合の対称差(xor)を表す).
さらに言い換えると,次のようになります.
グラフで言い換え2
頂点集合を ,辺集合を とする完全グラフ について, の部分閉路で長さが であるようなもの(の辺集合)全体の集合を とする. のいくつかの元の対称差で表すことのできる の部分集合全体の集合を とする(ただしとする).(グラフと辺集合を同一視すればとも書ける) であるような を求めよ.
PILAME杯第1部問2の答え
<行間>
自分で考えたい人は今のうちに
</行間>
各頂点の次数の偶奇を考えることでが偶数の時は不適であることがわかる.
が奇数のときは,頂点にからまでの数を割り振っておいて「として操作を行う」を全てのについて行えばよい.
よって
線形代数による自然な別解
上記の構成は少々天下り的で応用も効きづらそうです.以下では線形代数による構成をしない解答とそこから構成を見つける方法を紹介します(本番もこれで解きました).
以降グラフは単純かつ無向であるとします.
辺空間
ある集合の部分集合全体の集合は,対称差(排他的論理和)を和,について積をと定義することによって上のベクトル空間となります.
辺空間
グラフの辺集合の部分集合全体のなすベクトル空間を辺空間という.
以降,の部分グラフをその辺集合と同一視します.
の2つの偶部分グラフの対称差もまたの偶部分グラフで,偶グラフはいくつかの閉路の非交和で表すことができるので,次のようなものを考えられます.
閉路空間
無向グラフの偶部分グラフ全体のなすベクトル空間を閉路空間という.閉路空間はの部分閉路によって生成される辺空間の部分空間である.
少し前の「グラフで言い換え2」で出てきたは長さ3の閉路で生成される閉路空間の部分空間となります.
今から任意のでとの閉路空間が一致することを示し,そこからはが奇数のとき自分自身の偶部分グラフなのでであるということを導きます.
そのために,閉路空間の次元を調べます.
閉路空間の次元
閉路空間とボンド空間は直交する
閉路空間を辺空間の部分空間とみなしたとき,閉路空間はボンド空間の直交補空間である.
少々長くなるのでボンド空間についての解説は省略します(この定理の詳細はいつかは書くと思います,私がグラフ理論にハマったきっかけです).
連結グラフのボンド空間の次元はです(はの頂点数).今回欲しいのはここから得られる次の系です.
lockerさんが定理1を使わず系1を示しています
,ぜひ読んでみてください!.
閉路空間の基底
グラフの全域木について基本閉路というものが定義でき,これが基底となります.
基本閉路
グラフの全域木とについて,はただ一つの閉路を持つ.これを(あるいはについて)の基本閉路と呼ぶ.
定理名(任意)
グラフの任意の全域木について,についての基本閉路全体の集合はの閉路空間の基底である.
のについての基本閉路は他のどのの基本閉路も持たない辺を持っているので線形独立である.
の基本閉路は個あり,これは閉路空間の次元に等しい.
よって示された.
の全域木として,頂点1と他の全ての頂点を結ぶものを考えます.このとき基本閉路はすべて長さが3になります.よっては閉路空間となります.
完全グラフにおいては閉路空間と一致することがわかりました.はが奇数のとき自分自身の偶部分グラフなので,そうでないときです.よって示されました.
またここからが奇数のとき基本閉路全ての対称差がとなることがわかるので,構成が得られます.
グラフで言い換え2の一般化
頂点集合を ,辺集合を とする完全グラフ について, の部分閉路で長さが であるようなもの(の辺集合)全体の集合を とする. のいくつかの元の対称差で表すことのできる の部分集合全体の集合を とする(ただしとする).の元を特徴づけよ.
あとがき
グラフ理論は最高に面白いのでみんなやろう!!
非自明な面白い性質が山のように出てくるぞ!!