5
大学数学基礎解説
文献あり

PILAME杯本選Day1 P2の線形代数による解法&一般化

254
0

まえがき

この記事では,グラフ理論における線形代数の応用例を紹介します.
閉路空間を用いてPILAME杯第1部問2の構成を自然に見つける方法の紹介と一般のグラフへの一般化を行います.
前提知識としてグラフ理論と線形代数の基本的な知識を要求しています.
また,この記事を書くに当たって[1]を参考にしました.

問題

今回議論するのは,以下の問題です.

N を 3 以上の整数とする.N 人の人がおり,最初はどの 2 人も互いに友人ではないとする.以 下のようなイベントを何回か起こすことで,どの 2 人も互いに友人であるようにできるような N をすべて求めよ.

  • N 人のうちの 3 人を選び,A, B, C とする.2 人組 (A, B), (B, C), (C, A) それぞれ について,互いに友人である場合は互いに友人でなくなり,互いに友人でない場合は 互いに友人になる.

これを言い換えると,次のようになります.

グラフで言い換え

頂点集合を V={1,2,,N},辺集合を E= とするグラフ G がある.以下の操作を何回か起こすことで,G=KN(完全グラフ)とできるような N を全て求めよ.

  • 相異なる a,b,cV を選び,EE{{a,b},{b,c},{c,a}} にする( は集合の対称差(xor)を表す).

さらに言い換えると,次のようになります.

グラフで言い換え2

頂点集合を V={1,2,,N},辺集合を E={{a,b}a,bV,ab} とする完全グラフ KN について, KN の部分閉路で長さが 3 であるようなもの(の辺集合)全体の集合を cyc3 とする.cyc3 のいくつかの元の対称差で表すことのできる E の部分集合全体の集合を C3 とする(ただしC3とする).EC3(グラフと辺集合を同一視すればKNC3とも書ける) であるような N を求めよ.

PILAME杯第1部問2の答え

<行間>
自分で考えたい人は今のうちに














</行間>

各頂点の次数の偶奇を考えることでNが偶数の時は不適であることがわかる.
Nが奇数のときは,頂点に1からNまでの数を割り振っておいて「(A,B,C)=(1,a,b)として操作を行う」を全ての1<a<bについて行えばよい.
よってN=()

線形代数による自然な別解

上記の構成は少々天下り的で応用も効きづらそうです.以下では線形代数による構成をしない解答とそこから構成を見つける方法を紹介します(本番もこれで解きました).
以降グラフは単純かつ無向であるとします.

辺空間

ある集合Sの部分集合全体の集合2Sは,対称差(排他的論理和)を和,0,1F2,x2Sについて積を1x=x,0x=と定義することによってF2上のベクトル空間となります.

辺空間

グラフGの辺集合E=E(G)の部分集合全体のなすベクトル空間を辺空間という.

以降,Gの部分グラフをその辺集合と同一視します.
Gの2つの偶部分グラフの対称差もまたGの偶部分グラフで,偶グラフはいくつかの閉路の非交和で表すことができるので,次のようなものを考えられます.

閉路空間

無向グラフGの偶部分グラフ全体のなすベクトル空間を閉路空間という.閉路空間はGの部分閉路によって生成される辺空間の部分空間である.

少し前の「グラフで言い換え2」で出てきたC3は長さ3の閉路で生成される閉路空間の部分空間となります.
今から任意のNC3KNの閉路空間が一致することを示し,そこからKNNが奇数のとき自分自身の偶部分グラフなのでKNC3であるということを導きます.
そのために,閉路空間の次元を調べます.

閉路空間の次元

閉路空間とボンド空間は直交する

閉路空間を辺空間の部分空間とみなしたとき,閉路空間はボンド空間の直交補空間である.

少々長くなるのでボンド空間についての解説は省略します(この定理の詳細はいつかは書くと思います,私がグラフ理論にハマったきっかけです).
連結グラフのボンド空間の次元はn1です(nGの頂点数).今回欲しいのはここから得られる次の系です.

連結グラフGの閉路空間の次元は|E|n+1である.

lockerさんが定理1を使わず系1を示しています ,ぜひ読んでみてください!.

閉路空間の基底

グラフGの全域木Tについて基本閉路というものが定義でき,これが基底となります.

基本閉路

グラフGの全域木TeETについて,T{e}はただ一つの閉路を持つ.これをT(あるいはeについて)の基本閉路と呼ぶ.

定理名(任意)

グラフGの任意の全域木Tについて,Tについての基本閉路全体の集合はGの閉路空間の基底である.

Teについての基本閉路cは他のどのTの基本閉路も持たない辺eを持っているので線形独立である.
Tの基本閉路は|E|n+1個あり,これは閉路空間の次元に等しい.
よって示された.

KNの全域木として,頂点1と他の全ての頂点を結ぶものを考えます.このとき基本閉路はすべて長さが3になります.よってC3は閉路空間となります.
完全グラフにおいてC3は閉路空間と一致することがわかりました.KNNが奇数のとき自分自身の偶部分グラフなのでKNC3,そうでないときKNC3です.よって示されました.
またここからNが奇数のとき基本閉路全ての対称差がKNとなることがわかるので,構成が得られます.

グラフで言い換え2の一般化

頂点集合を V={1,2,,N},辺集合を E={{a,b}a,bV,ab} とする完全グラフ KN について, KN の部分閉路で長さが 3 であるようなもの(の辺集合)全体の集合を cyc3 とする.cyc3 のいくつかの元の対称差で表すことのできる E の部分集合全体の集合を C3 とする(ただしC3とする).C3の元を特徴づけよ.

グラフで言い換え2の一般化の解答

C3は閉路空間と一致するので,xC3xKN

あとがき

グラフ理論は最高に面白いのでみんなやろう!!
非自明な面白い性質が山のように出てくるぞ!!

参考文献

[1]
著 J.A.ボンディ, U.S.R.マーティ 訳 山下 登茂紀, 千葉 周也, グラフ理論
投稿日:202497
更新日:202499
OptHub AI Competition

この記事を高評価した人

243
MARTH
色数
locker
2y

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

抹茶屋
抹茶屋
25
1728
数弱 抹茶より麦茶がすき

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. まえがき
  2. 問題
  3. 線形代数による自然な別解
  4. あとがき
  5. 参考文献