これはグラフ理論の記事です。
証明はとばすことがあります。
マイナーを表すためにグラフの縮約について書く。
縮約とは、グラフの辺を一つ選び、選んだ辺を削除して、辺の両端の点をくっつける。
そうして得らてたグラフを
次にマイナー順序
グラフ
これを使って順序を作る、と言ってもそのままで、
マイナー順序は半順序ですが、証明がわからず、ネットでは 推移律について 書かれていましたが、反対称律はわかりませんでした。(反射律は縮約をしないまたは0かいするとすれば自明で良いと思います)
グラフの集合(族)
ここで禁止マイナーをフィルターで表すためにフィルターの定義を確認する。
半順序
1,
2,
ここで
すると、
これより、
ここで、大事な定理
マイナーで閉じたグラフの族
証明は省きます。ざっくりとした証明やより詳しく見たい人は
駆け足で学ぶグラフマイナーの定理
を参照してください。
これらから、
になる。
禁止マイナーとそれで特徴付けられたグラフのフィルターを使った表し方について書きました。
間違いがあったら教えてください。