閾值圖

閾值圖的示例。

在圖理論中，閾值圖是一個圖形，可以通過以下兩個操作的重複應用從一個vertex圖構造：

  1. 將單個隔離頂點添加到圖中。
  2. 在圖中添加單個主導頂點，即連接到所有其他頂點的單個頂點。

例如，圖的圖是閾值圖。它可以通過以單個vertex圖（頂點1）開始構建，然後以孤立的頂點和紅色頂點添加黑色頂點作為主導頂點，並按編號的順序。

閾值圖首先由Chvátal＆Hammer（1977）引入。關於閾值圖的一章出現在Golumbic（1980）中，而Mahadev＆Peled（1995）的書則介紹了它們。

替代定義

等效的定義如下：如果有實際號碼，則圖是閾值圖對於每個頂點真正的頂點重量因此對於任何兩個頂點 ，，，， 當且僅當 。

另一個等效的定義是：如果有實際號碼，則圖是閾值圖對於每個頂點真正的頂點重量因此對於任何頂點集 ，，，， 當且僅當

名稱“閾值圖”來自以下定義： S是邊緣屬性的“閾值”，或者等效t是獨立的閾值。

閾值圖還具有禁止的圖表：圖形是一個閾值圖，並且僅當它的四個頂點沒有形成一個誘導的子圖，該子圖是一個三邊路徑圖，四個邊緣循環圖或兩個邊緣匹配。

分解

從使用頂點的重複添加的定義來看，可以通過一串符號來得出唯一的唯一描述閾值圖的方式。 始終是字符串的第一個字符，代表圖形的第一個頂點。隨後的每個字符是 ，它表示添加孤立的頂點（或聯合頂點）或 ，這表示添加主導頂點（或加入頂點）。例如，字符串代錶帶有三片葉子的星形圖，而代表三個頂點的路徑。圖的圖可以表示為

圖形和識別的相關類別

閾值圖是Cophaphs ，拆分圖和瑣碎完美的圖形的特殊情況。當且僅當它既是Cophaph和split圖）時，是一個閾值圖。每個圖形既是一個瑣碎的完美圖形，又是一個奇特完美的圖的互補圖都是閾值圖。閾值圖也是間隔圖的特殊情況。所有這些關係都可以通過禁止引起的子圖表來解釋它們的特徵。 Cophaph是在四個頂點，p 4上沒有誘導路徑的圖形，閾值圖是沒有誘導p 4 ，c 4和2k 2的圖形。 C 4是四個頂點的循環，而2K 2是其補體，即兩個不相交的邊緣。這也解釋了為什麼在補充中關閉閾值圖； p 4是自我平衡的，因此，如果圖為p 4- ，c 4-和2k 2 ，則它的補體也是如此。

Heggernes＆Kratsch（2007）表明，可以在線性時間內識別閾值圖。如果圖不是閾值，則將輸出障礙物（P 4 ，C 4或2K 2 ）。

也可以看看