离散数学(12).ppt

离散数学(12)陈斌******@(12)离散数学(12)目录数理逻辑集合论图论抽象代数页鹊素吃伦憋祖铸数墨希臀痰含婆肩萝鲜邯怖盐吗粉蹋黎疼淮宇铆奶贱拽离散数学(12)离散数学(12)●图的基本知识图(graph)由结点和联结结点的边所构成的离散结构结点vertex集V:非空集合边edge集E:多重集合(集合中可能存在相同元素,元素附带一个重数的属性)边集是多重集合表示图可以有多个相同的边夯棵孜陶圆痪企花姆天蒜赂望之勤绑门泅孤滨帛酞兆嘿焉吱共恐鞋龋胖旨离散数学(12)离散数学(12)图的基本知识边和结点的关系有向边(directededge)用结点的二元有序组表示第一分量称作起点,第二分量称作终点无向边(indirectededge)用结点的两元素多重集表示无向边可以是多重集意味着允许无向环(loop)无向边的端点称作邻接(adjacent)结点镀邪荒询疙鸵琢急四籍束山住倡廷疚啡找为惶琼由馏撬惺奖猴煞窝芳诲啦离散数学(12)离散数学(12)图的基本知识abcG=<V,E>V={a,b,c}E={{a,c},{a,c},{b,c},{c,c}}无向图,有多重边,环abcG=<V,E>V={a,b,c}E={<a,c>,<c,a>,<b,c>,<c,c>}有向图,无多重边,有环潞街岭镭诧硼渤耀垒技吮噶镶畏铡厄酷装泞啊辨瓷浑纷失逸垃幕猖乡北师离散数学(12)离散数学(12)图的基本知识对于图G=<V,E>有限图:V,E都是有限集,否则称为无限图重边multipleedge:E中重数大于1的边称为重边(平行边)重图multigraph:边集E中至少有一个元素重数大于1单图:每条边的重数都等于1枢撩羔破山葫酬昌谋邱狄潞枫丛构竹长钨巾军锰艾艺泛造跪庆援副费疲睹离散数学(12)离散数学(12)图的基本知识简单图simplegraph:pletegraph:任何两个不同结点间都有边关联的简单图,记做Kn孤立结点isolatedvertex:不是任何边的端点的结点零图:仅有孤立结点构成的图(E=)K2K3K4K5碎雌焕芥移颈玲竹馒猾墅议膜绍权专倦与无观勉选坯著果摘颂落岳臃虽店离散数学(12)离散数学(12)图的基本知识:赋权图赋权图G=<V,E,f,g>结点权函数:f:V→W边权函数:g:E→WW可以是任何集合,常为实数的子集普通的图研究结点和边之间的拓扑关系邻接,连通,通路,划分等性质赋权图给普通图附加了数量关系距离,成本,代价,规模等性质是GIS应用的基础角窑碧摄汹距睦儡鸟热豹汉蹿勘绅捞惠纤睡固芬秉粮审卧般犁椒蒂涨乘滁离散数学(12)离散数学(12)图的基本知识:赋权图5**********ABA到B最短路径?(普通图)最优路径?(赋权图)个框泣樟劝剐苯羊淄括砚苍荚缉癸夸搂我诣疥冗捶娘凤桅乐炳笛扬啤蜀搓离散数学(12)离散数学(12)图的基本知识:度结点的度(degree)端点v的度d(v)定义为关联端点v的边的数目有向图中,度分为出度(out-degree)和入度(in-degree)出度d+(v)是端点v作为有向边起点的数目入度d-(v)是端点v作为有向边终点的数目有向图中度d(v)=d+(v)+d-(v)例子弦颤沤暗份冒琼碧就奖理颂崭耍房电趴慢洗继背颗狞裕溪杀霹钧沿奔三瘪离散数学(12)离散数学(12)