二、连通图

在无向图G=（V，E）中，若图G中某些点与某些边的交替序列可以排成如下（vi0，ei1，vi1，ei2，…，vi（k-1），eik，vik）的形式，且eit=（vit-1，vit），则称这个点边序列为联结的一条链，链长为k；没有重复顶点和边的链称为路；起点和终点重合的路称为回路.

例3 图9-6中，u=v6e6v5e7v1e8v5e5v4e4v3是一条从v6到v3的链；

p=v1e2v2e3v3e4v4e5v5e6v6是一条从v1到v6的路；

c=v1e2v2e3v3e4v4e5v5e6v6e1v1是一条从v1到v1的回路.

图9-6

连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路；若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路；具有欧拉回路的图称为欧拉图.

在引言中提到哥尼斯堡“七桥问题”就是要在图中寻找一条欧拉回路.关于欧拉图，有如下的定理成立.

定理2 无向连通图G是欧拉图，当且仅当G中无奇点.

推论1 无向连通图G为欧拉图，当且仅当G的边集可划分为若干个初等回路.

推论2 无向连通图G有欧拉道路，当且仅当G中恰有两个奇点.