离散数学耿素云第5版51.ppt

1
图论
2
图论部分
第5章图的基本概念
第6章特殊的图
第7章树
3
第5章图的基本概念
无向图及有向图
通路, 回路和图的连通性
图的矩阵表示
最短路径, 关键路径和着色
4
无向图及有向图
无向图与有向图
顶点的度数
握手定理
简单图
完全图
子图
补图
5
无向图
多重集合: 元素可以重复出现的集合
无序积: AB={(x,y) | xAyB}
定义无向图G=<V,E>, 其中
(1) 顶点集V是非空有穷集合,
其元素称为顶点
(2) 边集E为VV的多重子集,
其元素称为无向边,简称边.
例如, G=<V,E>, 其中
V={v1, v2, …,v5},
E={(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)}
6
有向图
定义有向图D=<V,E>, 其中
(1)顶点集V是非空有穷集合,
其元素称为顶点
(2) 边集E为VV的多重子集,其
元素称为有向边,简称边.
D的基图:用无向边代替有向边
如D=<V,E>, 其中
V={a,b,c,d}
E={<a,a>,<a,b>,<a,b>,<a,d>,<c,b>,<d,c>,<c,d>}
图的数学定义与图形表示,在同构意义下一一对应
7
无向图与有向图(续)
通常用G表示无向图, D表示有向图, 也常用G泛指
无向图和有向图.
V(G), E(G), V(D), E(D): G和D的顶点集, 边集.
n 阶图: n个顶点的图
零图: E=
平凡图: 1 阶零图
空图: V=
8
顶点和边的关联与相邻
定义设e=(u,v)是无向图G=<V,E>的一条边, 称u,v为e的端点,
e与u ( v)关联. 若u  v, 则称e与u ( v)的关联次数为1;若u=v, 则
称e为环, 此时称e与u 的关联次数为2; 若w不是e端点, 则称e与
w 的关联次数为0. 无边关联的顶点称作孤立点.
定义设无向图G=<V,E>, u,vV, e,eE, 若(u,v) E, 则称u,v
相邻; 若e,e至少有一个公共端点, 则称e,e相邻.
对有向图有类似定义. 设e=u,v是有向图的一条边,又称u是e
的始点, v是e的终点, u邻接到v, v邻接于u.
9
顶点的度数
设G=<V,E>为无向图, vV,
v的度数(度) d(v): v作为边的端点次数之和
悬挂顶点: 度数为1的顶点
悬挂边: 与悬挂顶点关联的边
G的最大度(G)=max{d(v)| vV}
G的最小度(G)=min{d(v)| vV}
例如 d(v5)=3, d(v2)=4, d(v1)=4,
(G)=4, (G)=1,
v4是悬挂顶点, e7是悬挂边, e1是环
10
顶点的度数(续)
设D=<V,E>为有向图, vV,
v的出度d+(v): v作为边的始点次数之和
v的入度d(v): v作为边的终点次数之和
v的度数(度) d(v): v作为边的端点次数之和
d(v)= d+(v)+ d-(v)
D的最大出度+(D) =max{d+(v)|vV}
最小出度+(D) =min{d+(v)|vV}
最大入度(D) =max{d(v)|vV}
最小入度(D) =min{d(v)|vV}
最大度(D) =max{d(v)|vV}
最小度(D) =min{d(v)|vV}