主題
Search

頂點圖


頂點圖是至少存在一個頂點,移除該頂點後得到的圖是平面圖的圖。移除後得到平面圖的頂點集合被稱為該圖的頂點集。

平面圖因此是平凡頂點圖,其所有頂點都是頂點集。

非平面頂點圖,有時也稱為近平面圖(儘管此術語也在其他語境中使用),是至少存在一個頂點,移除該頂點後得到的圖是平面圖非平面圖

頂點圖與臨界非平面圖的區別在於,頂點圖僅要求存在至少一個頂點,移除該頂點後得到平面圖,而臨界非平面圖則要求移除每個頂點後都得到平面圖

存在不是單交叉圖的非平面頂點圖。例如,完全二部圖 K_(3,4) 是非平面的頂點圖,但具有圖交叉數 2。

每個頂點圖的色數 <=5

NonplanarApexGraphs

頂點數為 n=1, 2, ... 的頂點圖的數量分別為 1, 2, 4, 11, 34, 155, 1026, 11666, 226916, ... (OEIS A215620),而非平面頂點圖的數量分別為 0, 0, 0, 0, 1, 13, 204, 4700, 147063, ... (OEIS A215621),其中頂點數 n<=5 的唯一非平面頂點圖是完全圖 K_5。上面展示了六個頂點的 13 個非平面頂點圖。在這些圖中,頂點集包括 (6,5)-圖蘭圖 的除 1 和 2 之外的所有頂點,(6,132), (6,138), (6,148)(5,1)-棒棒糖圖 的除頂點 2 之外的所有頂點,以及其他每個圖的所有頂點。

根據Robertson-Seymour 定理,由於頂點圖在子圖運算下封閉,它們具有由禁忌子圖組成的有限障礙集。頂點圖的禁忌子圖包括Petersen 族圖以及 2K_5, K_5 union K_(3,3)2K_(3,3) 的不相交併集 (Pierce 2014, p. 8; Thomas 2014)。Pierce (2014) 確定了 157 個極小頂點禁忌子圖,但禁忌子圖的完整列表尚不清楚 (Gupta and Impagliazzo 1991, Pierce 2014)。

頂點圖的Hadwiger 數最多為 5,因為它們包括禁忌子圖中的完全圖 K_6


另請參閱

頂點, 臨界非平面圖, 圖偏斜度, 平面圖, Robertson 的頂點圖

使用 探索

參考文獻

Gupta, A. and Impagliazzo, R. "Computing Planar Intertwines." In Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91). IEEE Computer Society, pp. 802-811, 1991.Pierce, M. "Searching for and Classifying the Finite Set of Minor-Minimal Non-Apex Graphs." Honors thesis. Chico, CA: California State University, Chico, 2014. http://tmattman.yourweb.csuchico.edu/mpthesis.pdf.Sloane, N. J. A. Sequences A215620 and A215621 in "The On-Line Encyclopedia of Integer Sequences."Thomas, J. "Properties of 2-Connected MMNA Graphs." Preprint, 2014.

請引用本文為

Weisstein, Eric W. "頂點圖。" 出自 Web 資源。 https://mathworld.tw/ApexGraph.html

主題分類