無関心グラフ

数学の一分野であるグラフ理論において、無差別グラフは、各頂点に実数を割り当て、2つの頂点の数が互いに1単位以内である場合に、それらの頂点を辺で接続することによって構築される無向グラフです。^[1]無差別グラフは、単位間隔の集合、または適切にネストされた間隔（どの間隔も他の間隔を含まない間隔）の交差グラフでもあります。これらの2種類の間隔表現に基づいて、これらのグラフは単位間隔グラフまたは適切な間隔グラフとも呼ばれ、間隔グラフのサブクラスを形成します。

同等の特徴

有限無差別グラフは次のように特徴付けられる。

単位区間の交差グラフ、[ ^1]
2つの区間が入れ子になっていない（一方が他方を包含していない）区間集合の交差グラフ、^[1]^[2]
クローフリー区間グラフ、^[1]^[2]
クローK _{1,3 、ネット（各頂点に隣接する次数1の頂点を持つ三角形）、サン（中央の三角形と1辺を共有する3つ}の三角形に囲まれた三角形）、ホール（長さ4以上のサイクル）と同型の誘導部分グラフを持たないグラフ、^[3]
半順序の非比較性グラフ、[ ^1]
3つの頂点が– – の順序で並んでいる場合、が辺であるならばも辺であり、も辺であるような線形順序を持つ無向グラフ^[4] $u$ $v$ $w$ $uw$ $uv$ $vw$
アストラルトリプルを持たないグラフ、すなわち3つの頂点が3番目の頂点を避ける経路でペアで接続され、3番目の頂点の2つの連続した隣接頂点を含まないグラフ、^[5]
各連結成分が、その成分の各最大クリークが連続したサブパスを形成するパスを含むグラフ、 ^[6]
頂点に番号を付けることによって、すべての最短経路が単調な数列を形成するグラフ[ 6 ^]
隣接行列を、各行と各列において行列の非ゼロ部分が行列の主対角線に隣接する連続した区間を形成するように順序付けることができるグラフ。 ^[7]
弦のない経路のべき乗の誘導部分グラフ。^[8]
葉の力は葉の根を持ち、それは幼虫である。^[8]

無限グラフの場合、これらの定義の一部が異なる場合があります。

プロパティ

無差別グラフは区間グラフの特殊なケースであるため、区間グラフのすべての特性を持ちます。特に、弦グラフと完全グラフの特殊なケースです。また、円グラフの特殊なケースでもありますが、これはより一般的な区間グラフには当てはまりません。

ランダムグラフのエルデシュ・レーニモデルでは、辺の数がより大幅に少ないグラフは高確率で無差別グラフとなるが、辺の数がより大幅に多いグラフは高確率で無差別グラフとはならない。^[9] $n$ $n^{2/3}$ $n^{2/3}$

任意のグラフのバンド幅は、サブグラフとしてを含む無差別グラフの最大クリークのサイズより 1 小さく、最大クリークのサイズを最小にするように選ばれます。^{[10]この特性は、}パス幅と区間グラフの間、およびツリー幅と弦グラフの間にある同様の関係に似ています。幅のより弱い概念であるクリーク幅は、無差別グラフ上では任意の大きさになることがあります。^{[11]ただし、}誘導サブグラフの下で閉じている無差別グラフの適切なサブクラスはすべて、クリーク幅が制限されています。^[12] $G$ $G$

連結された無差別グラフには必ずハミルトン路が存在する。^[13]無差別グラフがハミルトン閉路を持つのは、それが二重連結である場合のみである。^[14]

無差別グラフは再構成予想に従う。つまり、無差別グラフは頂点を削除した部分グラフによって一意に決定される。^[15]

アルゴリズム

高次元単位円グラフと同様に、出力グラフのサイズで測定される線形時間で、点の集合を無差別グラフに、または単位区間の集合を単位区間グラフに変換することができます。アルゴリズムは、点（または区間の中心）を最も近い小さい整数に切り捨て、ハッシュテーブルを使用して、丸められた整数が互いに1つの範囲内にあるすべての点のペアを見つけ（固定半径近傍問題）、丸められていない値も互いに1つの範囲内にあるペアの結果のリストをフィルタリングします。^[16]

与えられたグラフが無差別グラフであるかどうかを線形時間でテストすることは、PQ木を使ってグラフの区間表現を構築し、この表現から導かれる頂点順序が無差別グラフの特性を満たすかどうかをテストすることによって可能である。[ ^{4]また、無差別グラフの認識アルゴリズムを}弦グラフ認識アルゴリズムに基づいて構築することもできる。^[14]いくつかの代替線形時間認識アルゴリズムは、無差別グラフと区間グラフの関係ではなく、幅優先探索または辞書式幅優先探索に基づいている。 ^[17]^[18]^[19]^[20]

頂点が無差別グラフを表す数値（または区間表現の単位区間のシーケンス）によってソートされると、同じ順序付けを使用して、これらのグラフの最適なグラフカラーリングを見つけ、最短経路問題を解き、ハミルトン経路と最大マッチングを構築することができます。これらはすべて線形時間で行われます。 ^[4]ハミルトン閉路は、グラフの適切な区間表現から時間で見つけることができますが、^[13]グラフ自体が入力として与えられると、同じ問題が区間グラフに一般化できる線形時間解を受け入れます。^[21]^[22] $O(n\log n)$

リストカラーリングは、無差別グラフに制限された場合でもNP完全性を維持する。 ^[23]しかし、入力に含まれる色の総数によってパラメータ化された場合、固定パラメータで扱いやすくなる。 ^[12]

アプリケーション

数理心理学では、無差別グラフは効用関数から生じ、関数をスケーリングして、1単位が個人が無関心であると想定できるほど小さい効用の差を表すようにする。この応用では、効用の差が大きいアイテムのペアは、効用の相対的な順序によって部分的に順序付けされ、半順序付けされる。^[1]^[24]

バイオインフォマティクスでは、色付きグラフを適切に色付けされた単位間隔グラフに拡張する問題は、完全な消化物からのDNA 配列アセンブリにおける偽陰性の検出をモデル化するために使用できます。^[25]

参照

閾値グラフ、ラベルの差ではなく頂点ラベルの合計によってエッジが決定されるグラフ
自明に完全なグラフ、区間のペアがすべて適切に交差するのではなく、入れ子になっているか、または互いに素である区間グラフ
単位円グラフ、無差別グラフの2次元版

参考文献

^ abcdef Roberts, Fred S. (1969)、「無差別グラフ」、グラフ理論の証明技法 (第 2 回アナーバーグラフ理論会議議事録、ミシガン州アナーバー、1968 年)、Academic Press、ニューヨーク、pp. 139–146、MR 0252267。
^ ab ボガート、ケネス P.;ウェスト、ダグラス B. (1999)、「「固有 = 単位」の短い証明」"、離散数学、201（1–3）：21–23、arXiv：math / 9811036、doi：10.1016 / S0012-365X（98）00310-0、MR 1687858。
^ Wegner, G. (1967)、Eigenschaften der Nerven homologisch-einfacher Familien im R ⁿ、Ph.D.論文、ドイツ、ゲッティンゲン: ゲッティンゲン大学Hell & Huang (2004) より引用。
^ abc Looges, Peter J.; Olariu, Stephan (1993)、「無差別グラフの最適貪欲アルゴリズム」、Computers & Mathematics with Applications、25 (7): 15–25、doi : 10.1016/0898-1221(93)90308-I、MR 1203643。
^ Jackowski, Zygmunt (1992)、「適切な区間グラフの新しい特徴付け」、離散数学、105 (1–3): 103–109、doi : 10.1016/0012-365X(92)90135-3、MR 1180196。
^ ab Gutierrez, M.; Oubiña, L. (1996)、「適切な区間グラフとツリークリークグラフのメトリック特性」、Journal of Graph Theory、21 (2): 199–205、doi :10.1002/(SICI)1097-0118(199602)21:2<199::AID-JGT9>3.0.CO;2-M、MR 1368745。
^ Mertzios, George B. (2008)、「区間グラフと固有区間グラフの行列特性」、応用数学レター、21 (4): 332–337、doi :10.1016/j.aml.2007.04.001、MR 2406509。
^ ab Brandstädt, Andreas; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010)、「ルート付き有向パスグラフはリーフパワーである」、Discrete Mathematics、310 : 897–910、doi : 10.1016/j.disc.2009.10.006。
^ コーエン、ジョエル E. (1982)、「ランダムグラフが単位間隔グラフ、無差別グラフ、または適切な間隔グラフである漸近確率」、離散数学、40 (1): 21–24、doi : 10.1016/0012-365X(82)90184-4、MR 0676708。
^ Kaplan, Haim; Shamir, Ron (1996)、「小さなクリークを持つ適切な区間グラフへのパス幅、帯域幅、および完了問題」、SIAM Journal on Computing、25 (3): 540–561、doi :10.1137/S0097539793258143、MR 1390027。
^ Golumbic, Martin Charles ; Rotics, Udi (1999)、「単位間隔グラフのクリーク幅は無制限である」、第 30 回南東部国際組合せ論、グラフ理論、コンピューティング会議の議事録 (フロリダ州ボカラトン、1999 年)、Congressus Numerantium、第 140 巻、pp. 5–17、MR 1745205。
^ ab Lozin, Vadim V. (2008)、「ツリー幅からクリーク幅へ: 単位間隔グラフの除外」、アルゴリズムと計算、Lecture Notes in Comput. Sci.、vol. 5369、Springer、ベルリン、pp. 871–882、doi :10.1007/978-3-540-92182-0_76、MR 2539978。
^ ab Bertossi, Alan A. (1983)、「適切な区間グラフにおけるハミルトン回路の検出」、Information Processing Letters、17 (2): 97–101、doi :10.1016/0020-0190(83)90078-9、MR 0731128。
^ ab Panda, BS; Das, Sajal K. (2003)、「適切な区間グラフの線形時間認識アルゴリズム」、Information Processing Letters、87 (3): 153–161、doi :10.1016/S0020-0190(03)00298-9、MR 1986780。
^ フォン・リムシャ、マイケル（1983）、「再構築可能性と完全グラフ」、離散数学、47（2–3）：283–291、doi：10.1016/0012-365X（83）90099-7、MR 0724667。
^ Bentley, Jon L. ; Stanat, Donald F.; Williams, E. Hollins Jr. (1977)、「固定半径近傍点の検出の複雑さ」、Information Processing Letters、6 (6): 209–212、doi :10.1016/0020-0190(77)90070-9、MR 0489084。
^ コルニール、デレク G. ; キム、ヒリョン; ナタラジャン、スリダル; オラリウ、ステファン; スプラーグ、アラン P. (1995)、「単位間隔グラフの単純な線形時間認識」、情報処理レター、55 (2): 99–104、CiteSeerX 10.1.1.39.855、doi :10.1016/0020-0190(95)00046-F、MR 1344787 。
^ エレーラ・デ・フィゲイレド、セリーナ・M.;ジョアン州メイダニス。 Picinin de Mello、Célia (1995)、「適切な間隔グラフ認識のための線形時間アルゴリズム」、Information Processing Letters、56 (3): 179–184、doi :10.1016/0020-0190(95)00133-W、MR 1365411。
^ コルニール、デレク G. (2004)、「単位間隔グラフの認識のための単純な 3 スイープ LBFS アルゴリズム」、離散応用数学、138 (3): 371–379、doi : 10.1016/j.dam.2003.07.001、MR 2049655。
^ Hell, Pavol ; Huang, Jing (2004)、「適切な区間グラフと適切な区間バイグラフの LexBFS 認識アルゴリズムの認定」、SIAM Journal on Discrete Mathematics、18 (3): 554–570、doi :10.1137/S0895480103430259、MR 2134416。
^ Keil, J. Mark (1985)、「区間グラフにおけるハミルトン回路の探索」、Information Processing Letters、20 (4): 201–206、doi :10.1016/0020-0190(85)90050-X、MR 0801816。
^ イバラ、ルイス (2009)、「適切な区間グラフでハミルトンサイクルを見つけるための簡単なアルゴリズム」、情報処理レター、109 (18): 1105–1108、doi :10.1016/j.ipl.2009.07.010、MR 2552898。
^ マルクス、ダニエル (2006)、「単位区間グラフの事前着色拡張」、離散応用数学、154 (6): 995–1002、doi : 10.1016/j.dam.2005.10.008、MR 2212549。
^ ロバーツ、フレッド S. (1970)、「非推移的無関心について」、数学心理学ジャーナル、7 : 243–258、doi :10.1016/0022-2496(70)90047-7、MR 0258486。
^ Goldberg, Paul W.; Golumbic, Martin C.; Kaplan, Haim; Shamir, Ron (2009)、「DNA の物理的マッピングに対する 4 つの打撃」、Journal of Computational Biology、2 (2)、doi :10.1089/cmb.1995.2.139、PMID 7497116。

外部リンク

グラフクラス包含に関する情報システム: 単位区間グラフ

[roberts-1] Roberts, Fred S. (1969)、「無差別グラフ」、グラフ理論の証明技法 (第 2 回アナーバーグラフ理論会議議事録、ミシガン州アナーバー、1968 年)、Academic Press、ニューヨーク、pp. 139–146、MR 0252267。

[bogart-west-2] ボガート、ケネス P.;ウェスト、ダグラス B. (1999)、「「固有 = 単位」の短い証明」"、離散数学、201（1–3）：21–23、arXiv：math / 9811036、doi：10.1016 / S0012-365X（98）00310-0、MR 1687858。

[3] Wegner, G. (1967)、Eigenschaften der Nerven homologisch-einfacher Familien im R ⁿ、Ph.D.論文、ドイツ、ゲッティンゲン: ゲッティンゲン大学Hell & Huang (2004) より引用。

[greedy-4] Looges, Peter J.; Olariu, Stephan (1993)、「無差別グラフの最適貪欲アルゴリズム」、Computers & Mathematics with Applications、25 (7): 15–25、doi : 10.1016/0898-1221(93)90308-I、MR 1203643。

[5] Jackowski, Zygmunt (1992)、「適切な区間グラフの新しい特徴付け」、離散数学、105 (1–3): 103–109、doi : 10.1016/0012-365X(92)90135-3、MR 1180196。

[metric-6] Gutierrez, M.; Oubiña, L. (1996)、「適切な区間グラフとツリークリークグラフのメトリック特性」、Journal of Graph Theory、21 (2): 199–205、doi :10.1002/(SICI)1097-0118(199602)21:2<199::AID-JGT9>3.0.CO;2-M、MR 1368745。

[7] Mertzios, George B. (2008)、「区間グラフと固有区間グラフの行列特性」、応用数学レター、21 (4): 332–337、doi :10.1016/j.aml.2007.04.001、MR 2406509。

[leafroot-8] Brandstädt, Andreas; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010)、「ルート付き有向パスグラフはリーフパワーである」、Discrete Mathematics、310 : 897–910、doi : 10.1016/j.disc.2009.10.006。

[9] コーエン、ジョエル E. (1982)、「ランダムグラフが単位間隔グラフ、無差別グラフ、または適切な間隔グラフである漸近確率」、離散数学、40 (1): 21–24、doi : 10.1016/0012-365X(82)90184-4、MR 0676708。

[10] Kaplan, Haim; Shamir, Ron (1996)、「小さなクリークを持つ適切な区間グラフへのパス幅、帯域幅、および完了問題」、SIAM Journal on Computing、25 (3): 540–561、doi :10.1137/S0097539793258143、MR 1390027。

[11] Golumbic, Martin Charles ; Rotics, Udi (1999)、「単位間隔グラフのクリーク幅は無制限である」、第 30 回南東部国際組合せ論、グラフ理論、コンピューティング会議の議事録 (フロリダ州ボカラトン、1999 年)、Congressus Numerantium、第 140 巻、pp. 5–17、MR 1745205。

[lozin-12] Lozin, Vadim V. (2008)、「ツリー幅からクリーク幅へ: 単位間隔グラフの除外」、アルゴリズムと計算、Lecture Notes in Comput. Sci.、vol. 5369、Springer、ベルリン、pp. 871–882、doi :10.1007/978-3-540-92182-0_76、MR 2539978。

[bertossi-13] Bertossi, Alan A. (1983)、「適切な区間グラフにおけるハミルトン回路の検出」、Information Processing Letters、17 (2): 97–101、doi :10.1016/0020-0190(83)90078-9、MR 0731128。

[pandas-14] Panda, BS; Das, Sajal K. (2003)、「適切な区間グラフの線形時間認識アルゴリズム」、Information Processing Letters、87 (3): 153–161、doi :10.1016/S0020-0190(03)00298-9、MR 1986780。

[15] フォン・リムシャ、マイケル（1983）、「再構築可能性と完全グラフ」、離散数学、47（2–3）：283–291、doi：10.1016/0012-365X（83）90099-7、MR 0724667。

[16] Bentley, Jon L. ; Stanat, Donald F.; Williams, E. Hollins Jr. (1977)、「固定半径近傍点の検出の複雑さ」、Information Processing Letters、6 (6): 209–212、doi :10.1016/0020-0190(77)90070-9、MR 0489084。

[17] コルニール、デレク G. ; キム、ヒリョン; ナタラジャン、スリダル; オラリウ、ステファン; スプラーグ、アラン P. (1995)、「単位間隔グラフの単純な線形時間認識」、情報処理レター、55 (2): 99–104、CiteSeerX 10.1.1.39.855、doi :10.1016/0020-0190(95)00046-F、MR 1344787 。

[18] エレーラ・デ・フィゲイレド、セリーナ・M.;ジョアン州メイダニス。 Picinin de Mello、Célia (1995)、「適切な間隔グラフ認識のための線形時間アルゴリズム」、Information Processing Letters、56 (3): 179–184、doi :10.1016/0020-0190(95)00133-W、MR 1365411。

[19] コルニール、デレク G. (2004)、「単位間隔グラフの認識のための単純な 3 スイープ LBFS アルゴリズム」、離散応用数学、138 (3): 371–379、doi : 10.1016/j.dam.2003.07.001、MR 2049655。

[20] Hell, Pavol ; Huang, Jing (2004)、「適切な区間グラフと適切な区間バイグラフの LexBFS 認識アルゴリズムの認定」、SIAM Journal on Discrete Mathematics、18 (3): 554–570、doi :10.1137/S0895480103430259、MR 2134416。

[21] Keil, J. Mark (1985)、「区間グラフにおけるハミルトン回路の探索」、Information Processing Letters、20 (4): 201–206、doi :10.1016/0020-0190(85)90050-X、MR 0801816。

[22] イバラ、ルイス (2009)、「適切な区間グラフでハミルトンサイクルを見つけるための簡単なアルゴリズム」、情報処理レター、109 (18): 1105–1108、doi :10.1016/j.ipl.2009.07.010、MR 2552898。

[23] マルクス、ダニエル (2006)、「単位区間グラフの事前着色拡張」、離散応用数学、154 (6): 995–1002、doi : 10.1016/j.dam.2005.10.008、MR 2212549。

[24] ロバーツ、フレッド S. (1970)、「非推移的無関心について」、数学心理学ジャーナル、7 : 243–258、doi :10.1016/0022-2496(70)90047-7、MR 0258486。

[25] Goldberg, Paul W.; Golumbic, Martin C.; Kaplan, Haim; Shamir, Ron (2009)、「DNA の物理的マッピングに対する 4 つの打撃」、Journal of Computational Biology、2 (2)、doi :10.1089/cmb.1995.2.139、PMID 7497116。