弦グラフ

閉路（黒）と2本の弦（緑）で構成された、弦グラフの例。どちらかの弦を削除すると、弦を持たない長さ4の閉路が生まれるため、弦グラフではなくなる。

弦グラフとは、グラフ理論のグラフの一つであり、その内部に存在する長さの4以上の閉路全てが弦を持つようなグラフである。ここで、弦とは、閉路を構成しないが、閉路の2頂点をつなぐ辺である。また、誘導閉路グラフが常に3頂点の閉路となるようなグラフと同値である（4頂点以上の誘導グラフは閉路を持たないか、弦を持つ）。 他にも、弦グラフは「単体的頂点 (simplicial vertex) を順に除去することでグラフが除去できる、perfect elimination orderingという頂点の順序付けが可能である」「最小頂点分離(minimal separator)（グラフを全域グラフでなくするために除去する必要最小限なグラフ）がクリークである」「木の部分木の交差グラフ（英語版）」といった特徴も持つ。また、rigid circuit graphs[1]や、triangulated graph[2]とも呼ばれる。

弦グラフは完全グラフの部分グラフである。弦グラフを多項式時間で発見できることもあり、グラフ彩色のようなグラフ一般に対しては困難な問題も、弦グラフに対しては多項式時間で解ける場合もある。グラフの木幅(treewidth)は、それを含む弦グラフのクリークのサイズによって特徴づけられるかも知れない。

Perfect elimination とその効率的な導出

perfect elimination orderingとは、「隣接する頂点集合がクリークを形成しているグラフの頂点 v の削除」を繰り返し、グラフ全体が削除されるような順序付けである。グラフが弦グラフであれば、そしてその時に限りグラフはperfect elimination orderingを持つ[3]。

Rose, Lueker & Tarjan (1976) (see also Habib et al. 2000) は、Lexicographic Breadth First Search と呼ばれる辞書順に並べながら探索する手法で、効率的に弦グラフのperfect elimination orderingが見つかると示した。このアルゴリズムは、グラフの頂点を集合列に以下の手法で分割する。 まず、全ての頂点を含む1つの集合を考える。そして、一度も選ばれていない頂点を含む最初の集合 S から頂点 v を選び、S を「v に隣接している頂点」と「v に隣接していない頂点」の2つの集合に分割する。この分割を繰り返し、全ての頂点を一度ずつ選び終わったとき、perfect elimination orderingの逆の順に並ぶ。

lexicographic breadth first searchと、出力された順序がperfect elimination orderingかを確かめる処理は両方とも線形時間であるため、弦グラフに対して線形時間で処理可能である。弦グラフに対するprobe graph problemは多項式時間で解ける[4]一方、弦グラフに対するGraph sandwich problemはNP完全である[5]。

弦グラフに対する全てのperfect elimination ordering集合は反マトロイド(antimatroid)の基としてモデル化できる。例えば、Chandran et al. (2003)は与えられた弦グラフの全てのperfect elimination orderingsを効率的に列挙するアルゴリズムの一部として、反マトロイドへのこの接続を使いた。

極大クリークとグラフ彩色

perfect elimination orderingは、多項式時間で弦グラフの最大クリーク問題にも応用できる。最大クリーク問題は一般のグラフに対してはNP完全である。より一般には、弦グラフは極大クリークを高々頂点数に対して比例する数だけ持ちうるが、一般のグラフに対しては頂点数に対して極大クリークの個数は指数関数的に増大する。弦グラフの極大クリークを列挙するには、perfect elimination orderingを見つけ、その除去で用いるクリークが極大であるかを判定するだけである。

弦グラフのクリークは、双対弦グラフ（英語版）と呼ばれる[6]。

弦グラフがパーフェクトであるとき、極大クリークが最大クリークとなる。この時、クリークの頂点数はグラフの彩色数（頂点彩色）と等しくなる。また、弦グラフはperfect elimination orderingの逆順に頂点を選択して、貪欲法を用いることで最適な彩色が可能である[7]。

弦グラフの彩色多項式（英語版）は容易に計算できる。perfect elimination ordering v 1 , v 2 , … , v n {\displaystyle v_{1},v_{2},\ldots ,v_{n}} を導出し、Niをviまで削除した後のviの次数（隣接する頂点数）とする。例えば、最後の頂点に対するNであるNn、は他の頂点が除去された状態での隣接する頂点の数なので、Nn = 0である。彩色多項式は ( x − N 1 ) ( x − N 2 ) ⋯ ( x − N n ) {\displaystyle (x-N_{1})(x-N_{2})\cdots (x-N_{n})} であり、最終項は単にxであるため、この多項式はxで割り切れる。また、この性質は弦グラフの形から簡単に導ける。[8]

最小頂点分離

弦グラフに限らず、頂点分離（英語版）（vertex separator）とは、それらを除去すると残されたグラフが非連結となるような頂点集合を指す。最小頂点分離とは、頂点分離の部分集合が頂点分離とならない場合、その頂点分離を最小頂点分離と呼ぶ。弦グラフの頂点分離はクリークでありDirac (1961)、この性質は弦グラフがパーフェクトグラフである証明に使われた。

弦グラフの族は、A∪SとS∪Bは弦グラフである誘導部分グラフであり、Sはクリークであり、そしてA と B 間に辺が存在しないという3つを満たす、空集合ではない頂点集合A、S、Bに分割できるグラフとして再帰的に定義できる。つまり、クリークによって小さな部分グラフに再帰的に分解されるグラフである。このため、弦グラフは decomposable graphsとも呼ばれていた[9]。

部分木の交差グラフ

木（6頂点）の部分木（8頂点）を表す、8頂点の弦グラフ

1974年、Gavrilによって、部分木を用いた弦グラフの異なる定義が用いられた。

木の部分木の集合から、部分木ごとに1つの頂点と重複する2つの部分木を持つ交差グラフである「部分木グラフ」を定義できる。この「部分木グラフ」は弦グラフであることをGavrilは証明した。

部分木の交差として弦グラフを表すと、グラフの木幅がグラフ内の最大クリークのサイズより1小さい、木分解が生成される。任意のグラフG の木分解は弦グラフの部分グラフとしてGを表現したものとして捉えられる。グラフの木分解は、Junction tree algorithmの木分解でもある。

他のグラフとの関連

特別な弦グラフ（下位分類）

  • 区間グラフは道の部分木の交差グラフであり、木の特殊な場合である。したがって、弦グラフの一種である。
  • スプリットグラフは、あるグラフと、その補グラフがともに弦グラフであるようなグラフである。頂点数nが増加するにつれ、弦グラフがスプリットグラフである割合は1に近づくBender, Richmond & Wormald (1985).
  • プトレマイオスグラフは、弦グラフの内、Distance-hereditary graphでもあるものをいう。Distance-hereditary graphとは、2頂点間の距離が、その2頂点を含む任意の連結な誘導部分グラフにおいても変化しないグラフである。
    • 準閾値グラフはプトレマイオスグラフの一種であり、弦グラフであり、cographであるプトレマイオスグラフをいう。
    • ブロックグラフもプトレマイオスグラフの一種であり、任意の2つの極大クリークが少なくとも1つの頂点を共有するようなグラフである。
      • 風車グラフはさらにそのブロックグラフの特殊な例であり、任意の2つの極大クリークの共有頂点がある1つの頂点であるようなグラフである。
  • 強弦グラフ（英語版）はn-sun (n>=3)グラフを誘導部分グラフとして持たない弦グラフである。ここで、 n-sun グラフとは、2n頂点からなるハミルトン閉路に、奇数個離れた頂点をつなぐ弦が1個しか含まれないないグラフである。頂点集合内には隣接する頂点が1組ずつしかないような2つの頂点集合に分けられるグラフでもある（その場合、閉路に対して奇数個目と偶数個目の頂点の集合となる。）。
  • K-木は全ての極大クリークと極大クリーク分離が同じサイズの弦グラフである[10]。
    • アポロニアンネットワークは、弦グラフである極大平面グラフもしくは平面グラフである3-木である[10]。
    • 極大外平面グラフは2-木のサブクラスであり、そのため弦グラフである。

弦グラフを含むグラフ（上位分類）

弦グラフは、パーフェクトグラフの一種である。 また、弦グラフは、弱弦グラフ、コップウィングラフ（英語版）、odd-hole-free graphs（誘導部分グラフに偶数頂点のハミルトン閉路が存在しないグラフ）、even-hole-free graph、Meyniel graphなどの特殊な場合でもある。 弦グラフは、odd-hole-free graphsでもeven-hole-free graphでもあるグラフである。

弦グラフは、strangulated graph（グラフ内に含まれるperipheral cycleが全て三角形であるようなグラフ。peripheral cyclesは閉路である誘導グラフの特殊な例である）Strangulated graphsは極大平面グラフと弦グラフのクリーク和（英語版）で形成される。それゆえに、strangulated graphは極大平面グラフを含む[11]。

弦化(Chordal completion)と木幅

任意のグラフGの弦化とは、Gを部分グラフとして持つような弦グラフである。最小弦化は複数のパラメータに従う計算複雑性を持ち、準指数時間で解くことができる[12][13]。 Gの木幅はクリークのサイズが最小となるような弦化が施されたGの最大クリークの頂点数-1である。 k-木は木幅をkより大きくしなければ辺を追加できないグラフである。したがって、k-木はそれ自身の弦化であり、弦グラフの一種である。弦化は他のグラフの特徴付にも使われる[14]。

脚注

  1. ^ Dirac (1961)
  2. ^ Weisstein, Eric W. "Triangulated Graph". mathworld.wolfram.com (英語).
  3. ^ Fulkerson & Gross (1965).
  4. ^ Berry, Golumbic & Lipshteyn (2007).
  5. ^ Bodlaender, Fellows & Warnow (1992).
  6. ^ Szwarcfiter & Bornstein (1994).
  7. ^ Maffray (2003).
  8. ^ 例えば, Agnarsson (2003)のRemark 2.5が有名である。
  9. ^ Peter Bartlett. “Undirected Graphical Models: Chordal Graphs, Decomposable Graphs, Junction Trees, and Factorizations:”. 2019年3月1日閲覧。
  10. ^ a b Patil (1986)
  11. ^ Seymour & Weaver (1984).
  12. ^ Kaplan, Shamir & Tarjan (1999).
  13. ^ Fomin & Villanger (2013).
  14. ^ Parra & Scheffler (1997).

参考文献

  • Agnarsson, Geir (2003), “On chordal graphs and their chromatic polynomials”, Mathematica Scandinavica 93 (2): 240–246, MR2009583, http://www.mscand.dk/article/view/14421 .
  • Bender, E. A.; Richmond, L. B.; Wormald, N. C. (1985), “Almost all chordal graphs split”, J. Austral. Math. Soc., A 38 (2): 214–221, doi:10.1017/S1446788700023077, MR0770128 .
  • Berry, Anne; Golumbic, Martin Charles; Lipshteyn, Marina (2007), “Recognizing chordal probe graphs and cycle-bicolorable graphs”, SIAM Journal on Discrete Mathematics 21 (3): 573–591, doi:10.1137/050637091 .
  • Bodlaender, H. L.; Fellows, M. R.; Warnow, T. J. (1992), “Two strikes against perfect phylogeny”, Proc. of 19th International Colloquium on Automata Languages and Programming, Lecture Notes in Computer Science, 623, pp. 273–283, doi:10.1007/3-540-55719-9_80 .
  • Chandran, L. S.; Ibarra, L.; Ruskey, F.; Sawada, J. (2003), “Enumerating and characterizing the perfect elimination orderings of a chordal graph”, Theoretical Computer Science 307 (2): 303–317, doi:10.1016/S0304-3975(03)00221-4, http://www.cis.uoguelph.ca/~sawada/papers/chordal.pdf .
  • Dirac, G. A. (1961), “On rigid circuit graphs”, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 25: 71–76, doi:10.1007/BF02992776, MR0130190 .
  • Fomin, Fedor V.; Villanger, Yngve (2013), “Subexponential Parameterized Algorithm for Minimum Fill-In”, SIAM J. Comput. 6: 2197–2216, arXiv:1104.2230, doi:10.1137/11085390X .
  • Fulkerson, D. R.; Gross, O. A. (1965), “Incidence matrices and interval graphs”, Pacific J. Math. 15: 835–855, doi:10.2140/pjm.1965.15.835, http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1102995572 .
  • Gavril, Fănică (1974), “The intersection graphs of subtrees in trees are exactly the chordal graphs”, Journal of Combinatorial Theory, Series B 16: 47–56, doi:10.1016/0095-8956(74)90094-X .
  • Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press .
  • 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”, Theoretical Computer Science 234: 59–84, doi:10.1016/S0304-3975(97)00241-7, http://www.cs.colostate.edu/~rmm/lexbfs.ps .
  • Kaplan, Haim; Shamir, Ron; Tarjan, Robert (1999), “Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs”, SIAM J. Comput. 5: 1906–1922, doi:10.1137/S0097539796303044 .
  • Maffray, Frédéric (2003), “On the coloration of perfect graphs”, in Reed, Bruce A.; Sales, Cláudia L., Recent Advances in Algorithms and Combinatorics, CMS Books in Mathematics, 11, Springer-Verlag, pp. 65–84, doi:10.1007/0-387-22444-0_3, ISBN 0-387-95434-1 .
  • Parra, Andreas; Scheffler, Petra (1997), “Characterizations and algorithmic applications of chordal graph embeddings”, Discrete Applied Mathematics 79 (1-3): 171–188, doi:10.1016/S0166-218X(97)00041-3, MR1478250 .
  • Patil, H. P. (1986), “On the structure of k-trees”, Journal of Combinatorics, Information and System Sciences 11 (2–4): 57–64, MR966069 .
  • Rose, D.; Lueker, George; Tarjan, Robert E. (1976), “Algorithmic aspects of vertex elimination on graphs”, SIAM Journal on Computing 5 (2): 266–283, doi:10.1137/0205021 .
  • Seymour, P. D.; Weaver, R. W. (1984), “A generalization of chordal graphs”, Journal of Graph Theory 8 (2): 241–251, doi:10.1002/jgt.3190080206, MR742878 .
  • Szwarcfiter, J.L.; Bornstein, C.F. (1994), “Clique graphs of chordal and path graphs”, SIAM Journal on Discrete Mathematics 7: 331–336, doi:10.1137/s0895480191223191 .

外部リンク

  • Information System on Graph Class Inclusions: chordal graph
  • Weisstein, Eric W. "Chordal Graph". mathworld.wolfram.com (英語).