第二节 图的连通性 n 通路和回路 n 无向图的连通性 n 有向图的连通性 n 欧拉图 n 哈密顿图 通路和回路 可达的：在图G 中，结点u 和结点v 之间存在一 条路，则称结点u 到结点v 是可达的。 通路： G 中前后相互关联的点边交替序列 w=v 0 e 1 v 1 e 2 e n v n 称为连接v 0 到v n 的通路。 W 中边的数目K 称为通路W 的长。 回路：在点边序列v 0 e 1 v 1 e 2 e n v n 中，当 v 0 =v n 时称此通路为回路。 无向图的连通性 图是连通的判定法则：从图中任意一结点出发 ，通过某些边一定能到达其它任意一结点，则 称图是连通的。 连通：在无向图G 中，结点u 和结点v 之间存在一 条路，则称结点u 与结点v 是连通的。约定：任一 结点与自身总是连通的。 连通图：若图G 中，任意两个结点均连通，则称G 是连通图，否则称非连通图。对非连通图可分成几 个无公共结点的连通分支。无向图中结点间的连通 关系是等价关系。 练习1：连通图的判定 (1) (2) (3) (4) (5) (6) (7) (8) 指出下列各图是否连通 欧拉图
