Loading article…
数学の一分野であるグラフ理論において、分割グラフは、頂点をクリークと独立集合に分割できるグラフである。分割グラフは、FöldesとHammer （1977a、1977b）によって最初に研究され 、TyshkevichとChernyak（1979）によって独立に導入され、彼らはこれらのグラフを「極グラフ」（ロシア語：полярные графы）と呼んだ。[1]
分割グラフには、クリークと独立集合への複数の分割が含まれる場合があります。たとえば、パスa – b – cは分割グラフであり、その頂点は次の 3 つの異なる方法で分割できます。
- クリーク{ a , b }と独立集合{ c }
- クリーク{ b , c }と独立集合{ a }
- クリーク{ b }と独立集合{ a , c }
分割グラフは、その禁止された誘導サブグラフの観点から特徴付けることができます。つまり、グラフが分割されるのは、4つまたは5つの頂点のサイクル、または互いに素な辺のペア（4サイクルの補数）の誘導サブグラフがない場合のみです。[ 2 ]
他のグラフファミリーとの関係
定義から、分割グラフは明らかに相補性の下で閉じている。[3]分割グラフの別の特徴付けは相補性を伴う。分割グラフは、その相補グラフも弦グラフである。[4]弦グラフがツリーのサブツリーの交差グラフであるのと同様に、分割グラフはスターグラフの異なるサブスターの交差グラフである。[5]ほぼすべての弦グラフは分割グラフである。つまり、n が無限大に近づくにつれて、分割されているn頂点弦グラフの割合は1 に近づく。 [6]
弦グラフは完全であるため、分割グラフも完全です。分割グラフから各頂点を 2 倍にして派生したグラフの族である二重分割グラフ(したがって、クリークは反マッチングを引き起こし、独立セットはマッチングを引き起こす) は、Chudnovsky ら (2006) による強完全グラフ定理の証明において、他のすべてのグラフを形成できる 5 つの基本完全グラフのクラスの 1 つとして重要な役割を果たしています。
グラフが分割グラフと区間グラフの両方である場合、その補グラフは分割グラフと比較可能性グラフの両方であり、その逆も同様です。分割比較可能性グラフ、およびしたがって分割区間グラフも、3つの禁止誘導サブグラフの集合によって特徴付けることができます。[7]分割コグラフは、まさに閾値グラフです。分割順列グラフは、まさに区間グラフ補グラフを持つ区間グラフです。[8]これらは、歪曲併合順列 の順列グラフです。[9]分割グラフの共彩色数は2です。
アルゴリズムの問題
G を分割グラフとし、クリークCと独立集合iに分割する。分割グラフ内の最大クリークはC自体かi内の頂点の近傍のいずれかとなる。したがって、分割グラフ内の最大クリーク、および補完的に最大独立集合を特定するのは簡単である。どの分割グラフでも、次の 3 つの可能性のいずれかが真である必要がある: [10]
- iにはC ∪ { x }が完全となるような頂点x が存在する。この場合、 C ∪ { x }は最大クリークであり、i は最大独立集合である。
- Cにはi ∪ { x }が独立となるような頂点x が存在する。この場合、 i ∪ { x }は最大独立集合であり、C は最大クリークである。
- C は最大クリークであり、iは最大独立集合です。この場合、G はクリークと独立集合への一意の分割( C、i )を持ち、 C は最大クリークであり、i は最大独立集合です。
グラフの色付けを含む、より一般的なグラフ族でNP完全である他のいくつかの最適化問題は、分割グラフでも同様に簡単です。ハミルトン閉路を見つけることは、強く弦のあるグラフである分割グラフの場合でもNP完全のままです。[11]最小支配集合問題が分割グラフに対してNP完全であることもよく知られています。[12]
度数列
分割グラフの注目すべき特性の1つは、次数列のみから認識できることです。グラフGの次数列をd 1 ≥ d 2 ≥ … ≥ d nとし、d i ≥ i – 1となるiの最大値mとします。このとき、 Gが分割グラフであるための必要条件は次の通り です。
この場合、最大次数を持つm個の頂点がG内で最大クリークを形成し、残りの頂点は独立集合を構成する。[13]
任意のグラフの分割率は、この不等式がどの程度成り立たないかを測る指標である。グラフが分割グラフでない場合、分割グラフになる最小のエッジ挿入および削除シーケンスは、次数が最大のm頂点間のすべての欠落エッジを追加し、残りの頂点のペア間のすべてのエッジを削除することで得られる。分割率は、このシーケンス内の操作の数を数える。[14]
分割グラフのカウント
ロイル (2000) は、(ラベルなしの) n頂点分割グラフが特定のスペルナー族と一対一に対応していることを示した。この事実を用いて、彼はn頂点上の非同型分割グラフの数の公式を決定した。n = 1から始まるnの小さな値に対して、これらの数は
- 1、2、4、9、21、56、164、557、2223、10766、64956、501696、...（OEISの配列A048194）。
この列挙結果は、以前にTyshkevich & Chernyak (1990) によっても証明されました。
注記
- ^ Földes & Hammer (1977a) はより一般的な定義を持っており、分割グラフと呼ばれるグラフには二部グラフ(つまり、2 つの独立した集合に分割できるグラフ) と二部グラフの補集合 (つまり、2 つのクリークに分割できるグラフ) も含まれていました。Földes & Hammer (1977b) はここで示した定義を使用しており、その後の文献でもこの定義が採用されています。たとえば、Brandstädt、Le & Spinrad (1999)、定義 3.2.3、p.41 などです。
- ^ フェルデスとハンマー (1977a); Golumbic (1980)、定理 6.3、p. 151.
- ^ ゴルンビック（1980）、定理6.1、p.150。
- ^ フェルデスとハンマー (1977a); Golumbic (1980)、定理 6.3、p. 151; Brandstädt、Le & Spinrad (1999)、定理 3.2.3、p. 41.
- ^ マクモリス＆シャイアー (1983);ヴォス (1985); Brandstädt、Le & Spinrad (1999)、定理 4.4.2、p. 52.
- ^ ベンダー、リッチモンド＆ワーモルド（1985年）。
- ^ フェルデスとハンマー (1977b); Golumbic (1980)、定理 9.7、212 ページ。
- ^ Brandstädt, Le & Spinrad (1999)、系7.1.1、p. 106、および定理7.1.2、p. 107。
- ^ Kézdy、Snevily、Wang（1996年）。
- ^ Hammer & Simeone (1981); Golumbic (1980)、定理6.2、p.150。
- ^ ミュラー（1996）
- ^ ベルトッシ（1984）
- ^ Hammer & Simeone (1981); Tyshkevich (1980); Tyshkevich、Melnikow、Kotov (1981); Golumbic (1980)、定理 6.7 および系 6.8、p. 154; Brandstädt、Le、Spinrad (1999)、定理 13.3.2、p. 203。Merris (2003) は、分割グラフの次数列をさらに調査しています。
- ^ ハマー＆シメオネ（1981年）。
参考文献
- Bender, EA; Richmond, LB; Wormald, NC (1985)、「ほとんどすべての弦グラフは分割される」、J. Austral. Math. Soc.、A、38 (2): 214–221、doi : 10.1017/S1446788700023077、MR 0770128。
- ベルトッシ、アラン A. (1984)、「分割グラフと二部グラフの支配集合」、情報処理レター、19 :37–40、doi :10.1016/0020-0190(84)90126-1。
- Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999)、「グラフクラス: 概観」、SIAM Monographs on Discrete Mathematics and Applications、ISBN 0-89871-432-X。
- チュドノフスキー、マリア;ロバートソン、ニール;シーモア、ポール;トーマス、ロビン(2006)、「強い完全グラフ定理」、Annals of Mathematics、164 (1): 51–229、arXiv : math/0212070、doi :10.4007/annals.2006.164.51、MR 2233847。
- 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。
- フォルデス、ステファン;ハンマー、ピーター・ラディスロー(1977b)、「ディルワース数 2 を持つ分割グラフ」、カナダ数学ジャーナル、29 (3): 666–672、doi : 10.4153/CJM-1977-069-1、MR 0463041。
- ゴルビック、マーティン・チャールズ（1980）、アルゴリズムグラフ理論と完全グラフ、アカデミックプレス、ISBN 0-12-289260-7、MR 0562306。
- Hammer, Peter Ladislaw ; Simeone, Bruno (1981)、「グラフの分割」、Combinatorica、1 (3): 275–284、doi :10.1007/BF02579333、MR 0637832。
- Kézdy, André E.; Snevily, Hunter S.; Wang, Chi (1996)、「順列を増加および減少サブシーケンスに分割する」、Journal of Combinatorial Theory、Series A、73 (2): 353–359、doi : 10.1016/S0097-3165(96)80012-4、MR 1370138。
- マクモリス、FR; Shier、DR (1983)、「 K 1, nでの弦グラフの表現」、Commentationes Mathematicae Universitatis Carolinae、24 : 489–494、MR 0730144。
- メリス、ラッセル (2003)、「分割グラフ」、ヨーロッパ組合せ論ジャーナル、24 (4): 413–430、doi : 10.1016/S0195-6698(03)00030-1、MR 1975945。
- ミュラー、ハイコ（1996）、「弦二部グラフのハミルトン回路」、離散数学、156：291-298、doi：10.1016/0012-365x（95）00057-4。
- Royle, Gordon F. (2000)、「セットカバーと分割グラフのカウント」(PDF)、Journal of Integer Sequences、3 (2): 00.2.6、MR 1778996。
- Tyshkevich, Regina I. (1980)、「グラフの標準分解」、Doklady Akademii Nauk SSSR (ロシア語)、24 : 677–679、MR 0587712
- ティシュケビッチ、レジーナ I. ; Chernyak、AA (1979) 、 「頂点の次数によって定義されるグラフの正規分割」アカド。ナウク BSSR、Ser.図-マット。ナウク(ロシア語)、5 : 14–26、MR 0554162。
- ティシュケビッチ、レジーナ I. ;チェルニャック、AA (1990)、Еще один метод перечисления непомеченных комбинаторных объектов、Mat。ザメトキ(ロシア語)、48 (6): 98–105、MR 1102626. 「マークされていない組み合わせオブジェクトを列挙するさらに別の方法」と翻訳（1990年）、ソ連科学アカデミーの数学ノート 48（6）：1239–1245、doi：10.1007 / BF01240267。
- Tyshkevich, Regina I. ; Melnikow, OI; Kotov, VM (1981)、「グラフと次数列について: 標準分解」、Kibernetika (ロシア語)、6 : 5–8、MR 0689420。
- ヴォス、H.-J. (1985)、「McMorris と Shier の論文に関するメモ」、Commentationes Mathematicae Universitatis Carolinae、26 : 319–322、MR 0803929。
さらに読む
- 分割グラフに関する章は、 Martin Charles Golumbicの著書「Algorithmic Graph Theory and Perfect Graphs」に掲載されています。