顶点的度( Degree) ●无向图中,顶点的度是以该顶点为一个端点的边 的条数。例如,G1中V2的度为3,V4的度为1。 ●有向图中,以某顶点为弧头的弧的数目称为该顶 点的入度( Indegree)。例如e中顶点1的入度 为1。以某顶点为弧尾的弧的数目称为该顶点的 出度(0 utdegree)。例如G中顶点1的出度为2。 该顶点的度=入度+出度。例如,G2中顶点1的度 =2+1=3。 v2 □上一页 停止放映 G1 G2 v4 第11页
下一页 上一页 停止放映 第 11 页 顶点的度（Degree） ⚫ 无向图中，顶点的度是以该顶点为一个端点的边 的条数。例如，G1中V2的度为3，V4的度为1。 ⚫ 有向图中，以某顶点为弧头的弧的数目称为该顶 点的入度（Indegree）。例如G2中顶点1的入度 为1。以某顶点为弧尾的弧的数目称为该顶点的 出度（Outdegree）。例如G2中顶点1的出度为2。 该顶点的度=入度+出度。例如，G2中顶点1的度 =2+1=3。 o o o o v1 v2 v3 v4 G1 1 3 2 4 G2
路径、长度 路径(Path) 在图中,从顶点Wx到顶点Wy的顶点序列(Vx,V1, V2,…,Ⅵn,Vy)称为从Wx到Vy的路径。路径可能是 不唯一的。例如,G1中,Ⅵ1到W3的路径为: (Ⅵ1V2V3)或(ⅥV3);而G中,1到4的路径为 <134>。 长度( LengtH 路径的长度是该路径上边或弧的数目。例如,G1 中Ⅵ1到V3的长度为1或2;而G2中1到4的长度为2。 上页√1 2 停止放映 G2 3 v4 第12页
下一页 上一页 停止放映 第 12 页 路径、长度 ⚫ 路径（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
连通图、强连通图、连通分量 G3 连递图( onnected Graph) 在无向图中,若每一对顶点间都有 路径,称此图是连通图。如图G3所 连递分量( onnected Component) 无向图中的极大连通子图称为连通 分量 强连通图( Strong1 y Connected Graph) □上一页 在有向图中,若每对顶点Vx到Vy 间都存在Vx到V,及从y到Vx的路 停止放映 径,则称此图是强连通图。如图G4 G4 所示 第13页
下一页 上一页 停止放映 第 13 页 连通图、强连通图、连通分量 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,若ⅥsV,E1≤E,即Ⅵ中的顶点 G=(,E)都属于V中的顶点,E中的关系都 G1=(V1,E1)属于E中的关系,则称G1是G的子图。 ●生成机 设G是一个连通图,G中任一包含G的所有顶点的子图 称为生成子图。如果该子图是树,则称为G的生成树 G的生成树不是唯一的。一棵有n个顶点的生成树, 有且仅有n-1条边(弧)。 □上一页 停止放映 第14页
下一页 上一页 停止放映 第 14 页 子图、生成树 ⚫ 子图 有两个图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 若图的边或弧带有与之相关的数,称此数为 该边或弧的权。权通常用来表示从一个顶点 到另一个顶点的距离或费用。 My(Network) 带权的图称为网。如G5为带权的网。 5 □上一页 3 G5 停止放映 第15页
下一页 上一页 停止放映 第 15 页 网、权 ⚫ 权（Weight） 若图的边或弧带有与之相关的数，称此数为 该边或弧的权。权通常用来表示从一个顶点 到另一个顶点的距离或费用。 ⚫ 网（Network） 带权的图称为网。如G5为带权的网。 V1 V2 V3 V4 G5 3 2 5 7