问题
单项选择题
图中不存在______。
A.欧拉回路
B.欧拉路径
C.欧密尔顿回路
D.哈密尔顿路径
答案
参考答案:A
解析: 通过连通图G中每条边一次且仅一次,遍历图中所有节点的回路称为欧拉回路。
通过连通图G中每条边一次且仅一次,遍历图中所有节点的开路称为欧拉开路(欧拉路径)。
若G是连通图,则存在欧拉回路的充要条件是:所有节点的度数均为偶数度;存在欧拉开路的充要条件是:当且仅当G中有且只有两个节点的度数为奇数度。
由于图中有两个节点的度数是奇数度,因此图中只存在欧拉路径,但不符合欧拉回路的充要条件,即不存在欧拉回路。
通过连通图G中每个节点一次且仅一次的回路称为欧密尔顿回路。
通过连通图G中每个节点一次且仅一次的开路称为欧密尔顿开路(哈密尔顿路径)。