路径、长度 路径(Path) 相应的边必在图中,从顶点Vx到顶点的顶点序列(Wx,V1, 须在图中V2,…,Vn,Wy)称为从V到y的路径。路径可能是 不唯一的。例如,(1中,Ⅵ到V3的路径为: (v1V2V3)或(Ⅵ1V3);而G2中,1到4的路径为 134>。 ●长度( Length) 路径的长度是该路径上边或弧的数目。例如,G1 中Ⅵ1到V3的长度为1或2;而G2中1到4的长度为2。 v2 停止放映 G2 下一页 v4 3 第11页
下一页 上一页 停止放映 第 11 页 路径、长度 ⚫ 路径（Path） 在图中，从顶点Vx到顶点Vy的顶点序列（Vx，V1， V2，…,Vn,Vy)称为从Vx到Vy的路径。路径可能是 不唯一的。例如，G1中，V1到V3的路径为： （V1V2V3）或（V1V3）；而G2中，1到4的路径为 <134>。 ⚫ 长度（Length） 路径的长度是该路径上边或弧的数目。例如，G1 中V1到V3的长度为1或2；而G2中1到4的长度为2。 1 3 2 4 G2 o o o o v1 v2 v3 v4 G1 相应的边必 须在图中
连通图、强连通图、连通分量 连通图( Connected Graph) G3 在无向图中,若每一对顶点间都有路径, 称此图是连通图。如图G3所示。 连通分量( Connected Component) 无向图中的极大连通子图称为连通 分量。(连通图有一个分量,非连通图 有多个连通分量) 强连通图( Strongly Connected Graph) 上在有向图中,若每对顶点Vx到Vy 你止放间都存在Vx到Vy,及从Wy到Vx的路径, G4 则称此图是强连通图。如图G4所示 下一页 (有去有回) 第12页
下一页 上一页 停止放映 第 12 页 连通图、强连通图、连通分量 1 2 ⚫ 连通图（Connected Graph） 在无向图中，若每一对顶点间都有路径， 称此图是连通图。如图G3所示。 ⚫ 连通分量（Connected Component） 无向图中的极大连通子图称为连通 分量。（连通图有一个分量，非连通图 有多个连通分量） ⚫ 强连通图 （ Strongly Connected Graph） 在有向图中，若每对顶点Vx到Vy 间都存在Vx到Vy，及从Vy到Vx的路径， 则称此图是强连通图。如图G4所示。 （有去有回） 3 4 5 G3 1 2 3 4 5 G4
子图、生成树 子图 有两个图G和G1,若V1V,E1sE,即Ⅵ1中的顶点 G=(V,E)都属于V中的顶点,E1中的关系都 G1=(Ⅵ1,E1)属于E中的关系,则称G1是G的子图。 (图的部分顶点和部分边组成的图) 生成子图、生成加 设G是一个连通图,G中任一包含G的所有顶点的子图 G的生成树不是唯一的。一棵有n个顶点的生成树, 上有且仅有n-1条边(弧)。 停止放映 (子图包含所有顶点,但不一定包含所有边) 下一页 第13页
下一页 上一页 停止放映 第 13 页 子图、生成树 ⚫ 子图 有两个图G和G1，若V1V，E1 E，即V1中的顶点 G = （V，E） 都属于V中的顶点，E1中的关系都 G1 =（V1，E1） 属于E中的关系，则称G1是G的子图。 （图的部分顶点和部分边组成的图） ⚫ 生成子图、生成树 设G是一个连通图，G中任一包含G的所有顶点的子图 称为生成子图。如果该子图是树，则称为G的生成树。 G的生成树不是唯一的。一棵有n个顶点的生成树， 有且仅有n-1条边（弧）。 （子图包含所有顶点，但不一定包含所有边）
网、权 权( Weight 若图的边或弧带有与之相关的数,称此数为该 边或弧的权。权通常用来表示从一个顶点到另 个顶点的距离或费用。 网( Network)(权图) 带权的图称为网。如G5为带权的网。 5 2 G5 停止放映 7 下一页 第14页
下一页 上一页 停止放映 第 14 页 网、权 ⚫ 权（Weight） 若图的边或弧带有与之相关的数，称此数为该 边或弧的权。权通常用来表示从一个顶点到另 一个顶点的距离或费用。 ⚫ 网（Network）(赋权图) 带权的图称为网。如G5为带权的网。 V1 V2 V3 V4 G5 3 2 5 7
图的应用实例 [路径问题]城市中有许多街道,每一个十字路口都可以 看作图中一个顶点,邻接两个十字路口之间的每一段街 道既可以看作一条,也可以看作两条有向边。如果街道 双向的,就用两条有向边。如果街道是单向的,就用 条有向边。(路线咨询) 街道2街道3 单向 4 停止放映 单向 单向 下一页 第15页
下一页 上一页 停止放映 第 15 页 图的应用实例 ⚫ [路径问题] 城市中有许多街道，每一个十字路口都可以 看作图中一个顶点，邻接两个十字路口之间的每一段街 道既可以看作一条，也可以看作两条有向边。如果街道 是双向的，就用两条有向边。如果街道是单向的，就用 一条有向边。(路线咨询)