主題
Search

仙人掌圖

下載 Mathematica 筆記本下載 Wolfram 筆記本
CactusGraph

仙人掌圖，有時也稱為仙人掌樹、混合 Husimi 樹或帶橋的多邊形仙人掌，是一個連通圖，其中任意兩個圖的環沒有公共邊。等價地，它是一個連通圖，其中任意兩個（簡單）環最多有一個公共頂點。仙人掌圖也可以定義為連通平面圖，其中每個塊是一個環或一條邊（White 2001，第 57 頁）。

仙人掌圖的每個環都是弦圖。然而，存在一些圖（例如，theta_0-圖和Pasch 圖），它們的環都是弦圖，但它們不是仙人掌圖。

不等式

mu(G)=nu(G),

其中 mu 是環秩，nu 是無向圖的環的總數，對於連通圖 G 成立，當且僅當它是仙人掌圖（Volkmann 1996）。

每個仙人掌圖都是一個單位距離圖（Erdős et al. 1965）。

每個偽樹都是仙人掌圖。

節點數為 1, 2, ... 的仙人掌圖的數量為 1, 1, 2, 4, 9, 23, 63, 188, ... (OEIS A000083)。

另請參閱

弦圖環, 圖的環, 偽樹, 樹, 單位距離圖

使用 探索

參考文獻

Bona, M.; Bousquet, M.; Labelle, G.; 和 Leroux, P. "m-ary 仙人掌的列舉。" Adv. Appl. Math. 24, 22-56, 2000.Chao, C. Y. 和 Whitehead, E. G. Jr. "關於圖的色等價性。" 在 圖論及其應用（Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976) (Ed. Y. Alavi 和 D. R. Lick). Berlin: Springer-Verlag, pp. 121-131, 1978.Erdős, P.; Harary, F.; 和 Tutte, W. T. "關於圖的維數。" Mathematika 12, 118-122, 1965.Ford, G. W. 和 Uhlenbeck, G. E. "圖論中的組合問題 III。" Proc. Nat. Acad. Sci. USA 42, 529-535, 1956.Geller, D. 和 Manvel, B. "仙人掌的重構。" Canad. J. Math. 21, 1354-1360, 1969.Harary, F. 和 Uhlenbeck, G. "關於 Husimi 樹的數量，I。" Proc. Nat. Acad. Sci. USA 39, 315-322, 1953.Husimi, K. "關於 Mayer 簇積分理論的註釋。" J. Chem. Phys. 18, 682-684, 1950.Sloane, N. J. A. 序列 A000083/M1191 在 "整數序列線上百科全書" 中。Soifer, A. 數學著色書：著色數學及其創造者的多彩生活。 New York: Springer, p. 91, 2008.Volkmann, L. "圖中環數的估計。" Per. Math. Hungar. 33, 153-161, 1996.White, A. T. "圖論中的嵌入問題。" Ch. 6 在 曲面群圖：互動與模型 (Ed. A. T. White). Amsterdam, Netherlands: Elsevier, 2001.

在 中被引用

仙人掌圖

引用為

Weisstein, Eric W. "仙人掌圖。" 來自 ——Wolfram 網路資源。 https://mathworld.tw/CactusGraph.html

主題分類