离散数学(12).ppt

离散数学(12)
陈斌
******@pku.

目录
数理逻辑
集合论
图论
抽象代数
●图的基本知识
图(graph)
由结点和联结结点的边所构成的离散结构
结点vertex集V:非空集合
边edge集E:多重集合(集合中可能存在相同元素,元素附带一个重数的属性)
边集是多重集合表示图可以有多个相同的边
图的基本知识
边和结点的关系
有向边(directed edge)用结点的二元有序组表示
第一分量称作起点,第二分量称作终点
无向边(indirected edge)用结点的两元素多重集表示
无向边可以是多重集意味着允许无向环(loop)
无向边的端点称作邻接(adjacent)结点
图的基本知识
a
b
c
G=<V,E>
V={a,b,c}
E={{a,c}, {a,c}, {b,c}, {c,c}}
无向图,有多重边,环
a
b
c
G=<V,E>
V={a,b,c}
E={<a,c>, <c,a>, <b,c>, <c,c>}
有向图,无多重边,有环
图的基本知识
对于图G=<V,E>
有限图:V,E都是有限集,否则称为无限图
重边multiple edge:E中重数大于1的边称为重边(平行边)
重图multigraph:边集E中至少有一个元素重数大于1
单图:每条边的重数都等于1
图的基本知识
简单图simple graph:无环和重边的无向图
plete graph:任何两个不同结点间都有边关联的简单图,记做Kn
孤立结点isolated vertex:不是任何边的端点的结点
零图:仅有孤立结点构成的图(E=)
K2
K3
K4
K5
图的基本知识:赋权图
赋权图G=<V,E,f,g>
结点权函数:f:V→W
边权函数:g:E→W
W可以是任何集合,常为实数的子集
普通的图研究结点和边之间的拓扑关系
邻接,连通,通路,划分等性质
赋权图给普通图附加了数量关系
距离,成本,代价,规模等性质
是GIS应用的基础
图的基本知识:赋权图
5
15
2
1
7
4
20
2
6
8
A
B
A到B
最短路径?(普通图)
最优路径?(赋权图)
图的基本知识:度
结点的度(degree)
端点v的度d(v)定义为关联端点v的边的数目
有向图中,度分为出度(out-degree)和入度(in-degree)
出度d+(v)是端点v作为有向边起点的数目
入度d-(v)是端点v作为有向边终点的数目
有向图中度d(v)=d+(v)+d-(v)
例子