离散数学 第2版 教学课件 作者 王元元 离散第17讲 图的基础知识.ppt

《离散数学 第2版 教学课件 作者 王元元 离散第17讲 图的基础知识.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机专业基础课程授课人：王元元单位：计算机理论教研室理工大学指挥自动化学院PowerPointTemplate_Sub1图的基础知识2路径、回路及连通性3欧拉图与哈密顿图4图的矩阵表示2第17讲图的基础知识图的基础知识《离散数学》第17讲Page108to112引言图论是一门很有实用价值的学科，在自然科学，社会科学等各个领域中均有广泛的应用图论是一门古老而又年轻的学科古老：18世纪已经被用来解决问题年轻：20世纪中、后期随着计算机科学的发展，图的理论研究和应用研究才得到迅速广泛的重视起源于1736年的一个数学游戏，瑞士数学家欧拉（Eu

2、ler）通过解决哥尼斯堡七桥问题创立了图论这一数学分支4第17讲图的基础知识18世纪普鲁士的哥尼斯堡镇（现名加里宁格勒）被普雷格尔河支流分成四部分，由七座桥连接起来。镇上的居民在周日喜欢长距离散步，他们提问：能否从镇里某个地方出发不重复地经过所有桥并且返回出发点？欧拉解决了这个问题，解答发表于1736年，这也许是人们第1次使用图论，被认为是图论的起源。b1b2b6Bb4b7DAb5Cb3哥尼斯堡七桥问题5第17讲图的基础知识数学家欧拉6第17讲图的基础知识科学家简介列昂哈德·欧拉(1707-1783）欧拉是瑞士巴塞尔一位牧师之子，13岁

3、进入巴塞尔大学，开始神学生涯。在大学里受伯努利影响转向数学，16岁取得哲学硕士学位。1727年加入圣彼得堡的科学院，1741年到柏林科学院，1766年回到圣彼得堡直到去世。欧拉在数学许多领域做出贡献，包括数论、组合以及分析在诸如音乐和造船上的应用等。他写的书籍和文章数量在1100部以上，另外还有非常多的生前未能发表的著作，以至去世后用了47年才发表完。他的全集的出版工作由瑞士自然科学协会负责，目前还在进行中，预期将超过75卷。科学家简介7第17讲图的基础知识拓扑图由节点和联结节点的边组成只关心节点和节点之间的关联关系图形中节点的位置、边

4、的长短、形状无关紧要BACDABCDABCD8第17讲图的基础知识图(Graph)的定义图G由两个部分所组成:非空集合V(G)，称为图G的节点集，其成员称为节点或顶点(nodesorvertices)。节点用拉丁字母或希腊字母来表示。多重集合E(G)，称为图G的边集，其成员称为边(edges)。边用节点的序偶或节点的两元素多重集表示。节点序偶表示的边称为有向边(directededges)，两元素多重集表示的边称为无向边(indirectededges)。V(G)={A,B,C,D}E(G)={{A,C},{A,C},{A,D},{A,

5、D},{A,B},{C,B},{D,B}}9第17讲图的基础知识当图的边均为有向边（用序偶表示）时，称该图为有向图；当图的边均为无向边（用两元素多重集）时，称该图为无向图。有向图与无向图G1=<{v1,v2,v3,v4},{,,}>G2=<{v1,v2,v3,v4},{{v1,v2},{v1,v3},{v2,v3}}>v1v2v3v4G1v1v2v3v4G210第17讲图的基础知识边e=时，称边e关联端点u,v，并称u为e的起点，v为e的终点。边e={u,v}时，称边e关联节点u，v,

6、并称u，v为e的端点，这时u，v为相邻(接)的节点。当u=v时，和{u,v}均称为环。图G常用二元组,或来表示。有向图与无向图<{v1,v2,v3,v4,v5,v6},{，，，，，}>11第17讲图的基础知识图的表示方法序组表示：或如<{v1,v2,v3},{{v1,v3},{v1,v2}}>图示：用点和线来表示v1v2v312第17讲图的基础知识设图G为。(1)当V和E

7、为有限集时，称G为有限图，否则称G为无限图。只讨论有限图。(2)当边集合中至少有一个元素的重数不小于2时，称G为重图，否则称G为单图；重数不小于2的边称为重边,或平行边。(3)无环和重边的无向图称为简单图。当G为有限简单图时，也常用(n，m)表示图G，其中n=V，m=E。术语13第17讲图的基础知识(4)任何两个不同节点间都有边关联的简单图，称为完全图。n个顶点的完全图常记作Kn。不是任何边的端点的节点称为孤立节点，仅由孤立节点构成的图(E=)称为零图。(5)当给G赋予映射f：V→W，或g：E→W，W为任意集合，常为实数集的子

8、集,此时称G为赋权图，用或或表示之。f(v)称为节点v的权，g(e)称为边e的权。术语14第17讲图的基础知识图例b1，b2为重边。有向图，e1为环，v6为孤立