7.2.2图的连通性 1.无向图的连通性 定义722在一个无向图G中,若从顶点v到 存在通路(当然从V到也存在通路),则称Ⅵ与 是连通的规定ⅵ到自身总是连通的 设M,为无向图G中的任意两点,若w与v是 连通的,则称与v之间长度最短的通路为v与v之 间的短程线,短程线的长度称为v与v之间的距离, 记作dM,)若v与y不连通,规定d(W,y)=
7.2.2图的连通性 1.无向图的连通性 定义7.2-2 在一个无向图G中，若从顶点vi到 vj存在通路（当然从vj到vi也存在通路），则称vi与 vj是连通的.规定vi到自身总是连通的. 设vi，vj为无向图G中的任意两点，若vi与vj是 连通的，则称vi与vj之间长度最短的通路为vi与vj之 间的短程线，短程线的长度称为vi与vj之间的距离， 记作d(vi ,vj ).若vi与vj不连通，规定d(vi ,vj ) = ∞
7.2.2图的连通性 定义7.23若无向图G是平凡图,或G 中任意两顶点都是连通的,则称G是连通图; 否则,称G是非连通图 定理72-3无向图中顶点之间的连通关 系是顶点集上的等价关系
7.2.2图的连通性 定义7.2-3 若无向图G是平凡图，或G 中任意两顶点都是连通的，则称G是连通图； 否则，称G是非连通图. 定理7.2-3 无向图中顶点之间的连通关 系是顶点集上的等价关系
7.2.2图的连通性 2.有向图的连通性 定义72-4在一个有向图D中,若从顶点w到v存在通 路,则称v可达v规定v到自身总是可达的 定义72-5一个有向图,如果忽略其边的方向后得到 的无向图是连通的,则称此有向图为连通图;否则称为非 连通图 定义72-6一个有向连通图G,如果其任何两顶点间 均是相互可达的,则称图G是强连通 果其任何两顶 点间至少存在一个方向是可达的,则称图G是单向连通的 如果忽略边的方向后其无向图是连通的,则称图G是弱连 通的
7.2.2图的连通性 2.有向图的连通性 定义7.2-4 在一个有向图D中，若从顶点vi到vj存在通 路，则称vi可达vj .规定vi到自身总是可达的. 定义7.2-5 一个有向图，如果忽略其边的方向后得到 的无向图是连通的，则称此有向图为连通图；否则称为非 连通图. 定义7.2-6 一个有向连通图G，如果其任何两顶点间 均是相互可达的，则称图G是强连通的；如果其任何两顶 点间至少存在一个方向是可达的，则称图G是单向连通的； 如果忽略边的方向后其无向图是连通的，则称图G是弱连 通的
7.2.2图的连通性 定理724一个有向图D是强连通的 当且仅当D中存在一条回路,它至少经过每 个顶点一次 推论若有向图D中存在经过每个顶点 至少一次的通路,则D是单向连通的
7.2.2图的连通性 定理7.2-4 一个有向图D是强连通的， 当且仅当D中存在一条回路，它至少经过每 个顶点一次. 推论 若有向图D中存在经过每个顶点 至少一次的通路，则D是单向连通的