主題
Search

不可切換圖

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook

如果一個圖無法透過邊切換簡化為另一個具有相同度序列的圖，則稱該圖為不可切換圖。

相反，如果一個圖可以透過邊切換簡化為另一個具有相同度序列的圖，則該圖被稱為可切換圖。

不可切換圖的特徵在於停用匯出子圖 C_4、 P_4 和 2P_2，其中 C_n 是圈圖，P_4 是路徑圖，而 2P_2 是梯子橫檔圖。

所有不可切換圖都是分裂圖 (Mukhopadhyay et al. 2023)。

UnswitchableConnectedGraphs

節點數為 n=1, 2, ... 的不可切換連通圖的數量為 1, 1, 2, 4, 8, 16, 32, 64, ...，（均為 2 的冪），上面展示了前幾個。類似地，簡單但不必連通的圖的數量為 1, 2, 4, 8, 16, 32, 64, 128, ....

另請參閱

度序列, 分裂圖, 可切換圖

使用 探索

參考文獻

Berge, C. Graphs and Hypergraphs. New York: Elsevier, 1973.Eggleton, R. B. "Graphic Sequences and Graphic Polynomials: A Report." Colloq. Math. Soc. J. Bolyai 10, 385-392, 1975.Mukhopadhyay, A.; John, D.; and Vasudevan, S. "Recognizing and Generating Unswitchable Graphs." 12 Apr 2023. https://arxiv.org/abs/2304.12381.

請引用為

Weisstein, Eric W. "不可切換圖。" 來自 —— 資源。 https://mathworld.tw/UnswitchableGraph.html

學科分類