图的术语 第七章图 子图:设有两个图G=(VE)和G=VE),如果Ⅴ CVECE则 称G为G的子图。 邻接点:若无向边(v)∈E,则称顶点v和v互为邻接点。 关联:称无向边(vv)与顶点v和v相关联 顶点V的度:与v相关联的边的数目,记为TD(v) 顶点V的入度:有向图中,以顶点V为弧头(即终端点)的弧 的数目,记为ID(V) 顶点V的出度:有向图中,以顶点V为弧尾(即初始点)的弧 的数目,记为OD(V)。 示例2有向图G1:顶点数目n=4;有向边或弧的 数目e=4;ID(V1)=1OD(V)=2,TD(V1)=3 无向图(G2:顶点数目n=5;无向边的 数目e=6;TD(Vv1)2。 注,一个有n个顶点, e条边或弧的图,有: 2 ∑TD( 第1页
第七章 图 第11页 子图：设有两个图G=(V,E)和G`=(V`,E`)，如果V` V, E` E,则 称G`为G的子图 。 邻接点：若无向边(v,v`)∈E，则称顶点v和v`互为邻接点。 关联：称无向边(v,v`)与顶点v和v`相关联。 顶点V的度：与v相关联的边的数目，记为TD(v)。 顶点V的入度：有向图中，以顶点V为弧头（即终端点）的弧 的数目，记为ID(V)。 顶点V的出度：有向图中，以顶点V为弧尾（即初始点）的弧 的数目，记为OD(V)。 示例2 有向图G1：顶点数目n=4；有向边或弧的 数目e=4；ID(V1 )=1,OD(V1 )=2，TD(V1 )=3。 无向图G2：顶点数目n=5；无向边的 数目e=6；TD(V1 )=2。 注. 一个有n个顶点， e条边或弧的图，有： ( ). 2 1 1 = = n i e TD Vi ⚫ 图的术语 V1 V2 V3 V4 G1 V1 V2 V4 V5 V3 G2
路径:图G中由顶点V到V的路径是一个顶点序列 第七章图 VEV, V V,其中1Y)∈E1车m。若图G是个有向图 ,则由顶点V到V的路径亦是有向的,它由E(G中的有向边 <VM1v∈E15m组成。 路径的长度:图G中由顶点V到V的路径长度是指在该路径上 的边或弧的数目。 简单路径:若图G中由顶点V到V的一条路径上,除了V和V 可以相同外,其余顶点均不相同,则称此路径为一条简单路径。 简单回路:起点∨和终点相同的简单路径。亦称简单环 回路或环:起点∨和终点V相同的路径。其余顶点允许重复出 现。 示例3下述有向图G3和无向图G4 VG3:顶点序列VV2V是二个长度为2的有向简 单环;V1,v2,V3是由顶点v到V3的长度为 2 的有向简单路径 G4:V1,V2,V3,M4是由V到∨长度为3简单路径 G3 G4 第1页
第七章 图 第12页 路径：图G中由顶点V到V`的路径是一个顶点序列 V=Vi0,Vi1,···,Vim=V`，其中(Vij-1 ,Vij)∈E,1≤j≤m。若图G是个有向图 ，则由顶点V到V`的路径亦是有向的，它由E(G)中的有向边 <Vij-1 ,Vij>∈E,1≤j≤m组成。 路径的长度：图G中由顶点V到V`的路径长度是指在该路径上 的边或弧的数目。 简单路径：若图G中由顶点V到V`的一条路径上，除了V和V` 可以相同外，其余顶点均不相同，则称此路径为一条简单路径。 简单回路：起点V和终点V`相同的简单路径。亦称简单环。 回路或环：起点V和终点V`相同的路径。其余顶点允许重复出 现。 示例3 下述有向图G3和无向图G4 G3：顶点序列V1 ,V2 ,V1是一个长度为2的有向简 单环； V1 ,V2 ,V3是由顶点V1到V3的长度为2 的有向简单路径 G4：V1 ,V2 ,V3 ,V4是由V1到V4长度为3简单路径 V1 V2 V3 V4 V1 V2 V3 G3 G4
0图的术语 第七章图 有根图:在一个有向图中,若存在一个顶点V,从该顶点有路径 可以到达图中其他所有顶点,则称此有向图为有根图,顶点V称作 该图的根。 连通:在无向图G中,如果从顶点到顶点V有路径,则称和 V是连通的 连通图:若在无向图G中,V(G的任意两个不同的顶点V和 都连通(即有路径),则称G为连通图 连通分量:无向图G的极大连通子图称为G的连通分量。显然 任何连通图的连通分量只有一个,即是其自身。而非连通的无向 图却有多个连通分量。 强连通图:在有向图G中,若对于∨(G中任意两个不同的的顶 点V和V,都存在从∨到V和从V到V的路径则称G是强连通图 强连通分量:有向图G的极大强连通子图称为G的强连通分量 第13页
第七章 图 第13页 有根图：在一个有向图中，若存在一个顶点V，从该顶点有路径 可以到达图中其他所有顶点，则称此有向图为有根图，顶点V称作 该图的根。 连通：在无向图G中，如果从顶点V到顶点V`有路径，则称V和 V`是连通的。 连通图：若在无向图G中，V(G)的任意两个不同的顶点Vi和Vj 都连通（即有路径），则称G为连通图。 连通分量：无向图G的极大连通子图称为G的连通分量。显然 ，任何连通图的连通分量只有一个，即是其自身。而非连通的无向 图却有多个连通分量。 强连通图：在有向图G中，若对于V(G)中任意两个不同的的顶 点Vi和Vj，都存在从Vi到Vj和从Vj到Vi的路径,则称G是强连通图。 强连通分量：有向图G的极大强连通子图称为G的强连通分量 ⚫ 图的术语
图的术语 第七章图 强连通只有一个强连通分量,即是其自身。非强连通的 有向图有多个强连通分量 示例5设有下列图 3 有向图G3无向图G4 无向图G5 无向图G6 则G4与G5均是连通图。 G6是非连通图,但它有两个连通分量H1和H2 G3不是强连通图,因为V3到V2没有路径。但G3有两个 强连通分量,如下所示 网:若将图的每条边或弧都赋上一个权,则将这种带权 的图称为网络,或简称网。通常权是具有某种意义的数,比 如它们可以表示两个结点之间的距离、耗费、流量等 第14页
第七章 图 第14页 强连通只有一个强连通分量，即是其自身。非强连通的 有向图有多个强连通分量。 示例5 设有下列图 V1 V2 V3 V4 V1 V2 V3 V1 V2 V3 V4 V5 V6 V7 V1 V2 V3 V4 V5 V6 V7 有向图G3 无向图G4 无向图 V8 G5 无向图G6 则 G4与G5均是连通图。 G6是非连通图，但它有两个连通分量H1和H2。 G3不是强连通图，因为V3到V2没有路径。但G3有两个 强连通分量，如下所示 V1 V2 V3 网：若将图的每条边或弧都赋上一个权，则将这种带权 的图称为网络，或简称网。通常权是具有某种意义的数，比 如它们可以表示两个结点之间的距离、耗费、流量等。 ⚫ 图的术语
图的术语 第七章图 一示例4有关图的术语图解示例 0 3 4 3 2) (3) ()一个图(2)一个有向图 (3)一个有向标号图,且边上标有权。 简单路径:顶点0→顶点1→顶点3→顶点2。 非简单路径:顶点0顶点1→顶点3一顶点2→顶点4→顶点1 简单回路:顶点1→顶点3→顶点2→顶点4→顶点1 第15页
第七章 图 第15页 示例4 有关图的术语图解示例 0 1 3 2 4 4 1 1 2 3 7 ⑴ 一个图 ⑵ 一个有向图 ⑶ 一个有向标号图，且边上标有权。 简单路径：顶点0→顶点1 →顶点3 →顶点2。 非简单路径：顶点0→顶点1 →顶点3 →顶点2 →顶点4 →顶点1。 简单回路：顶点1 →顶点3 →顶点2 →顶点4 →顶点1。 （1） ⚫ 图的术语 （2） （3）