主題
Search

無爪圖

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本
Claw

一個圖是無爪圖 當且僅當 它不包含 完全二部圖 K_(1,3) (被稱為“爪圖”；如上圖所示) 作為 停用匯出子圖。

任何圖的線圖都是無爪圖，任何無三角形圖的補圖也是如此。

無爪圖的圖類包括

1. 反稜柱圖,

2. 啞鈴圖,

3. 主教圖 (及其連通分量),

4. 雞尾酒會圖 K_(n×2),

5. 完全圖,

6. 環圖,

7. 德布魯因圖,

8. 空圖 K^__n,

9. 河內圖,

10. 梯子橫檔圖,

11. 車圖,

12. 線圖,

13. 棒棒糖圖,

14. 路徑圖 P_n,

15. 謝爾賓斯基墊片圖,

16. 強完美圖,

17. 三角圖, 和

18. 2-正則圖。

Claw-FreeGraphs

n 個節點上無爪簡單圖的數量，對於 n 節點，當 n=1, 2, ... 分別是 1, 2, 4, 10, 26, 85, 302, 1285, 6170, ... (OEIS A086991; 如上圖所示)。

ConnectedClaw-FreeGraphs

n 個節點上無爪連通簡單圖的數量，對於 n 節點，當 n=1, 2, ... 分別是 1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, 1728403, ... (OEIS A022562; 如上圖所示)。

Minty (1980) 證明了 最大獨立集問題，該問題在無限制圖上通常是 NP-完全 的，但在無爪圖上可以用強多項式時間解決。他的證明使用了 Edmonds (1965) 的演算法來找到最大權重匹配。然而，Nakamura 和 Tamura (2001) 表明該演算法在某些特殊情況下會失敗，並提供了修改來糾正這個錯誤。在無爪圖中找到最大基數獨立集的問題由 Sbihi (1980) 解決。

另請參閱

爪圖, 完全二部圖, 停用匯出子圖, 線圖, 完美匹配

此條目的部分內容由 Jonathan William Mugan 貢獻

使用 探索

參考文獻

Edmonds, J. "Paths, Trees, and Flowers." Canad. J. Math. 17, 449-467, 1965.Faudree, R.; Flandrin, E.; and Ryjáček, Z. "Claw-Free Graphs--A Survey." Disc. Math. 164, 87-147, 1997.Minty, G. J. "On Maximal Independent Sets of Vertices in Claw Free Graphs." J. Combin. Th. B 28, 284-304, 1980.Nakamura, D. and Tamura, A. "A Revision of Minty's Algorithm for Finding a Maximum Weight Stable Set of a Claw-Free Graph." J. Oper. Res. Soc. Japan 44, 194-204, 2001.Sbihi, N. "Algorithme de Recherche d'un Stable de Cardinalite Maximum dans un Graphe sans Étoile." Disc. Math. 29, 53-76, 1980.Sloane, N. J. A. Sequences A022562 and A086991 in "The On-Line Encyclopedia of Integer Sequences."

在 中引用

無爪圖

請引用為

Mugan, Jonathan William 和 Weisstein, Eric W. "Claw-Free Graph." 來自 —— 資源。 https://mathworld.tw/Claw-FreeGraph.html

學科分類