大门|大门-CS-2007 |问题23

以下哪个图有欧拉回路？ （A） 任意k-正则图，其中kis是偶数。 （B） 90个顶点上的完整图 （C） 25个顶点上循环的补 （D） 以上都不是 答复: （C） 说明： 一个图表 欧拉电路 如果以下条件为真。

….a） 所有非零度的顶点都是连通的。我们不关心零度的顶点，因为它们不属于欧拉循环或路径（我们只考虑所有边）。 ….b） 所有顶点都有偶数阶。

让我们分析所有选项。 A） 任何 k-正则图 其中k是偶数 .不是欧拉图，因为k正则图可能不连通（属性b为真，但a可能不连通）

B） A 完全图 在90个顶点上 不是欧拉的，因为所有顶点的度数都为89（属性b为false）

C） 那个 补足 在25个顶点上的循环 他是欧拉人。在25个顶点的循环中，所有顶点的阶数均为2。在补图中，所有顶点的阶数都为22，并且图是连通的。 这个问题的小测验