主題
Search

Ore 圖


Ore 圖是滿足 Ore 定理,即圖 G 使得對於所有非鄰接頂點的子集,非鄰接頂點的度數之和大於或等於節點數 n。令 V(G)頂點集E(G)G邊集,令 |V(G)| 表示 G頂點計數,用 d(v) 表示頂點 v頂點度,用 (u,v) 表示一對頂點。那麼,圖 G 為 Ore 圖的條件可以寫成

 (u,v) not in E(G)=>d(u)+d(v)>=|V(G)|

(Ore 1960;Bondy 1971)。請注意,Skiena(1990,第 197 頁)和 Pemmaraju 與 Skiena(2003,第 301 頁)陳述了此結果的較弱版本,將“大於或等於”替換為“大於”。

OreGraphs

Ore 定理指出,Ore 圖始終是哈密頓圖。此外,對於此類圖,可以在多項式時間內構造哈密頓環(Bondy 和 Chvátal 1976;Skiena 1990,第 197 頁)。滿足 Ore 準則(使用“空真”約定,因此包括完全圖 K_n)的 n=1, 2, ... 個圖的數量為 1, 1, 1, 3, 5, 21, 68, 503, 4942, 128361, ... (OEIS A264683),其中前幾個圖示如上所示。

HamiltonianNonOreGraph

每個滿足 Ore 準則的圖都是哈密頓圖,但並非每個哈密頓圖都滿足該準則。不滿足 Ore 準則的 n=1, 2, ... 個頂點的簡單哈密頓圖的數量為 0, 0, 0, 0, 3, 27, 315, 5693, 172141, 9176757, ... (OEIS A264684),其中前幾個圖示如上所示。


另請參閱

哈密頓環, 哈密頓圖, Ore 定理

使用 探索

參考文獻

Bondy, J. A. "Pancyclic Graphs I." J. Combin. Th. 11, 80-84, 1971.Bondy, J. A. and Chvátal, V. "A Method in Graph Theory." Disc. Math. 15, 111-136, 1976.Meyniel, M. "Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté." J. Combin. Th. 14, 137-147, 1973.Ore, O. "A Note on Hamiltonian Circuits." Amer. Math. Monthly 67, 55, 1960.Palmer, E. M. "The Hidden Algorithm of Ore's Theorem on Hamiltonian Cycles." Computers Math. Appl. 34, 113-119, 1997.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, 2003.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequences A264683 and A264684 in "The On-Line Encyclopedia of Integer Sequences."Woodall, D. R. "Sufficient Conditions for Circuits in Graphs." Proc. London Math. Soc. 24: 739-755, 1972.

在 中引用

Ore 圖

請引用為

Weisstein, Eric W. "Ore 圖。" 來自 —— 資源。 https://mathworld.tw/OreGraph.html

主題分類