主題
Search

弦圖


弦圖是一個 簡單圖,其中每個長度為四或更大的 圖的環 都有一個 環的弦。換句話說,弦圖是一個沒有長度為四或更大的 無弦環 的圖(參見 West 2000, p. 225; Gross and Yellen 2006, p. 437)。

ChordalGraphs

節點數為 n=1, 2, ... 的簡單絃圖的數量分別為 1, 2, 4, 10, 27, 94, 393, ... (OEIS A048193)。上面展示了前幾個,儘管許多都是平凡的弦圖,因為它們沒有長度 >=4 的環。

ChordalGraphsConnected

相應的簡單連通弦圖的數量分別為 1, 1, 2, 5, 15, 58, 272, ... (OEIS A048192)。上面展示了前幾個,儘管許多再次只是平凡的弦圖。

分裂圖 是一個弦圖,其 圖的補圖 也是弦圖 (Royle 2000)。

每個弦圖都是 完美圖

線上性時間內識別弦圖是可能的。此外,可以在 多項式時間 內找到弦圖的最大團,儘管對於一般圖,這個問題是 NP-完全 的。

弦圖(沒有無弦環)與 無弦圖(沒有 )不是相同的(或相反的)。例如,方形圖 C_4無弦圖 但不是弦圖,鑽石圖四面體圖 K_4 是弦圖但不是 無弦圖,並且 空圖 K^__n, 路徑圖 P_n, 和 三角形圖 C_3 既是弦圖又是 無弦圖

弦圖的圖類包括 塊圖


另請參閱

仙人掌圖, 無弦環, 無弦圖, 環的弦, 圖的環, 完美圖, 托勒密圖, 分裂圖

使用 探索

參考文獻

Blair, J. R. S. 和 Peyton, B. W. "弦圖和團樹導論。" 在 圖論與稀疏矩陣計算 (Ed. A. George, J. R. Gilbert, 和 J. W. H. Liu)。紐約: Springer-Verlag, pp.1-29, 1993.Brandstadt, A.; Le, V. B.; 和 Spinrad, J. P. 圖類:綜述。 費城,賓夕法尼亞州: SIAM, 1999. Bulatov, Y. "Mathematica Bits: 弦圖包更新。" http://mathematica-bits.blogspot.com/2011/02/chordal-graph-usage.html.Gross, J. T. 和 Yellen, J. 圖論及其應用,第二版。 博卡拉頓,佛羅里達州: CRC Press, 2006.Habib, M.; McConnell, R.; Paul, C.; 和 Viennot, L. "Lex-BFS 和分割槽細化,及其在傳遞定向、區間圖識別和連續 1 測試中的應用。" Theoret. Comput. Sci. 234, 59-84, 2000.Rose, D.; Lueker, G.; 和 Tarjan, R. E. "圖上頂點消除的演算法方面。" SIAM J. Comput. 5, 266-283, 1976.Royle, G. F. "計數集合覆蓋和分裂圖。" J. Integer Seq. 3, Article 00.2.6, 2000. https://cs.uwaterloo.ca/journals/JIS/VOL3/ROYLE/royle.html.Sloane, N. J. A. 序列 A048192A048193 在 "整數序列線上百科全書" 中。West, D. B. "弦圖" 和 "弦圖再探"。 圖論導論,第二版。 恩格爾伍德懸崖,新澤西州: Prentice-Hall, pp. 224-226 和 323-328, 2000.

在 中被引用

弦圖

引用為

Weisstein, Eric W. "弦圖。" 來自 Web 資源。 https://mathworld.tw/ChordalGraph.html

主題分類