要么改变世界,要么适应世界

图论之欧拉路

2021-04-25 12:00:34
95
目录

欧拉路

给定无孤立节点图G,若存在一条路,经过图中的每一条边一次且仅一次,那么该条路称为欧拉路,如果这条路的起点和终点相同,则该路称为欧拉回路,否则称为欧拉通路。

无向图

无向图中具有一条欧拉图,当且仅当该图是连通图且有零个或者两个奇数度的节点,所有点的度都是偶数的时候,该图有欧拉回路,有两个奇数度的节点时,有欧拉通路。

有向图

有向图具有欧拉路当且仅当该图是连通的,若每个节点的入度等于出度,则存在欧拉回路,若图中除了两个节点之外,每个点的入度等于出度,而这两个点中一个点的入度比出度大1,另外一个点的出度比入读大1,则存在欧拉通路。

求解欧拉路

当判断图中具有欧拉路后,可以根据深度优先搜索,对每一条边设置访问标记,当找到一条欧拉路后直接结束搜索,否则根据回溯思想不断进行搜索。

历史评论
开始评论