文档介绍：第7章图
第 2 页
图的术语与定义
图的定义
图(Graph)——图G是由两个集合 V(G) 和E(G) 组成的,记为 G=(V,E)
其中:V(G) 是顶点的非空有限集
E(G) 是边的有限集合,边是顶点的无序对或有序对。
图的分类
有向图
无向图
第 3 页
图的术语与定义
图的定义
有向图——有向图G是由两个集合 V(G) 和E(G) 组成的。
其中:
V(G) 是顶点的非空有限集。
E(G) 是有向边(也称弧)的有限集合,弧是顶点的有序对,记为<v, w>,v、w是顶点,v为弧尾,w为弧头。
第 4 页
图的术语与定义
例如:
G1 = <V1, E1>
V1 = { A, B, C, D, E }
E1 = {<A,B>, <A,E>, <B,C>, <C,D>, <D,B>, <D,A>, <E,C> }
E
A
C
B
D
第 5 页
图的术语与定义
图的定义
无向图——无向图G是由两个集合 V(G) 和E(G) 组成的。
其中:
V(G) 是顶点的非空有限集。
E(G) 是边的有限集合,边是顶点的无序对,记为(v, w) 或(w, v),并且(v, w) = (w, v)。
第 6 页
图的术语与定义
例如:
G2 = <V2, E2>
V2 = { v0, v1, v2, v3, v4 }
E2 = { (v0, v1), (v0, v3), (v1, v2), (v1, v4), (v2, v3), (v2, v4) }
V0
V4
V3
V1
V2
第 7 页
图的术语与定义
例如:
G2 = <V2,E2>
V2 = { v0,v1,v2,v3 }
E2 = { <v0,v1 >, <v0,v2 >, <v2,v3 >, <v3,v0 > }
例
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> }
V0
V1
V2
V3
第 8 页
图的术语与定义
图的应用举例
例1. 交通图(公路、铁路)
顶点:地点边:连接地点的路
例2. 电路图
顶点:元件边:连接元件之间的线路
例3. 通讯线路图
顶点:地点边:地点间的连线
例4. 各种流程图
如产品的生产流程图。
顶点:工序边:各道工序之间的顺序关系
第 9 页
图的术语与定义
图的基本术语
邻接点及关联边
邻接点:边的两个顶点
关联边:若边 e = (v, u), 则称顶点v、u 关连边 e。
e
V0
V4
V3
V1
V2
第 10 页
图的术语与定义
顶点的度、入度、出度 顶点V的度= 与V相关联的边的数目
在有向图中:
顶点V的出度= 以V为起点有向边数
顶点V的入度= 以V为终点有向边数
顶点V的度= V的出度+V的入度
设图G 的顶点数为 n,边数为 e
图的所有顶点的度数和= 2*e
(每条边对图的所有顶点的度数和“贡献”2度)