🗺️

グラフ理論の”横断”についてクソ雑なメモ

2022/11/26に公開

社会人大学生をやっていて、グラフ理論の授業で”横断”が一瞬どういうことかわからなかった→ちょっとわかって問題が解ける状態になったのでメモする。というわけで専門的な内容は含んでいません。怒らないでください。

Tl; Dr

大体↓のような説明がされていることが多い。なんとなくわかった気にはなる。

E: 空でない有限集合
F = (S1, S2, ··· , Sm):E の空でない部分集合の族
Fの横断 : 各集合Siから、1つ選んだEの相異なるm個の元の集合

以下の集合Eと部分集合の族Fについて考える。

E = {1,2,3,4,5}
F = ({1,3}, {2,3}, {4,5}, {4, 5})
(Fの左から順に集合S1 ~ S4とする)

以下の手順で横断を見つけることができる。

以下の集合Eと部分集合の族Fについて考える。

E = {1,2,3,4,5}
F = ({1,3}, {2,3}, {1,2}, {3})
(Fの左から順に集合S1 ~ S4とする)

以下の手順で横断を見つけようとする。