弦グラフのソースを表示

[[Image:Chordal-graph.svg|thumb|220px|閉路（黒）と2本の弦（緑）で構成された、弦グラフの例。どちらかの弦を削除すると、弦を持たない長さ4の閉路が生まれるため、弦グラフではなくなる。]]
'''弦グラフ'''とは、[[グラフ理論]]のグラフの一つであり、その内部に存在する長さの4以上の[[閉路]]全てが'''弦'''を持つようなグラフである。ここで、閉路の'''弦'''とは、その閉路自体には含まれず、かつ、その閉路を構成する2頂点を両端点とする辺である。また、誘導閉路グラフが常に3頂点の閉路となるようなグラフと同値である（4頂点以上の誘導グラフは閉路を持たないか、弦を持つ）。 他にも、弦グラフは「単体的頂点 (simplicial vertex) を順に除去することでグラフが除去できる、[[perfect elimination ordering]]という頂点の順序付けが可能である」「最小頂点分離(minimal separator)（グラフを全域グラフでなくするために除去する必要最小限なグラフ）が[[クリーク (グラフ理論)|クリーク]]である」「木の部分木の{{仮リンク|交差グラフ|en|intersection graph}}」といった特徴も持つ。また、'''rigid circuit graphs'''<ref name="dirac">{{harvtxt|Dirac|1961}}</ref>や、'''triangulated graph'''<ref>{{mathworld | urlname = TriangulatedGraph | title = Triangulated Graph}}</ref>とも呼ばれる。

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

==Perfect elimination とその効率的な導出==
''perfect elimination ordering''とは、「隣接する頂点集合がクリークを形成しているグラフの頂点 ''v'' の削除」を繰り返し、グラフ全体が削除されるような順序付けである。グラフが弦グラフであれば、そしてその時に限りグラフはperfect elimination orderingを持つ{{sfnp|Fulkerson|Gross|1965}}。

{{harvtxt|Rose|Lueker|Tarjan|1976}} (see also {{harvnb|Habib|McConnell|Paul|Viennot|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は多項式時間で解ける{{sfnp|Berry|Golumbic|Lipshteyn|2007}}一方、弦グラフに対するGraph sandwich problemはNP完全である{{sfnp|Bodlaender|Fellows|Warnow|1992}}。

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

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

弦グラフのクリークは、{{仮リンク|双対弦グラフ|en|dually chordal graph}}と呼ばれる{{sfnp|Szwarcfiter|Bornstein|1994}}。

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

弦グラフの{{仮リンク|彩色多項式|en|chromatic polynomial}}は容易に計算できる。perfect elimination ordering <math>v_1,v_2,\ldots,v_n</math>を導出し、''N''<sub>''i''</sub>を''v''<sub>''i''</sub>まで削除した後の''v''<sub>''i''</sub>の次数（隣接する頂点数）とする。例えば、最後の頂点に対する''N''である''N''<sub>''n''</sub>、は他の頂点が除去された状態での隣接する頂点の数なので、''N''<sub>''n''</sub> = 0である。彩色多項式は<math>(x-N_1)(x-N_2)\cdots(x-N_n)</math>であり、最終項は単に''x''であるため、この多項式は''x''で割り切れる。また、この性質は弦グラフの形から簡単に導ける。<ref>例えば, {{harvtxt|Agnarsson|2003}}のRemark 2.5が有名である。</ref>

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

弦グラフの族は、''A''∪''S''と''S''∪''B''は弦グラフである誘導部分グラフであり、''S''はクリークであり、そして''A'' と ''B'' 間に辺が存在しないという3つを満たす、空集合ではない頂点集合''A''、''S''、''B''に分割できるグラフとして再帰的に定義できる。つまり、クリークによって小さな部分グラフに再帰的に分解されるグラフである。このため、弦グラフは '''decomposable graphs'''とも呼ばれていた<ref>{{cite web |url=http://www.stat.berkeley.edu/~bartlett/courses/241A-spring2007/graphnotes.pdf |title=Undirected Graphical Models: Chordal Graphs, Decomposable Graphs, Junction Trees, and Factorizations: | author=Peter Bartlett | accessdate=2019-03-01}}</ref>。

==部分木の交差グラフ==
[[Image:Tree decomposition.svg|thumb|木（6頂点）の部分木（8頂点）を表す、8頂点の弦グラフ]]
1974年、Gavrilによって、部分木を用いた弦グラフの異なる定義が用いられた。

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

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

==他のグラフとの関連==
===特別な弦グラフ（下位分類）===
* [[区間グラフ]]は道の部分木の交差グラフであり、木の特殊な場合である。したがって、弦グラフの一種である。

* [[スプリットグラフ]]は、あるグラフと、その補グラフがともに弦グラフであるようなグラフである。頂点数''n''が増加するにつれ、弦グラフがスプリットグラフである割合は1に近づく{{harvtxt|Bender|Richmond|Wormald|1985}}.

* [[プトレマイオスグラフ]]は、弦グラフの内、[[Distance-hereditary graph]]でもあるものをいう。[[Distance-hereditary graph]]とは、2頂点間の距離が、その2頂点を含む任意の連結な誘導部分グラフにおいても変化しないグラフである。
** [[準閾値グラフ]]はプトレマイオスグラフの一種であり、弦グラフであり、cographであるプトレマイオスグラフをいう。
** [[ブロックグラフ]]もプトレマイオスグラフの一種であり、任意の2つの極大クリークが少なくとも1つの頂点を共有するようなグラフである。
*** [[風車グラフ]]はさらにそのブロックグラフの特殊な例であり、任意の2つの極大クリークの共有頂点がある1つの頂点であるようなグラフである。

* {{仮リンク|強弦グラフ|en|Strongly chordal graph}}は''n''-sun (n>=3)グラフを誘導部分グラフとして持たない弦グラフである。ここで、 ''n''-sun グラフとは、2''n''頂点からなる[[ハミルトン閉路]]に、奇数個離れた頂点をつなぐ弦が1個しか含まれないないグラフである。頂点集合内には隣接する頂点が1組ずつしかないような2つの頂点集合に分けられるグラフでもある（その場合、閉路に対して奇数個目と偶数個目の頂点の集合となる。）。

* [[k-木|''K''-木]]は全ての極大クリークと極大クリーク分離が同じサイズの弦グラフである<ref name="patil86">{{harvtxt|Patil|1986}}</ref>。
** [[アポロニアンネットワーク]]は、弦グラフである極大平面グラフもしくは平面グラフである3-木である<ref name="patil86"/>。
** 極大[[外平面グラフ]]は2-木のサブクラスであり、そのため弦グラフである。

===弦グラフを含むグラフ（上位分類）===
弦グラフは、パーフェクトグラフの一種である。
また、弦グラフは、弱弦グラフ、{{仮リンク|コップウィングラフ|en|cop-win graph}}、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は極大平面グラフと弦グラフの{{仮リンク|クリーク和|en|clique-sum}}で形成される。それゆえに、strangulated graphは極大平面グラフを含む{{sfnp|Seymour|Weaver|1984}}。

==弦化(Chordal completion)と木幅==
任意のグラフ''G''の'''弦化'''とは、''G''を部分グラフとして持つような弦グラフである。最小弦化は複数のパラメータに従う計算複雑性を持ち、準指数時間で解くことができる{{sfnp|Kaplan|Shamir|Tarjan|1999}}{{sfnp|Fomin|Villanger|2013}}。
''G''の木幅はクリークのサイズが最小となるような弦化が施された''G''の最大クリークの頂点数-1である。
''k''-木は木幅を''k''より大きくしなければ辺を追加できないグラフである。したがって、''k''-木はそれ自身の弦化であり、弦グラフの一種である。弦化は他のグラフの特徴付にも使われる{{sfnp|Parra|Scheffler|1997}}。

==脚注==
{{Reflist|30em}}

==参考文献==
*{{citation
 | last = Agnarsson | first = Geir
 | issue = 2
 | journal = Mathematica Scandinavica
 | mr = 2009583
 | pages = 240–246
 | title = On chordal graphs and their chromatic polynomials
 | url = http://www.mscand.dk/article/view/14421
 | volume = 93
 | year = 2003}}.
*{{citation
 | last1 = Bender | first1 = E. A.
 | last2 = Richmond | first2 = L. B.
 | last3 = Wormald | first3 = N. C.
 | doi = 10.1017/S1446788700023077
 | mr = 0770128
 | issue = 2
 | journal = J. Austral. Math. Soc.
 | series = A
 | pages = 214–221
 | title = Almost all chordal graphs split
 | volume = 38
 | year = 1985}}.
*{{citation
 | last1 = Berry | first1 = Anne
 | last2 = Golumbic | first2 = Martin Charles | author2-link = Martin Charles Golumbic
 | last3 = Lipshteyn| first3 = Marina
 | title     = Recognizing chordal probe graphs and cycle-bicolorable graphs
 | journal   = [[SIAM Journal on Discrete Mathematics]]
 | volume    = 21
 | year      = 2007
 | pages     = 573–591
 | doi = 10.1137/050637091
 | issue = 3}}.
*{{citation
 | last1 = Bodlaender | first1 = H. L. | author1-link = Hans L. Bodlaender
 | last2 = Fellows | first2 = M. R. | author2-link = Michael Fellows
 | last3 = Warnow | first3 = T. J. | author3-link = タンディ・ワルノ
 | contribution = Two strikes against perfect phylogeny
 | doi = 10.1007/3-540-55719-9_80
 | pages = 273–283
 | series = Lecture Notes in Computer Science
 | title = [[International Colloquium on Automata, Languages and Programming|Proc. of 19th International Colloquium on Automata Languages and Programming]]
 | volume = 623
 | year = 1992}}.
*{{citation
 | last1 = Chandran | first1 = L. S.
 | last2 = Ibarra | first2 = L.
 | last3 = Ruskey | first3 = F. | author3-link = Frank Ruskey
 | last4 = Sawada | first4 = J.
 | doi = 10.1016/S0304-3975(03)00221-4
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | pages = 303–317
 | title = Enumerating and characterizing the perfect elimination orderings of a chordal graph
 | url = http://www.cis.uoguelph.ca/~sawada/papers/chordal.pdf
 | volume = 307
 | year = 2003
 | issue = 2}}.
*{{citation
 | last = Dirac | first = G. A. | authorlink = Gabriel Andrew Dirac
 | doi = 10.1007/BF02992776
 | mr = 0130190
 | journal = Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
 | pages = 71–76
 | title = On rigid circuit graphs
 | volume = 25
 | year = 1961}}.
*{{citation
 | last1 = Fomin | first1 = Fedor V.
 | last2 = Villanger | first2 = Yngve
 | journal = SIAM J. Comput.
 | pages = 2197–2216
 | title = Subexponential Parameterized Algorithm for Minimum Fill-In
 | volume = 6
 | year = 2013
 | doi=10.1137/11085390X| arxiv = 1104.2230}}.
*{{citation
 | last1 = Fulkerson | first1 = D. R. | author1-link = D. R. Fulkerson
 | last2 = Gross | first2 = O. A.
 | journal = Pacific J. Math.
 | pages = 835–855
 | title = Incidence matrices and interval graphs
 | url = http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1102995572
 | volume = 15
 | year = 1965 | doi=10.2140/pjm.1965.15.835}}.
*{{citation
 | last = Gavril | first = Fănică
 | doi = 10.1016/0095-8956(74)90094-X
 | journal = [[Journal of Combinatorial Theory]] | series = Series B
 | pages = 47–56
 | title = The intersection graphs of subtrees in trees are exactly the chordal graphs
 | volume = 16
 | year = 1974}}.
*{{citation
 |first=Martin Charles|last=Golumbic
 |authorlink=Martin Charles Golumbic
 |title=Algorithmic Graph Theory and Perfect Graphs
 |year=1980|publisher=Academic Press}}.
*{{citation
 | last1 = Habib | first1 = Michel
 | last2 = McConnell | first2 = Ross
 | last3 = Paul | first3 = Christophe
 | last4 = Viennot | first4 = Laurent
 | doi = 10.1016/S0304-3975(97)00241-7
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | pages = 59–84
 | title = Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing
 | url = http://www.cs.colostate.edu/~rmm/lexbfs.ps
 | volume = 234
 | year = 2000}}.
*{{citation
 | last1 = Kaplan | first1 = Haim
 | last2 = Shamir | first2 = Ron
 | last3 = Tarjan | first3 = Robert
 | journal = SIAM J. Comput.
 | pages = 1906–1922
 | title = Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
 | volume = 5
 | year = 1999 | doi=10.1137/S0097539796303044}}.
*{{citation
 | last = Maffray | first = Frédéric
 | contribution = On the coloration of perfect graphs
 | doi = 10.1007/0-387-22444-0_3
 | editor1-last = Reed | editor1-first = Bruce A. | editor1-link = Bruce Reed (mathematician)
 | editor2-last = Sales | editor2-first = Cláudia L.
 | pages = 65–84
 | publisher = Springer-Verlag
 | series = CMS Books in Mathematics
 | title = Recent Advances in Algorithms and Combinatorics
 | volume = 11
 | year = 2003
 | isbn = 0-387-95434-1}}.
*{{citation
 | last1 = Parra | first1 = Andreas
 | last2 = Scheffler | first2 = Petra
 | doi = 10.1016/S0166-218X(97)00041-3
 | issue = 1-3
 | journal = Discrete Applied Mathematics
 | mr = 1478250
 | pages = 171–188
 | title = Characterizations and algorithmic applications of chordal graph embeddings
 | volume = 79
 | year = 1997}}.
*{{citation
 | last = Patil | first = H. P.
 | mr = 966069
 | issue = 2–4
 | journal = Journal of Combinatorics, Information and System Sciences
 | pages = 57–64
 | title = On the structure of ''k''-trees
 | volume = 11
 | year = 1986}}.
*{{citation
 | last1 = Rose | first1 = D.
 | last2 = Lueker | first2 = George
 | last3 = Tarjan | first3 = Robert E. | author3-link = ロバート・タージャン
 | doi = 10.1137/0205021
 | journal = [[SIAM Journal on Computing]]
 | pages = 266–283
 | title = Algorithmic aspects of vertex elimination on graphs
 | volume = 5
 | year = 1976
 | issue = 2}}.
*{{citation
 | last1 = Seymour | first1 = P. D. | author1-link = Paul Seymour (mathematician)
 | last2 = Weaver | first2 = R. W.
 | doi = 10.1002/jgt.3190080206
 | issue = 2
 | journal = [[Journal of Graph Theory]]
 | mr = 742878
 | pages = 241–251
 | title = A generalization of chordal graphs
 | volume = 8
 | year = 1984}}.
*{{citation
 | last1 = Szwarcfiter | first1 = J.L. | author1-link = Jayme Luiz Szwarcfiter
 | last2 = Bornstein | first2 = C.F.
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | pages = 331–336
 | title = Clique graphs of chordal and path graphs
 | volume = 7
 | year = 1994 | doi=10.1137/s0895480191223191}}.

== 外部リンク ==
* [http://www.graphclasses.org/index.html Information System on Graph Class Inclusions]: [http://www.graphclasses.org/classes/gc_32.html chordal graph]
* {{mathworld | urlname = ChordalGraph | title = Chordal Graph}}

{{DEFAULTSORT:けんくらふ}}
[[Category:グラフ理論]]
[[Category:数学に関する記事]]