数结 华中科技大学 计犷机学院(9 9008=8799
2001 -- 12 -- 27/29 华中科技大学 数据结构计算机学院(9)
第七章图( Graph) 7.1图的定义和术语 ●图 图G由顶点集V和关系集E组成,记为 V是顶点(元素)的有穷非空集, E是两个顶点之间的关系的集合。 G1 ●若顶点a,C之间的关系为有序对<a,c>,<a,c>∈E, 则称〈a,C>为从a到c的一条弧/有向边; a是<a,c>的弧尾, C是<a,c>的弧头; G是有向图 W G1=V1,E1, V1=A, B, C, D, El E1={<A,C>,<A,D>,<C,D>,<B,E>,<E,B>}
第七章 图(Graph) 7.1 图的定义和术语 ● 图 图G由顶点集V和关系集E组成,记为 G=(V,E) V是顶点(元素)的有穷非空集， E是两个顶点之间的关系的集合。 A B C E D ● 若顶点a,c之间的关系为有序对<a,c>,<a,c>∈E, 则称<a,c>为从a到c的一条弧/有向边； a是<a,c>的弧尾， c是<a,c>的弧头； G是有向图。 例 G1={V1,E1}, V1={A,B,C,D,E} E1={<A,C>,<A,D>,<C,D>,<B,E>,<E,B>} G1
●若顶点a,b之间的关系为无序对(a,b) 则称(a,b)为无向边(边),G是无向图。 无向图可简称为图 (a,b)依附于a和b,(a,b)与a和b相关联 例G2={V2,E2}, V2={1,2,3,4,5,6}, G2 E2={(1,3),(1,5),(3,5),(4,6)} ●完全图有n个顶点和n(n-1)/2条边的无向图 B G2 G4 e=1(1-1)/2e=2(2-1)/2e=3(3-1)/2e=4(4-1)/2e=5(5-1)/2 0 10
1 2 5 6 3 G2 ● 若顶点a,b之间的关系为无序对(a,b), 则称(a,b)为无向边(边）,G是无向图。 无向图可简称为图。 (a,b)依附于a和b, (a,b)与a和b相关联 例 G2={V2,E2}, V2={1,2,3,4,5,6}, E2={(1,3),(1,5),(3,5),(4,6)} 4 v1 A v2 C v3 G1 G2 G3 G4 G5 v1 v1 B v2 D A C B D E ● 完全图----有n个顶点和n(n-1)/2条边的无向图 e=1(1-1)/2 =0 e=2(2-1)/2 =1 e=3(3-1)/2 =3 e=4(4-1)/2 =6 e=5(5-1)/2 =10
●有向完全图一有n个顶点和n(n-1)条弧的有向图 G1 G2 e=1(1-1)e=2(2-1) e=3(3-1) 0 ●网( Network)-边(弧)上加权( weight)的图 4 B 无向网G1 有向网G2
● 有向完全图----有n个顶点和n(n-1)条弧的有向图。 ● 网(Network)----边(弧)上加权(weight)的图。 1 2 3 G1 G2 G3 1 1 2 1 2 3 无向网G1 4 A B C 4 15 5 9 9 4 3 有向网G2 e=1(1-1) =0 e=2(2-1) =2 e=3(3-1) =6
●对图G=(V,E)和G=(V,E'), 若VcV且E≌E,则称G是G的一个子图 3)(4 G G1 G2 ②2③④4 G3 G4 G1,G2,G3是G的子图 G4不是G的子图
● 对图 G=(V,E)和G'=(V',E')， 若V' V 且 E' E，则称G'是G的一个子图 1 2 3 G 4 1 2 G1 3 4 1 G2 3 4 1 G4 1 2 3 G3 4 G1,G2,G3是G的子图 G4不是G的子图 2