円弧グラフ

円弧グラフ (左) と対応する円弧モデル (右)。

グラフ理論において、円弧グラフとは、円周上の弧の集合の交差グラフです。集合内の弧ごとに1つの頂点を持ち、交差する弧に対応する頂点のペアごとに 辺を持ちます。

正式には、

${\displaystyle I_{1},I_{2},\ldots ,I_{n}\subset C_{1}}$

円弧の集合とする。対応する円弧グラフはG = ( V ,  E )で、

${\displaystyle V=\{I_{1},I_{2},\ldots ,I_{n}\}}$

そして

${\displaystyle \{I_{\alpha},I_{\beta}\}\in E\iff I_{\alpha}\cap I_{\beta}\neq \varnothing .}$

G に対応する弧のファミリーは弧モデルと呼ばれます。

認識

Tucker (1980) は、円弧グラフに対する最初の多項式認識アルゴリズムを実証しました。これは時間で実行されます。McConnell (2003) は、最初の線形時間認識アルゴリズムを提示しました。ここで、は辺の数です。最近では、Kaplan と Nussbaum ^[1]がより単純な線形時間認識アルゴリズムを開発しました。 ${\displaystyle {\mathcal {O}}(n^{3})}$ ${\displaystyle ({\mathcal {O}}(n+m))}$ ${\displaystyle m}$

他のグラフクラスとの関係

円弧グラフは区間グラフの自然な一般化である。円弧グラフG が円の一部の点を覆わない円弧モデルを持つ場合、その点で円を切断し、直線まで引き伸ばすことで区間表現が得られる。しかし、区間グラフとは異なり、円弧グラフは常に完全とは限らない。奇弦閉路C ₅、C ₇などは円弧グラフである。

いくつかのサブクラス

以下では、任意のグラフを とします。 ${\displaystyle G=(V,E)}$

単位円弧グラフ

${\displaystyle G}$ 各弧の長さが等しい対応する弧モデルが存在する場合、グラフ は単位円弧グラフです。

n頂点のラベル付き単位円弧グラフの数はで与えられる。 ^[2]${\displaystyle (n+2){\binom {2n-1}{n-1}}-2^{2n-1}}$

真円弧グラフ

${\displaystyle G}$ 対応する弧モデルが存在し、どの弧も他の弧を適切に包含しないとき、真円弧グラフ（円弧区間グラフとも呼ばれる）^[3]は真円弧グラフである。これらのグラフの認識と真円弧モデルの構築はどちらも線形時間で実行できる。^{[4]これらは}クローフリーグラフ の基本的なサブクラスの1つを形成する。^[3]${\displaystyle ({\mathcal {O}}(n+m))}$

ヘリー円弧グラフ

${\displaystyle G}$ 対応する弧モデルが存在し、その弧がHelly族を構成する場合、Helly円弧グラフである。Gavril (1974)は、このクラスの特徴づけを行い、認識アルゴリズムを示唆している。 ${\displaystyle {{\mathcal {O}}(n^{3})}}$

Joerisら (2009) はこのクラスの他の特徴付けを示しており、入力がグラフである場合にO(n+m)時間で実行される認識アルゴリズムを示唆している。入力グラフがHelly円弧グラフでない場合、このアルゴリズムは禁制誘導部分グラフの形でその事実の証明を返す。彼らはまた、与えられた円弧モデルがHelly特性を持つかどうかを判定する O(n)時間アルゴリズムも提示した。

アプリケーション

円弧グラフは、オペレーションズ・リサーチにおける周期的な資源配分問題をモデル化する際に役立ちます。各区間は、特定の期間における資源の要求を時間的に繰り返し表します。

注記

1. Kaplan, Haim; Nussbaum, Yahav (2011-11-01). 「円弧グラフのよりシンプルな線形時間認識」. Algorithmica . 61 (3): 694– 737. CiteSeerX  10.1.1.76.2480 . doi :10.1007/s00453-010-9432-y. ISSN  0178-4617.
2. Alexandersson, Per; Panova, Greta (2018年12月). 「LLT多項式、彩色準対称関数、サイクル付きグラフ」.離散数学. 341 (12): 3453– 3482. arXiv : 1705.10353 . doi :10.1016/j.disc.2018.09.001.
3. Chudnovsky & Seymour (2008) による異なるが同等の定義で説明されている。
4. Deng、Hell、Huang (1996) pg. ?

参考文献

• マリア・チュドノフスキー、ポール・シーモア(2008)、「クローフリーグラフ。III. 円形区間グラフ」（PDF）、Journal of Combinatorial Theory、シリーズB、98 (4): 812– 834、doi : 10.1016/j.jctb.2008.03.001、MR  2418774。
• Deng, Xiaotie; Hell, Pavol ; Huang, Jing (1996)、「適切な円弧グラフと適切な区間グラフの線形時間表現アルゴリズム」、SIAM Journal on Computing、25 (2): 390– 403、doi :10.1137/S0097539792269095。
• ガブリル、ファニカ（1974）、「円弧グラフ上のアルゴリズム」、ネットワーク、4（4）：357–369、doi：10.1002/net.3230040407。
• ゴルンビック、マーティン・チャールズ（1980年）、アルゴリズムグラフ理論と完全グラフ、アカデミックプレス、ISBN 978-0-444-51530-8、2010年5月22日にオリジナルからアーカイブされ、2008年5月21日に取得. 第2版、Annals of Discrete Mathematics 57、Elsevier、2004年。
• Joeris, Benson L.; Lin, Min Chih; McConnell, Ross M.; Spinrad, Jeremy P.; Szwarcfiter, Jayme L. (2009)「Helly円弧モデルとグラフの線形時間認識」、Algorithmica、59 (2): 215– 239、CiteSeerX  10.1.1.298.3038、doi :10.1007/s00453-009-9304-5。
• McConnell, Ross (2003)、「円弧グラフの線形時間認識」、Algorithmica、37 (2): 93– 147、CiteSeerX  10.1.1.22.4725、doi :10.1007/s00453-003-1032-7。
• タッカー、アラン（1980）、「円弧グラフの効率的なテスト」、SIAM Journal on Computing、9（1）：1– 24、doi：10.1137/0209001。

外部リンク

• 円弧グラフ、グラフクラス包含に関する情報システム