图论之欧拉路
目录
欧拉路
给定无孤立节点图
G
,若存在一条路,经过图中的每一条边一次且仅一次,那么该条路称为欧拉路,如果这条路的起点和终点相同,则该路称为欧拉回路,否则称为欧拉通路。
无向图
无向图中具有一条欧拉图,当且仅当该图是连通图且有零个或者两个奇数度的节点,所有点的度都是偶数的时候,该图有欧拉回路,有两个奇数度的节点时,有欧拉通路。
有向图
有向图具有欧拉路当且仅当该图是连通的,若每个节点的入度等于出度,则存在欧拉回路,若图中除了两个节点之外,每个点的入度等于出度,而这两个点中一个点的入度比出度大1
,另外一个点的出度比入读大1
,则存在欧拉通路。
求解欧拉路
当判断图中具有欧拉路后,可以根据深度优先搜索,对每一条边设置访问标记,当找到一条欧拉路后直接结束搜索,否则根据回溯思想不断进行搜索。
历史评论
开始评论