欧拉图是包含欧拉回路 的图 。具有 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.net.cn/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)。