0

マイナー順序のフィルターで禁止マイナーを表す

67
1

はじめに

これはグラフ理論の記事です。
証明はとばすことがあります。

本題

マイナーを表すためにグラフの縮約について書く。
縮約とは、グラフの辺を一つ選び、選んだ辺を削除して、辺の両端の点をくっつける。
そうして得らてたグラフをG/e(グラフGの辺eを縮約したという意味)と書く。
次にマイナー順序

マイナーとして含む

グラフGとグラフGがあるときGにたいして縮約を繰り返してGにできるときGGをマイナーとして含むという

これを使って順序を作る、と言ってもそのままで、

マイナー順序

GG'をマイナーとして含むときGGとして、これをマイナー順序という

マイナー順序は半順序ですが、証明がわからず、ネットでは 推移律について 書かれていましたが、反対称律はわかりませんでした。(反射律は縮約をしないまたは0かいするとすれば自明で良いと思います)

禁止マイナー

グラフの集合(族)AとグラフXがあるときAの全てのグラフがXをマイナーとして含まないときXを禁止マイナーという。

ここで禁止マイナーをフィルターで表すためにフィルターの定義を確認する。

フィルター

半順序(G,)にたいしてGの空ではない部分集合Fがフィルターであるとは、
1,a,bFca,cbとなるcFに含まれる。
2,aFについてabとなるbFに含まれる。

ここでGをグラフ全体として、禁止マイナーをa1,a2,,,として、禁止マイナー全体をUとする。a1をマイナーとして含むグラフ全体をFa1とする、これはフィルターである。a2,a3,,,にも同じことができる。
すると、Faxaxをマイナーとして含むグラフを全て含み、かつそれしか含まないので(2の性質とFaxの構成方法からくる)、その補集合はaxをマイナーとして含まないグラフの集合となる。
これより、
A=(aiUFai)c
ここで、大事な定理

定理 Wagner

マイナーで閉じたグラフの族Aは有限個の禁止マイナーで表せる。

証明は省きます。ざっくりとした証明やより詳しく見たい人は
駆け足で学ぶグラフマイナーの定理
を参照してください。
これらから、Xのグラフをマイナーとして含まないグラフの集合Aがマイナーで閉じていたら
nN
A=(i=1nFai)c
になる。

おわりに

禁止マイナーとそれで特徴付けられたグラフのフィルターを使った表し方について書きました。
間違いがあったら教えてください。

投稿日:2024419
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

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

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

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

投稿者

高二です

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中