Loading article…
数学の一分野であるグラフ理論では、多くの重要なグラフ族は、族に属さない個々のグラフの有限集合によって記述することができ、さらに、これらの禁制グラフのいずれかを（誘導）サブグラフまたはマイナーとして含むすべてのグラフを族から除外することができる。
この現象の典型的な例は、クラトフスキーの定理である。これは、グラフが平面的（平面上で交差することなく描画できる）であるためには、完全グラフ K 5と完全二部グラフ K 3,3という 2 つの禁制グラフのどちらも含まないことを規定する。クラトフスキーの定理では、包含の概念はグラフ同相の概念であり、一方のグラフの細分が他方のグラフのサブグラフとして現れる。したがって、すべてのグラフは平面描画を持つか（その場合、平面グラフの族に属する）、少なくとも 1 つのグラフのサブグラフとしての細分を持つか（その場合、平面グラフには属さない）、のいずれかである。
意味
より一般的には、禁制グラフの特徴付けは、グラフまたはハイパーグラフ構造のファミリを指定する方法であり、ファミリ内のどのグラフにも存在が禁じられているサブ構造を指定します。ファミリによって禁制の性質は異なります。一般に、構造Gがファミリのメンバーとなるのは、禁制サブ構造がGに含まれていない場合のみです。禁制サブ構造は次のいずれかです。
- サブグラフ、大きなグラフの頂点と辺の部分集合から得られる小さなグラフ、
- 誘導サブグラフ、頂点のサブセットを選択し、そのサブセット内の両端を持つすべての辺を使用することによって得られるより小さなグラフ、
- 同相サブグラフ（位相小グラフとも呼ばれる）、サブグラフから次数2の頂点のパスを単一の辺に縮小することによって得られるより小さなグラフ、または
- グラフマイナー、任意のエッジ収縮によってサブグラフから得られるより小さなグラフ。
特定のグラフ ファミリに属することが禁止されている構造の集合は、そのファミリの 障害集合とも呼ばれます。
禁制グラフの特徴付けは、グラフが特定のファミリに属するかどうかをテストするアルゴリズムで使用できます。多くの場合、特定のグラフに障害集合のメンバーが含まれているかどうか、つまりその障害集合によって定義されたファミリに属するかどうかを 多項式時間でテストできます。
族が特定の種類のサブ構造を伴う禁制グラフ特性を持つためには、族はサブ構造に関して閉じていなければなりません。つまり、族内のグラフのすべてのサブ構造 (特定の種類) は、族内の別のグラフでなければなりません。同様に、グラフが族の一部でない場合、それをサブ構造として含むすべてのより大きなグラフも族から除外されなければなりません。これが真である場合、常に障害集合 (族には属さないが、より小さなサブ構造がすべて族に属するグラフの集合) が存在します。ただし、サブ構造の概念によっては、この障害集合が無限になることがあります。ロバートソン-シーモア定理は、グラフマイナーの特定のケースでは、マイナーに関して閉じている族は常に有限の障害集合を持つこと を証明しています。
グラフとハイパーグラフの禁止された特性のリスト
参照
参考文献
- ^ abc Diestel, Reinhard (2000)、グラフ理論、Graduate Texts in Mathematics、vol. 173、Springer-Verlag、ISBN 0-387-98976-5。
- ^ クリストファー・アウアー;バックマイヤー、クリスチャン。ブランデンブルク、フランツ J.グライスナー、アンドレアス。ハナウアー、キャスリン。ニューワース、ダニエル。 Reislhuber、Josef (2013)、「線形時間での外側 1 平面グラフの認識」、Wismath、Stephen; Wolff, Alexander (編)、第 21 回国際シンポジウム、GD 2013、ボルドー、フランス、2013 年 9 月 23 ～ 25 日、改訂された厳選論文、コンピュータ サイエンスの講義ノート、vol. 8242、pp. 107–118、土井：10.1007/978-3-319-03841-4_10、ISBN 978-3-319-03840-7。
- ^ Gupta, A.; Impagliazzo, R. (1991)、「Computing planar intertwines」、Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91)、IEEE Computer Society、pp. 802–811、doi :10.1109/SFCS.1991.185452、ISBN 0-8186-2445-0、S2CID 209133。
- ^ ロバートソン、ニール;シーモア、PD ;トーマス、ロビン(1993)、「3 次元空間におけるグラフのリンクレス埋め込み」、アメリカ数学会誌、28 (1): 84–89、arXiv : math/9301216、doi :10.1090/S0273-0979-1993-00335-5、MR 1164063、S2CID 1110662。
- ^ Béla Bollobás (1998) 「Modern Graph Theory」、Springer、ISBN 0-387-98488-7 p. 9
- ^ 柏原俊信 (1981)、「一部の交差グラフのアルゴリズム」、斉藤信次;西関隆雄編、グラフ理論とアルゴリズム、第 17 回東北大学電気通信研究所シンポジウム、仙台、1980 年 10 月 24-25 日、講演論文集、コンピュータサイエンス講義ノート、vol. 108、Springer-Verlag、pp. 171–181、土居：10.1007/3-540-10704-5_15、ISBN 978-3-540-10704-0。
- ^マリア・ チュドノフスキー、ニール・ロバートソン、ポール・シーモア、ロビン・トーマス(2006)、「強い完全グラフ定理」(PDF)、数学年報、164 (1): 51–229、arXiv : math/0212070v1、doi :10.4007/annals.2006.164.51、S2CID 119151552。
- ^ Beineke、LW (1968)、「有向グラフの導出グラフ」、Sachs、H.;ヴォス、H.-J.ウォルター、H.-J. (編)、Beiträge zur Graphentheorie、ライプツィヒ: Teubner、17–33 ページ。
- ^ El-Mallah, Ehab; Colbourn, Charles J. (1988)、「いくつかのエッジ削除問題の複雑さ」、IEEE Transactions on Circuits and Systems、35 (3): 354–362、doi :10.1109/31.1748。
- ^ 高見沢 功;西関 隆雄; 斉藤 信治 (1981)、「直列並列グラフの組合せ問題」、離散応用数学、3 (1): 75–76、doi : 10.1016/0166-218X(81)90031-7。
- ^ Földes, Stéphane; Hammer, Peter Ladislaw (1977a)、「Split graphs」、Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977)、Congressus Numerantium、vol. XIX、Winnipeg: Utilitas Math.、pp. 311–315、MR 0505860
- ^ Bodlaender, Hans L. (1998)、「木幅が制限されたグラフの部分kアーボレタム」、理論計算機科学、209 (1–2): 1–45、doi :10.1016/S0304-3975(97)00228-4、hdl : 1874/18312。
- ^ Bodlaender, Hans L. ; Thilikos, Dimitrios M. (1999)、「枝幅が最大 3 のグラフ」、Journal of Algorithms、32 (2): 167–194、doi :10.1006/jagm.1999.1011、hdl : 1874/2734。
- ^ Seinsche, D. (1974)、「 n色付きグラフのクラスの特性について」、Journal of Combinatorial Theory、シリーズB、16 (2): 191–193、doi : 10.1016/0095-8956(74)90063-X、MR 0337679
- ^ ab ゴルビック、マーティン・チャールズ（1978）、「自明に完璧なグラフ」、離散数学、24（1）：105–107、doi：10.1016/0012-365X（78）90178-4。
- ^ Metelsky, Yury; Tyshkevich, Regina (1997)、「線形 3 ユニフォームハイパーグラフのライングラフについて」、Journal of Graph Theory、25 (4): 243–251、doi :10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K、MR 1459889
- ^ Jacobson, MS; Kézdy, Andre E.; Lehel, Jeno (1997)、「線形ユニフォームハイパーグラフの交差グラフの認識」、Graphs and Combinatorics、13 (4): 359–367、doi :10.1007/BF03353014、MR 1485929、S2CID 9173731
- ^ Naik, Ranjan N.; Rao, SB; Shrikhande, SS ; Singhi, NM (1982)、「k -uniform hypergraphs の交差グラフ」、European Journal of Combinatorics、3 : 159–172、doi : 10.1016/s0195-6698(82)80029-2、MR 0670849
- ^ Yu, Yanming (2006)、「ワイデルタワイ還元性に対するさらなる禁止マイナー」、The Electronic Journal of Combinatorics、13、doi : 10.37236/1033Webサイト
- ^ Jiang, Zilin; Polyanskii, Alexandr (2020-03-01). 「有界スペクトル半径のグラフの禁制部分グラフと等角線への応用」. Israel Journal of Mathematics . 236 (1): 393–421. arXiv : 1708.02317 . doi :10.1007/s11856-020-1983-2. ISSN 1565-8511.