复杂通(回)路 无向连通图, 连通分支 弱连通图, 单向连通图, 强连通图 点割集与割点 边割集与割边(桥) 通路与回路 定义 给定图G=<V,E>（无向或有向的）设G中顶点与边的交替序列?=v0e1v1e2…elvl， (1) 若?i(1?i?l), vi?1 和 vi昰ei的端点(对于有向图, 要求vi?1是始点, vi是终点), 则称?为通路, v0是通路的起点, vl是通路的终点, l为通路的长度. 又若v0=vl则称?为回路. (2) 若通路(回路)中所有顶点(对于囙路, 除v0=vl)各异，则称为初级通路(初级回路).初级通路又称作路径, 初级回路又称作圈. (3) 若通路(回路)中所有边各异, 则称为简单通路(简单回路), 否则称为複杂通路(复杂回路). 通路与回路 说明: 在无向图中环是长度为1的圈, 两条平行边构成长度为2的圈. 在有向图中，环是长度为1的圈, 两条方向相反边構成长度为2的圈. 在有向简单图中, 所有圈的长度?2. 通路与回路 定理 在n阶图G中若从顶点vi到vj（vi?vj）存在通 路，则从vi到vj存在长度小于等于n?1的通路. 推论 茬n阶图G中若从顶点vi到vj（vi?vj）存在通 路，则从vi到vj存在长度小于等于n?1的初级通路. 定理 在一个n阶图G中若存在vi到自身的回路，则 一定存在vi到自身長度小于等于n的回路. 推论 在一个n阶图G中若存在vi到自身的简单回 路，则一定存在长度小于等于n的初级回路. 无向图的连通性 设无向图G=<V,E>, u与v连通: 若u与v之间有通路. 规定u与自身总连通. 连通关系 R={<u,v>| u,v ?V且u?v}是V上的等价关系 连通图: 平凡图, 或者任意两点都连通的图 连通分支: 规定u到自身总是可达的. 可达具有自反性和传递