尤拉圖是包含歐拉回路 的圖 。具有 A133736 )，其中前幾個示例如上所示。
相應的連通尤拉圖的數量為 1, 0, 1, 1, 4, 8, 37, 184, 1782, ... (OEIS A003049 ; Robinson 1969; Liskovec 1972; Harary and Palmer 1973, p. 117)，其中前幾個示例如上所示。
然而，在解釋該術語時需要注意，因為一些作者將尤拉圖 定義為不同的物件，即所有頂點的度數均為偶數的圖（受以下定理的啟發）。尤拉（未提供證明）表明，一個連通 簡單圖 是尤拉圖 當且僅當 它沒有圖頂點 具有奇數 度 （即，所有頂點都是偶數度）。雖然在
可以使用 Wolfram 語言 測試圖是否為尤拉圖，使用的命令是EulerianGraphQ g ].
一個圖是尤拉圖 當且僅當 它的邊集可以分解為環（Veblen 1916, p. 15; Fleischner 1990; Heinrich and Streicher 2019; Gross and Yellen 2006, p. 195）。確定一個尤拉圖是否可以分解為最多 NP-完全 問題 (Péron 1984, Heinrich and Streicher 2017)。找到具有奇數個頂點的圖中最大的尤拉子圖 也是一個 NP-完全問題 (Skiena 1990, p. 194)。
確定無向圖中歐拉回路的數量是 #P-完全的。
下表給出了一些命名的尤拉圖。
一個有向圖 是尤拉圖 當且僅當 每個圖頂點 都具有相等的入度 和出度 。平面二分圖 與平面 尤拉圖互為對偶 。在 A058337 )。
另請參閱 歐拉回路 ,
哈密頓圖 ,
Two-Graph
使用 探索
參考文獻 Bollobás, B. Graph Theory: An Introductory Course. Brightwell, G. R. and Winkler, P. "Note on Counting Eulerian Circuits." CDAM Research Report LSE-CDAM-2004-12. May 2004. http://www.cdam.lse.ac.uk/Reports/Files/cdam-2004-12.pdf . Colbourn, C. J. and Dinitz, J. H. (Eds.). CRC Handbook of Combinatorial Designs. Fleischner, H. Eulerian Graphs and Related Topics. 1990. Frank, A. and Szegő, L. "Constructive Characterizations for Packing and Covering With Trees." Discr. Appl. Math. 131 , 347-371, 2003. Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Harary, F. and Palmer, E. M. "Eulerian Graphs." §1.4 and 4.7 in Graphical Enumeration. Heinrich, I. and Streicher, M. "Cycle Decompositions and Constructive Characterizations." 7 Jan 2019. https://arxiv.org/abs/1708.09141 . Liskovec, V. A. "Enumeration of Euler Graphs" [Russian]. Review MR#6557 in Math. Rev. 44 , 1195, 1972. McKay, B. "Eulerian Graphs." http://cs.anu.edu.au/~bdm/data/graphs.html . Péroche, B. "NP-Completeness of Some Problems of Partitioning and Covering in Graphs." Discr. Appl. Math. 8 , 195-208, 1984. Skiena, S. "Eulerian Cycles." §5.3.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Sloane, N. J. A. Sequences A003049 /M3344, A058337 , and A133736 in "The On-Line Encyclopedia of Integer Sequences." Veblen, O. Analysis Situs. New York: Amer. Math. Soc., 1916. 在 中被引用 尤拉圖
請引用為
Weisstein, Eric W. “尤拉圖。” 來自 https://mathworld.tw/EulerianGraph.html
主題分類
, 2, ... 個節點的尤拉圖的數量為 1, 1, 2, 3, 7, 15, 52, 236, ... (OEIS A133736)，其中前幾個示例如上所示。
個節點上的連通尤拉圖的數量等於在 
個節點上的連通尤拉圖的數量，但對於非連通圖，計數是不同的，因為存在非連通圖，它們具有多個不相交的環，每個節點的度數均為偶數，但沒有單個環透過所有邊。
個環是 NP-完全 問題 (Péron 1984, Heinrich and Streicher 2017)。找到具有奇數個頂點的圖中最大的尤拉子圖也是一個 NP-完全問題 (Skiena 1990, p. 194)。
, 2, ... 個節點上的尤拉有向圖的數量為 1, 1, 3, 12, 90, 2162, ... (OEIS A058337)。