概念:
欧拉回路:经过图中所有边恰好一次,并回到原点的路径
欧拉路径( 欧拉通路):经过图中所有边恰好一次的路径。
半欧拉图:存在欧拉通路,但不存在欧拉回路;
欧拉图:存在欧拉回路;
基图:有向图忽略所有边的方向,得到的无向图为有向图的基图。
性质及定理
无向图
定理1:
无向图G存在欧拉回路的充要条件是G中无奇数度数的节点。
判断半欧拉图的推论:
推论1:
1.无向图G 为半欧拉图,当且仅当G为连通图且除两个顶点的度为奇数外,其余所有的顶点的度都为偶数。
2.G为欧拉图时, 所有点度数为偶数,或者只有2个点度数为奇数
有向图
定理2:
1.有向图为欧拉图,当且仅当G 的基图连通,且所有顶点的入度等于出度。
2.每个顶点入度等于出度;
或者只有1个点入度比出度小1, 从这点出发,只有1个点出度比入度小1,从这个点结束,其他点入度等于出度。
欧拉回路的判定:
1.无向图是否具有欧拉通路或回路的判定:
G有欧拉通路的充分必要条件为:G 连通,G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。
G有欧拉回路(G为欧拉图):G连通,G中均为偶度顶点。
2. 有向图是否具有欧拉通路或回路的判定
**D有欧拉通路:
D连通,除两个顶点外,其余顶点的入度均等于出度,这两个特殊的顶点中,一个顶点的入度比出度大1,另一个顶点的入度比出度小1。
D有欧拉回路(D为欧拉图):D连通,D中所有顶点的入度等于出度。
(注意:这里说有向图连通,说的是有向图是弱连通图。即把有向图中的边变成无向边,只要该图连通,那么原有向图即是弱连通图。实际中可用并查集判断是否弱连通)