第六章图 §6.1图的定义和术语 心图( Graph)—图G是由两个集合∨(G)和E(G)组成的, 记为G=(V,E) 其中:V(G是顶点的非空有限集 E(G)是边的有限集合,边是顶点的无序对或有序对 ☆有向图—有向图G是由两个集合∨(G)和E(G组成的 其中:VG是顶点的非空有限集 E(G)是有向边(也称弧)的有限集合,弧是顶点的有序 对,记为<W>,VW是顶点,V为弧尾,W为弧头 ☆无向图—天向图G是由两个集合V(G)和E(G组成的 其中:V(G)是顶点的非空有限集 E(G是边的有限集合,边是顶点的无序对,记为(W,W) 或(W,V),并且(V,W)=(W,v)
第六章 图 §6.1 图的定义和术语 ❖图(Graph)——图G是由两个集合V(G)和E(G)组成的, 记为G=(V,E) 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对 ❖有向图——有向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是有向边（也称弧）的有限集合，弧是顶点的有序 对，记为<v,w>，v,w是顶点，v为弧尾，w为弧头 ❖无向图——无向图G是由两个集合V(G)和E(G)组成的 其中：V(G)是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对，记为（v,w） 或（w,v)，并且（v,w)=(w,v)
例 4)(5 GI 图G中:V(G1)={1,2,34.5,6} E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<56>,<6,3>} 例 7 G2 图G2中:V(G2){1,2,3,4,5,6,7 E(G1)={(1,2),(1,3),(2,3),(2,4)、(2,5),(56),(5,7)}
例 2 4 5 1 3 6 G1 图G1中：V(G1)={1,2,3,4,5,6} E(G1)={<1,2>, <2,1>, <2,3>, <2,4>, <3,5>, <5,6>, <6,3>} 例 1 5 7 3 2 4 G2 6 图G2中：V(G2)={1,2,3,4,5,6,7} E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)}
☆有向完备图—n个顶点的有向图最大边数是n(n-1) 令无向完备图—n个顶点的无向图最大边数是n(n-1)2 今权 与图的边或弧相关的数叫 今网 带权的图叫~ ☆子图——如果图G(和图G(V,E),满足: ●VcV ●EcE 则称G为G的子图 今顶点的度 ●无向图中,顶点的度为与每个顶点相连的边数 ●有向图中,顶点的度分成入度与出度 ◆入度:以该顶点为头的弧的数目 ◆出度:以该顶点为尾的弧的数目 ☆路径——路径是顶点的序列∨=Vo,vn,…Vm},满足 V1,V∈E或<Vr1,V>∈E(1<jn)
❖有向完备图——n个顶点的有向图最大边数是n(n-1) ❖无向完备图——n个顶点的无向图最大边数是n(n-1)/2 ❖权——与图的边或弧相关的数叫~ ❖网——带权的图叫~ ❖子图——如果图G(V,E)和图G‘(V’,E‘),满足： ⚫V’V ⚫E’E 则称G‘为G的子图 ❖顶点的度 ⚫无向图中，顶点的度为与每个顶点相连的边数 ⚫有向图中，顶点的度分成入度与出度 ◆入度：以该顶点为头的弧的数目 ◆出度：以该顶点为尾的弧的数目 ❖路径——路径是顶点的序列V={Vi0,Vi1,……Vin}，满足 (Vij-1,Vij)E 或 <Vij-1,Vij>E,(1<jn)
◆路径长度—沿路径边的数目或沿路径各边杈值之和 今回路—第一个顶点和最后一个顶点相同的路径叫 今简单路径—序列中顶点不重复出现的路径叫 ◇简单回路 除了第一个顶点和最后一个顶点外,其 余顶点不重复出现的回路叫~ 令连通—从顶点到顶点W有一条路径,则说∨和W是 连通的 今连通图—图中任意两个顶点都是连通的叫 ◆连通分量—非连通图的每一个连通部分叫 心强连通图—有向图中,如果对每一对V,v∈V,V≠V 从V到Ⅵ和从Ⅵ到Ⅵ都存在路径,则称G是~
❖路径长度——沿路径边的数目或沿路径各边权值之和 ❖回路——第一个顶点和最后一个顶点相同的路径叫~ ❖简单路径——序列中顶点不重复出现的路径叫~ ❖简单回路——除了第一个顶点和最后一个顶点外，其 余顶点不重复出现的回路叫~ ❖连通——从顶点V到顶点W有一条路径，则说V和W是 连通的 ❖连通图——图中任意两个顶点都是连通的叫~ ❖连通分量——非连通图的每一个连通部分叫~ ❖强连通图——有向图中，如果对每一对Vi,VjV, ViVj, 从Vi到Vj 和从Vj到Vi都存在路径，则称G是~
例 )(3 有向完备图 无向完备图 例 图与子图 例 例 G2 顶点2入度:1出度:3 顶点5的度:3 顶点4入度:1出度:0 顶点2的度:4
例 2 1 3 2 1 3 有向完备图 无向完备图 3 5 6 例 2 4 5 1 3 6 图与子图 例 2 4 5 1 3 6 G1 顶点2入度：1 出度：3 顶点4入度：1 出度：0 例 1 5 7 3 2 4 G2 6 顶点5的度：3 顶点2的度：4