円弧グラフ（左）とそれに対応する円弧モデル（右）。 グラフ理論 において、円弧グラフ とは、円上の弧 の集合の交差グラフ のことである。このグラフは、集合内の各弧に対応する頂点 を1つ持ち、交差する弧に対応する頂点のペア間には辺が存在する。
正式には、
私 1 、 私 2 、 … 、 私 n ⊂ C 1 {\displaystyle I_{1},I_{2},\ldots ,I_{n}\subset C_{1}} 弧の集合とする。すると、対応する円弧グラフはG = ( V , E )となる。
V = { 私 1 、 私 2 、 … 、 私 n } {\displaystyle V=\{I_{1},I_{2},\ldots ,I_{n}\}} そして
{ 私 α 、 私 β } ∈ E ⟺ 私 α ∩ 私 β ≠ ∅ 。 {\displaystyle \{I_{\alpha },I_{\beta }\}\in E\iff I_{\alpha }\cap I_{\beta }\neq \varnothing .} Gに対応する弧の集合を弧モデル と呼ぶ。
認識 タッカー（1980） は、円弧グラフの最初の多項式認識アルゴリズムを実証した。O （ n 3 ） {\displaystyle {\mathcal {O}}(n^{3})} マコーネル（2003） は最初の線形（ O （ n + m ） ） {\displaystyle ({\mathcal {O}}(n+m))} m {\displaystyle m} [ 1 ]
他のグラフクラスとの関係 円弧グラフは、区間グラフ の自然な一般化です。円弧グラフG の円弧モデルが円の一部の点を覆っていない場合、その点で円を切り取って線に引き伸ばすと、区間表現が得られます。ただし、区間グラフとは異なり、円弧グラフは必ずしも完全ではありません。例えば 、 奇数の弦のないサイクルC5 、C7 など は円弧グラフです。
いくつかのサブクラス 以下では、G = （ V 、 E ） {\displaystyle G=(V,E)}
単位円弧グラフ G {\displaystyle G} 単位円弧グラフ である。
n 個の頂点を持つラベル付き単位円弧グラフの数は、次式で与えられる。（ n + 2 ） （ 2 n − 1 n − 1 ） − 2 2 n − 1 {\displaystyle (n+2){\binom {2n-1}{n-1}}-2^{2n-1}} 2 ]
適切な円弧グラフ G {\displaystyle G} 対応する弧モデルが存在し、どの弧も他の弧を適切に含まない場合、それは適切な円弧グラフ（ 円区間グラフ とも呼ばれる）[ 3 ] （ O （ n + m ） ） {\displaystyle ({\mathcal {O}}(n+m))} [ 4 ] これらは、爪のないグラフ の基本的なサブクラスの 1 つを形成します。[ 3 ]
ヘリー円弧グラフ G {\displaystyle G} ヘリー族を構成する場合 、ヘリー円弧グラフ である。 ガヴリル（1974）は このクラスの特徴付けを与え、O （ n 3 ） {\displaystyle {{\mathcal {O}}(n^{3})}}
Joeris ら (2009) は、 このクラスの別の特徴付けを示しており、入力がグラフの場合、O(n+m) の 時間で実行される認識アルゴリズムを示唆している。入力グラフが Helly 円弧グラフでない場合、アルゴリズムは禁止誘導部分グラフの形でその事実の証明書を返す。また、与えられた円弧モデルが Helly 特性を持つかどうかを判定するO(n)時間のアルゴリズムも示している。
アプリケーション 円弧グラフは、オペレーションズリサーチ における周期的な資源配分 問題をモデル化する際に有用である。各区間は、特定の期間における資源要求が時間的に繰り返されることを表す。
注記 ↑ Kaplan, Haim; Nussbaum, Yahav (2011-11-01). "A Simpler Linear-Time Recognition of Circular-Arc Graphs". Algorithmica . 61 (3): 694– 737. CiteSeerX 10.1.1.76.2480 . doi : 10.1007/s00453-010-9432-y . ISSN 0178-4617 . ↑ Alexandersson, Per; Panova, Greta (2018 年 12 月). "LLT 多項式、彩色準対称関数、およびサイクルを持つグラフ". Discrete Mathematics . 341 (12): 3453– 3482. arXiv : 1705.10353 . doi : 10.1016/j.disc.2018.09.001 . 1 2 Chudnovsky & Seymour (2008) によって異なるが同等の定義で説明されている。 ↑ Deng、Hell 、 Huang (1996) ページ ?
参考文献 Chudnovsky, Maria ; Seymour, Paul (2008)、「爪のないグラフ III. 円形区間グラフ」(PDF) 、Journal of Combinatorial Theory 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/S0097539792269095Gavril, Fanica (1974)、「円弧グラフ上のアルゴリズム」、Networks 、4 (4): 357–369 、doi : 10.1002/net.3230040407 ゴルンビック、マーティン・チャールズ (1980)、『アルゴリズム的グラフ理論と完全グラフ』 、アカデミック・プレス、ISBN 978-0-444-51530-8 2010年5月22日にオリジナルからアーカイブされ、 2008年5月21日に 取得されました。 Annals of Discrete Mathematics 57、Elsevier、2004年。Joeris, Benson L.; Lin, Min Chih; McConnell, Ross M.; Spinrad, Jeremy P.; Szwarcfiter, Jayme L. (2009), "Helly Circular-Arc Models and Graphs の線形時間認識", 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
外部リンク 円弧グラフ、グラフクラスの包含関係に基づく情報システム 
