閾値グラフ

閾値グラフの例。

グラフ理論において、閾値グラフとは、次の 2 つの操作を繰り返し適用することで 1 頂点グラフから構築できるグラフです。

1. グラフに単一の孤立した頂点を追加します。
2. グラフに単一の支配頂点、つまり他のすべての頂点に接続された単一の頂点を追加します。

例えば、図のグラフは閾値グラフです。これは、単一頂点グラフ（頂点1）から始めて、黒の頂点を孤立頂点として、赤の頂点を支配頂点として、番号順に追加することで構築できます。

閾値グラフは、Chvátal & Hammer (1977) によって初めて導入されました。Golumbic (1980) には閾値グラフに関する章があり、Mahadev & Peled (1995) は閾値グラフに特化した書籍です。

代替定義

同等の定義は次のようになります。グラフが閾値グラフであるとは、実数が 個あり、各頂点に実頂点重みがあり、任意の 2 つの頂点について、が辺である場合に限ります。 ${\displaystyle S}$ ${\displaystyle v}$ ${\displaystyle w(v)}$ ${\displaystyle v,u}$ ${\displaystyle uv}$ ${\displaystyle w(u)+w(v)>S}$

もう一つの同等の定義は次の通りである。グラフが閾値グラフであるとは、実数があり、各頂点に対して実数の頂点重みがあり、任意の頂点集合に対して独立であるとき、そして次の場合に限って、${\displaystyle T}$ ${\displaystyle v}$ ${\displaystyle a(v)}$ ${\displaystyle X\subseteq V}$ ${\displaystyle X}$ ${\displaystyle \sum _{v\in X}a(v)\leq T.}$

「しきい値グラフ」という名前は、次の定義に由来しています。Sはエッジであるという特性の「しきい値」であり、同様に、Tは独立であるというしきい値です。

しきい値グラフには、禁止グラフ特性もあります。グラフがしきい値グラフとなるのは、その頂点のうち 4 つが3 辺パス グラフ、4 辺サイクル グラフ、または 2 辺マッチング である誘導サブグラフを形成しない場合のみです。

分解

頂点の繰り返し追加を用いる定義から、記号列を用いて閾値グラフを一意に記述する別の方法を導くことができる。これは、記号列の最初の文字である。 は常に文字列の最初の文字であり、グラフの最初の頂点を表す。後続の文字は であり、これは孤立頂点（または結合頂点）の追加を表す。また、 は支配頂点（または結合頂点）の追加を表す。例えば、文字列 は3つの葉を持つ星型グラフを表し、 は3つの頂点を持つパスを表す。図のグラフは次のように表すことができる。${\displaystyle \epsilon }$ ${\displaystyle u}$ ${\displaystyle j}$ ${\displaystyle \epsilon uuj}$ ${\displaystyle \epsilon uj}$ ${\displaystyle \epsilon uuujuuj}$

グラフと認識の関連クラス

閾値グラフは、コグラフ、分割グラフ、および自明に完全グラフの特殊なケースです。グラフが閾値グラフである場合、それはコグラフであり分割グラフでもあります。自明に完全グラフであり、かつ自明に完全グラフの補グラフであるすべてのグラフは、閾値グラフです。閾値グラフは、区間グラフの特殊なケースでもあります。これらすべての関係は、禁制の誘導部分グラフによる特徴付けで説明できます。コグラフは、4 つの頂点 P ₄に誘導パスがないグラフであり、閾値グラフは、誘導 P ₄、 C ₄、 2K ₂がないグラフです。 C ₄は、4 つの頂点のサイクルであり、 2K ₂はその補、つまり 2 つの互いに素な辺です。これは、閾値グラフが補集合を取る場合に閉じている理由も説明しています。 P ₄は自己補グラフであるため、グラフに P ₄ -、C ₄ -、および 2K _{2 -}が含まれない場合、その補グラフも同様に P 4 -、C 4 -、および 2K 2 -が含まれます。

Heggernes & Kratsch (2007) は、閾値グラフは線形時間で認識できることを示しました。グラフが閾値でない場合は、障害物 (P ₄、 C ₄、または 2K ₂のいずれか) が出力されます。

参照

• 無関心グラフ
• 直並列グラフ
• 閾値ハイパーグラフ^[1]

参考文献

1. ヤン・ライターマン;レードル、ヴォイチェヒ。シシャホバ、エディタ。トゥマ、ミロスラフ (1985-04-01)。 「閾値ハイパーグラフ」。離散数学。54 (2): 193–200。土井: 10.1016/0012-365X(85)90080-9。ISSN  0012-365X。

• Chvátal, Václav ; Hammer, Peter L. (1977)、「整数計画法における不等式の集約」、Hammer, PL; Johnson, EL; Korte, BH; et al. (eds.), Studies in Integer Programming (Proc. Worksh. Bonn 1975)、Annals of Discrete Mathematics、第1巻、アムステルダム：北ホラント、pp.  145– 162。
• ゴルビック、マーティン・チャールズ（1980）、アルゴリズムグラフ理論と完全グラフ、ニューヨーク：アカデミックプレス第2版​​、Annals of Discrete Mathematics、57、Elsevier、2004年。
• ヘガーネス、ピナール；クラッシュ、ディーター（2007）、「線形時間認証認識アルゴリズムと禁止誘導部分グラフ」（PDF）、Nordic Journal of Computing、14（1-2）：87-108（2008）、MR  2460558。
• Mahadev, NVR; Peled, Uri N. (1995),閾値グラフと関連トピック, Elsevier。

外部リンク

• しきい値グラフ、グラフ クラスとその包含に関する情報システム。