区間グラフ

区間を表す7本の線（下）と、それに対応する7頂点の区間グラフ

区間グラフとは、グラフ理論のグラフの一種であり、区間集合の区間の重複を表す交差グラフである。 それぞれの区間が頂点に対応し、辺は区間同士の重複（交差）関係を表す。

定義

正式には、区間グラフは区間の族

Si, （i = 0, 1, 2, ... ）

に対し、頂点 vi をそれぞれ1個ずつ与え、 SiとSjが空集合ではない共通部分（交差）を持つ場合にのみ、vi と vj を辺で結んだ、無向グラフである。つまり、グラフ G の辺集合 E(G)は

E(G) = {{vi, vj} | Si ∩ Sj ≠ ∅}.

である。

特徴

ある3つの頂点に対して、そのうち2つを含むが3つめの頂点に隣接する頂点を含まないパスが存在する場合、そのグラフ G はasteroidal tripleを形成する。また、asteroidal triple を含まない場合、グラフはAT-freeという。 区間グラフの初期の特徴付けは以下のようなものであった。

区間グラフは以下のグラフと同値である。

  • AT-freeである弦グラフ[1]
  • G の極大クリークが、i < k ならば任意のv ∈ Mi ∩ Mk であるようにM1, M2, ..., Mk と順序付けができるグラフ（i ≤ j ≤ kなるv ∈ Mj についても同様）[2]。
  • 極大クリークに含まれる辺の被覆が、クリークパス表現に配置することができるグラフ[3]。

他にも、区間グラフは様々な特徴付けがなされている[5][6]。

効率的なアルゴリズム

与えられたグラフ G = (V, E) が区間グラフであるかは、頂点被覆に関して連続な G の極大クリークの順番を求めることで O(|V|+|E|) 時間で判別できる。[要出典]

Booth & Lueker (1976)による線形時間アルゴリズムはPQ-木を用いたデータ構造をベースにしていた複雑な手法であったが、Habib et al. (2000)が「区間グラフは弦グラフかつ補グラフが比較可能グラフである」という性質を用い、よりシンプルな辞書順幅優先探索を用いた手法を示した[2][7]。 Corneil, Olariu & Stewart (2009)に6-sweep 辞書順幅優先探索を用いた手法も紹介されている。

関連するグラフ

AT-freeな弦グラフとしての特徴づけにより、区間グラフは強弦グラフであり、パーフェクトグラフである[1]。 補グラフが比較可能グラフであり、その大小関係はその区間順序(interval order)である[4][2]。

弦グラフでありその補グラフが比較可能であるという性質より、あるグラフとその補グラフの両方が区間グラフである場合、そしてその時に限りそれはスプリットグラフであり、置換グラフである。

任意の2区間が、重複区間を持たないかどちらかが完全に被覆する区間グラフは、自明なパーフェクトグラフ（英語版）である。

グラフのboxicityが1以上の場合、そしてその時に限り、そのグラフは区間グラフである。つまり、グラフ G の boxicity は区間グラフの辺集合の交差が G となるような頂点と同じ集合の区間集合の最小数である。

区間グラフの始点と終点を接続したものを円-弧グラフと呼び、全区間を円、区間を弧と呼ぶ。台形グラフも区間グラフの一般化である。 連結グラフの内、三角形を含まない区間グラフはキャタピラ木である[8]。

真区間グラフ（狭義区間グラフ）

真区間グラフは、被覆するような区間が存在しない区間グラフを指す。図は区間Bが区間Aに被覆され、区間Eは区間Dに、そして更に区間Dは区間Cに被覆されているため、真区間グラフではない。 単位区間グラフはすべての区間が長さ1であるような区間グラフである。同一区間を持たない単位区間グラフは、真区間グラフである。真区間グラフが常に単位区間グラフであるわけではないが、単位区間グラフは真区間グラフである[9]。真区間グラフは、クローフリーグラフであり、真区間グラフはクローフリー区間グラフである。しかし、区間グラフではないクローフリーグラフも存在する[10]。

区間グラフが、 q 個の例外区間を除き、他の区間に被覆される区間を持たない場合、q-真区間グラフであると呼ぶ。この表記では、真区間グラフは 0-真区間グラフである[11]。 図では、B, D, Eの3つが被覆されており、この3つ以外は真区間グラフを満たすため、3-真区間グラフである。

仮区間グラフ（広義区間グラフ）

区間グラフが p 個の例外区間を除き、他の区間を被覆する区間を持たない場合、p-仮区間グラフと呼ぶ。この表記では、真区間グラフは 0-仮区間グラフである[12] 図では、A, C, Dが他の区間を被覆し、この3つ以外は真区間グラフを満たすため、3-仮区間グラフである。

k-重 区間グラフ

k +1 段の入れ子になっていない区間グラフを、k -重であると呼ぶ。真区間グラフは被覆する区間を持たないため、 1-重区間グラフである[13]。

応用

区間グラフの数学理論は、ランド研究所の数学部門の研究者によって、応用を視野に入れて発展された。この部門には、Delbert FulkersonやVictor Kleeといったリーダーの他に、Peter C. Fishburnや、Alan C. TuckerやJoel E. Cohenなど学生といった若い研究者もいた[14]。Cohenは、集団生物学の数学的モデル、特に食物連鎖に区間グラフを応用した。[15]

区間グラフはオペレーションズ・リサーチのリソース割り当てやスケジューリングの制約を表すために用いられる。これらの応用では、それぞれの区間はリソースを必要とする区間（例えば、分散コンピューティングのプロセッサや授業のための教室）を表す。独立集合の最大重さは、リソースが衝突することなく割り当てが完了する、最良の割り当てを見つける問題の並列数を表す[16]。 区間グラフの最適彩色は最小のリソースへの割り当てを表し、貪欲彩色法により多項式時間で計算可能である[17]。

遺伝学やバイオインフォマティクスや計算機科学などの他の応用も存在する。DNAの断片から連続した元のゲノムの配列を予想するマッピングなどに使われる[18]。区間はtemporal reasoningでも重要な役割を担う[19]。

区間completionとパス幅

任意のグラフ G に対する、 Gの区間completionとは、部分グラフとしてGを含む同じ頂点集合上の区間グラフである。パラメータ化された区間completion（k個の追加辺をもつ区間拡大グラフを見つける）は、準指数関数時間で解決可能である[20][21]。

区間グラフのパス幅は最大クリークのサイズ-1であり、彩色数-1である。任意のグラフに対するパス幅はG を部分グラフとして含む区間グラフの最小のパス幅である。[22]。

注釈・出典

  1. ^ a b Lekkerkerker & Boland (1962)
  2. ^ a b c (Fishburn 1985)
  3. ^ Fulkerson & Gross (1965)
  4. ^ a b Gilmore & Hoffman (1964)
  5. ^ McKee & McMorris (1999)
  6. ^ Brandstädt, Le & Spinrad (1999)
  7. ^ Golumbic (1980).
  8. ^ Eckhoff (1993)
  9. ^ Roberts (1969); Gardi (2007)
  10. ^ Faudree, Flandrin & Ryjáček (1997), p. 89.
  11. ^ Proskurowski, Andrzej; Telle, Jan Arne (1999). “Classes of graphs with restricted interval models”. Discrete Mathematics & Theoretical Computer Science. 3 (4): 167–176. 
  12. ^ Beyerl, Jeffrey; Jamison, Robert (2008). “Interval graphs with containment restrictions”. Congressus Numerantium 191 (2008): 117–128. arXiv:1109.6675. Bibcode: 2011arXiv1109.6675B. 
  13. ^ Klavík, Pavel; Otachi, Yota; Šejnoha, Jiří (14 October 2015). "On the Classes of Interval Graphs of Limited Nesting and Count of Lengths". arXiv:1510.03998 [cs.DM]。
  14. ^ Cohen (1978, pp. ix-10)
  15. ^ Cohen (1978, pp. 12–33)
  16. ^ Bar-Noy et al. (2001).
  17. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990], Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, ISBN 0-262-03293-7 
  18. ^ Zhang et al. (1994).
  19. ^ Golumbic & Shamir (1993).
  20. ^ Villanger et al. (2009).
  21. ^ Bliznets et al. (2014).
  22. ^ Bodlaender (1998).

参考文献

  • Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; Naor, Joseph (Seffi); Schieber, Baruch (2001), “A unified approach to approximating resource allocation and scheduling”, Journal of the ACM 48 (5): 1069–1090, doi:10.1145/502102.502107, http://portal.acm.org/citation.cfm?id=335410&coll=portal&dl=ACM .
  • Bliznets, Ivan; Fomin, Fedor V.; Pilipczuk, Marcin; Pilipczuk, Michał (2014), “A subexponential parameterized algorithm for proper interval completion”, in Schulz, Andreas S.; Wagner, Dorothea, Proceedings of the 22nd Annual European Symposium on Algorithms (ESA 2014), Wroclaw, Poland, September 8-10, 2014, Lecture Notes in Computer Science, 8737, Springer-Verlag, pp. 173–184, arXiv:1402.3473, doi:10.1007/978-3-662-44777-2_15, ISBN 978-3-662-44776-5 .
  • Bodlaender, Hans L. (1998), “A partial k-arboretum of graphs with bounded treewidth”, Theoretical Computer Science 209 (1–2): 1–45, doi:10.1016/S0304-3975(97)00228-4 .
  • Booth, K. S.; Lueker, G. S. (1976), “Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms”, J. Comput. Syst. Sci. 13 (3): 335–379, doi:10.1016/S0022-0000(76)80045-1 .
  • Brandstädt, A.; Le, V.B.; Spinrad, J.P. (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X .
  • Cohen, Joel E. (1978), Food webs and niche space, Monographs in Population Biology, 11, Princeton, NJ: Princeton University Press, ISBN 978-0-691-08202-8 
  • Corneil, Derek; Olariu, Stephan; Stewart, Lorna (2009), “The LBFS structure and recognition of interval graphs”, SIAM Journal on Discrete Mathematics 23 (4): 1905–1953 .
  • Eckhoff, Jürgen (1993), “Extremal interval graphs”, Journal of Graph Theory 17 (1): 117–127, doi:10.1002/jgt.3190170112 .
  • Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), “Claw-free graphs — A survey”, Discrete Mathematics 164 (1–3): 87–147, doi:10.1016/S0012-365X(96)00045-3, MR1432221 .
  • Fishburn, Peter C. (1985), Interval orders and interval graphs: A study of partially ordered sets, Wiley-Interscience Series in Discrete Mathematics, New York: John Wiley & Sons 
  • Fulkerson, D. R.; Gross, O. A. (1965), “Incidence matrices and interval graphs”, Pacific Journal of Mathematics 15 (3): 835–855, doi:10.2140/pjm.1965.15.835 .
  • Gardi, Frédéric (2007), “The Roberts characterization of proper and unit interval graphs”, Discrete Mathematics 307 (22): 2906–2908, doi:10.1016/j.disc.2006.04.043, http://www.sciencedirect.com/science/article/pii/S0012365X07000696 .
  • Gilmore, P. C.; Hoffman, A. J. (1964), “A characterization of comparability graphs and of interval graphs”, Can. J. Math. 16: 539–548, doi:10.4153/CJM-1964-055-5 .
  • Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7 .
  • Golumbic, Martin Charles; Shamir, Ron (1993), “Complexity and algorithms for reasoning about time: a graph-theoretic approach”, J. Assoc. Comput. Mach. 40 (5): 1108–1133, doi:10.1145/174147.169675 .
  • Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), “Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing”, Theor. Comput. Sci. 234: 59–84, doi:10.1016/S0304-3975(97)00241-7, http://www.cs.colostate.edu/~rmm/lexbfs.ps .
  • Lekkerkerker, C.G.; Boland, J.C. (1962), “Representation of a finite graph by a set of intervals on the real line”, Fund. Math. 51: 45–64 .
  • McKee, Terry A.; McMorris, F.R. (1999), Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-430-3 .
  • Roberts, F. S. (1969), “Indifference graphs”, in Harary, Frank, Proof Techniques in Graph Theory, New York, NY: Academic Press, pp. 139–146, ISBN 978-0123242600, OCLC 30287853 .
  • Villanger, Yngve; Heggernes, Pinar; Paul, Christophe; Telle, Jan Arne (2009), “Interval Completion Is Fixed Parameter Tractable”, SIAM J. Comput. 38 (5): 2007–2020, doi:10.1137/070710913 .
  • Zhang, Peisen; Schon, Eric A.; Fischer, Stuart G.; Cayanis, Eftihia; Weiss, Janie; Kistler, Susan; Bourne, Philip E. (1994), “An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA”, Bioinformatics 10 (3): 309–317, doi:10.1093/bioinformatics/10.3.309 .

外部リンク

  • “interval graph”. Information System on Graph Classes and their Inclusions. 2019年3月2日閲覧。
  • Weisstein, Eric W. "Interval graph". mathworld.wolfram.com (英語).