1、7.2 路与连通7.2.1 路 7.2.2 连通图 7.1.3 连通度7.4.4 二分图 7.2.1 路设 u和 v是任意图 G的 结点n 图 G的 u v链 (chain 或 walk)： 有限结点 和边交替序列 u0e1u1e2un-1enun (u u0,v un)，其中结点 ui-1和 ui正好是 ei的两个端点 。n 链的 长度 ： 链 中出现的边 数n 链 的 端点 ； 链 的 内部 点n 开的 链：两端点不同； 闭的 链n 迹 (trail)： 边 互不同的 链n 路 (path)： 内部 点互不同的 链7.2.1 路n 注释 1）链 中 ， 结点和边可以重复。2）简单图 G的链
2、可用 结点 序列表示 。3） 平凡链 ： 不 含边（即长度为 0）4） 有向图 D的 u v有向 链 ：链中 各 边的方向都从 u到 v。5） 有向图 D的 u v有向 迹6） 有向图 D的 u v有向 路7.2.1 路n 例如 n x1 x3链 ： x1 e9 x2 e8 x5 e2 x5 e3 x4 e3 x5 e6 x3n x1 x3迹 ： x1 e9 x2 e8 x5 e2 x5 e3 x4 e4 x3n x1 x3路 ： x1 e9 x2 e8 x5 e3 x4 e4 x3n 有向 x1 x3链 ： x1 e1 x5 e2 x5 e6 x3 e4 x4 e5 x3e4e9e7e1e2
3、e5e3e8 e6x1 x4x2 x3x57.2.1 路n 回 (circuit)： 两端点相同的迹 闭迹n 圈 (cycle)或 回路 (circuit)： 闭路n k回 ： 长度为 k的回n 奇圈 ： 长度为偶数的圈n 有向回 ： 有向闭迹n 有向圈 ： 有向闭路7.2.2 连通图n 结点 x和 y是 连通的 ： 无向图 G中存在连接 结点x和 y的 路 。 规定 x到自身总是连通的n 连通图 ： 无向图 G中 每一对 不同的结点 x和 y间都有一条 路 。n 非连通图 连通分支 连通分支数7.2.2 连通图n 连通分支7.2.2 连通图n 结点 x可达 y： 有 向图 D中存在 x到 y的 有向 路 规定 结点 x到自身总是 可达n 单侧连通 有向图 ： 结点间一个可 达另一 个n 强连通 有向图 ： 结点间相互 可 达n 弱连通 向图 ： 基础 图是 连通图n 非强连通图 强连通分支 （ 强分图 ）7.2.2 连通图n 例如强连通图 单侧连通图 弱连通 图7.2.2 连通图n 非强连通图 n 强分图6532184 76532184 7
