离散数学--第7章-图论-1图的基本概念.ppt

离散数学-第7章-图论-1图的基本概念2返回 结束目的(1)掌握图论的基本问题、理论与方法(3)了解图论在信息学科中的应用以及在数学竞赛、数学建模中的应用(2)初步掌握运用图论的理论和方法解决实际问题的能力3返回 结束v为什么要学习图论？v图论计算机问题求解的描述工具。v可以采用图论的成果和方法；v最重要的是：可以培养我们思考问题和解决问题的能力。引言实际问题实际问题数学模型数学模型求解算法（算法）求解算法（算法）编程实现编程实现用大量数据验证用大量数据验证抽象求解测试4返回 结束v应用背景应用背景图论在现代科学技术中有着广泛的应用，如：网络设计、计算机科学、信息科学、密码学、DNA的基因谱的确定和计数、工业生产和企业管理中的优化方法等都广泛的应用了图论及其算法。计算机网络引言某学校网络架构图某学校网络架构图5返回 结束v应用背景应用背景计算机网络电路模拟电路模拟引言例：例：Pspice、Cadence、ADS.PspiceCadence6返回 结束v应用背景应用背景计算机网络电路模拟电路模拟交通网络引言航空网络航空网络!捷運路線图！捷運路線图！7返回 结束引言v应用背景有向图有有单单行道的街道！行道的街道！行程表！行程表！8返回 结束引言v应用背景SocialNetworkHigh School Datingcorporate e-mailReference:Bearman,Moody and Stovel,2004image by Mark NewmanReference:Adamic and Adar,20049返回 结束引言v应用背景TheInternetThe Internet as mapped by The Opte Projectnet,ca,uscom,org,mil,gov,edujp,cn,tw,aude,uk,it,pl,frbr,kr,nl10返回 结束引言vMore ApplicationsHypertexts网页包含到其他网页的超链接。整个网页包含到其他网页的超链接。整个Web是一个图是一个图.搜搜索引擎需要图处理算法。索引擎需要图处理算法。Matching职位招聘，如何有效将职位与应聘者匹配？职位招聘，如何有效将职位与应聘者匹配？Schedules工程项目的任务安排，如何满足限制条件，并在最短时工程项目的任务安排，如何满足限制条件，并在最短时间内完成？间内完成？Program structure大型软件系统，函数（模块）之间调用关系。编译器分大型软件系统，函数（模块）之间调用关系。编译器分析调用关系图确定如何最好分配资源才能使程序更有效析调用关系图确定如何最好分配资源才能使程序更有效率。率。11返回 结束引言v图论的产生和发展图论的产生和发展1.哥尼斯堡七桥问題(Bridges of Koenigsberg)问题问题 能否从某一块陆地出发，走遍每一座桥，且每一座桥只能走一次，最后回到出发点。12返回 结束引言欧拉路径：解決哥尼斯保七桥问題数学家欧拉(Euler,1707-1783)于1736年严格的证明了上述哥尼斯堡七桥问题无解，并且由此开创了图论的典型思维方式及论证方式原來是一笔画问题啊！转化 Euler1736年 图论中讨论的图 问题：是否能从四块陆地中的任一块开始，通过每座桥恰好一次再回到起点？是否能从任意一个顶点开始，通过每条边恰好一次再回到起点？转化包含两个要素：对象（陆包含两个要素：对象（陆地）及对象间的二元关系地）及对象间的二元关系（是否有桥连接）（是否有桥连接）13返回 结束引言2.四色猜想四色猜想在任何平面或球面上的地图，只用四种颜色涂色，就可使得相邻区域涂上不同颜色。1976年，Appel,Haken和Koch利用计算机辅助证明了四色猜想，但其数学证明仍不理想。14返回 结束引言v3.Hamilton周遊世界问題哈密頓路径至今尚无有效方法來解決！正十二面体有二十个顶点表示世界上20个城市各经每个城市一次最后返回原地投影至平面反映到图论上就是判断一个给反映到图论上就是判断一个给定的图是否存在一条含所有顶定的图是否存在一条含所有顶点的回路。点的回路。15返回 结束引言v4.最短路径问題最短路径问題(Shortest Path Problem)最快航線最快航線 最快的最快的routing16返回 结束引言最短路径算法最短路径算法Dijkstra算法算法可以求出從某一点到图上其他任一点的最短路径可以求出從某一点到图上其他任一点的最短路径17返回 结束引言v5.走迷宫与走迷宫与深度优先搜索深度优先搜索(Depth-First Search)老鼠走迷宮老鼠走迷宮深度优先搜索深度优先搜索一直往前走一直往前走碰壁就回碰壁就回头头換条路找換条路找沿途要沿途要记录记录下走过的下走过的路线路线两点之间有无道路可通？有多少条道路可通？哪条路最短？18返回 结束引言v图论的重要地位图论的重要地位图论在计算机科学领域中有着重要地位操作系统进程演变状态图和目录树搜索。人工智能图搜索策略和知识的表示数据结构的二大类非线性结构：树和图数据库系统的实体-联系模型和文件组织自动机理论19返回 结束引言v图论的发展图论的发展1847年基尔霍夫运用图论解决了电路理论中求解联立方程的问题，引进了“树”概念。1857年Cayley非常自然在有机化学领域发现了一种重要的图，称为“树”，解决了计算饱和氢化物同分异构体的数目。1936年,哥尼格的第一本图论专著问世,才使得图论成为一门独立的数学学科.1946年,随着世界上第一台计算机的问世,使图论的发展突飞猛进.20返回 结束引言v图论相关的交叉研究图论相关的交叉研究代数图论拓扑图论化学图论算法图论随机图论极值图论网络图论模糊图论超图论 以往数学家习惯将纯数学应用于其它学科，以往数学家习惯将纯数学应用于其它学科，Gowers将图论和组合数学中的将图论和组合数学中的Ramsey理论应用理论应用于泛函分析的研究，获得了于泛函分析的研究，获得了1998年的年的Fields奖。奖。21返回 结束7.1图的基本概念1.图的定义图论中讨论的“图”，不是微积分、解析几何、几何学中讨论的图形，而是客观世界中某些具体事物间联系的一个数学抽象。如二元关系的关系图，就不考虑点的位置及连线的长短曲直，而只关心哪些点之间有连线。这种数学抽象就是图论中“图”的概念。一堆顶点和边的组合！一堆顶点和边的组合！Set of vertices connected pairwise by edges.22返回 结束7.1图的基本概念1.图的定义定义定义7.1.1：所谓图图(graph)G是一个三元组，记作G，其中（1）图G的结点结点 组成的结点集结点集(vertexset)记作V(G)v1,v2,vn,(V(G)（2）图G的边边 组成的边集边集(edgeset)记作，且ei为(vj,vt)或。若ei(vj,vt)，称ei为以vj和vt为端点端点(endvertices)的无向边无向边 (undirectededge)；若ei，称ei为以vj为起点起点(origin)，vt为终点终点(terminus)的有向边有向边(directededge)。（3）(G)：EVV称为关联函数关联函数(incidencefunction）。注：这里的交叉点不是我们研究的顶点。与五位代表其中是朋友。例1点集合人边集合朋友关系23返回 结束7.1图的基本概念当图的顶点集和边集被给定时，可以省去，可以将图简记为G=。无向边无向边 若边ei的两个顶点vj,vk，不能区分起点和终点，则称该边为无向边。无向边e用无序偶（vj,vk）表示。有向边有向边若边的一起始顶点为vj，另一终止顶点为vk，则称该边为有向边。有向边用有序偶表示。无向图无向图每一条边都是无向边的图称无向图。有向图有向图 每一条边都是有向边的图称有向图。混合图混合图一些边是有向边，另一些边是无向边的图，称为混合图。邻接边邻接边 关联于同一顶点的两条边，被称为邻接边。邻接点邻接点若两个顶点由同一条边关联，则这两个顶点被称为是邻接点。孤立顶点孤立顶点不与任何顶点相邻接的顶点，被称为孤立顶点。零图零图 仅由若干孤立顶点组成的图，被称为零图。阶阶 图G的顶点个数称为图G的阶阶24返回 结束7.1图的基本概念例例1 1、(1)无向图，图形表示如右：图形表示如右：例例1 1、(2)有向图，25返回 结束7.1图的基本概念平凡图平凡图仅由一个孤立顶点构成的图，被称为平凡图。自回路或环自回路或环关联于同一顶点的一条边，被称为自回路或闭环。平行边平行边 若有两条有向边，他们的起点和终点相同，称他们为有向平行边有向平行边。我们把联结于一对顶点间的多条边称为平行边。简单图简单图 不含有任何平行边和自回路的图，被称为简单图。多重图多重图任何含有平行边的图，被称为多重图。完全图完全图 简单图G=中，若每对顶点间都有边相连，则称该图为完全图。无向完全图无向完全图 有n个顶点的无向完全图 记作Kn。Kn 的边数的边数 n个顶点的无向完全图Kn的边数为n(n-1)/2.对称有向图对称有向图对于无向图G，将G中的每条边用两条与e有相同端点的对称边e和e 来代替后得到的一个有向图。有向完全图有向完全图 对Kn中每条边任意确定一个方向，称该图为n顶点的有向完全图。有向完全图的边数有向完全图的边数 n个顶点的有向完全图边数也为n(n-1)/2。完全有向图完全有向图 完全图的对称有向图称为完全有向图完全图的对称有向图称为完全有向图(complete digraph），记作），记作 。26返回 结束7.1图的基本概念2.图的顶点度数(简称度)无向图的度数记，指与，相关联的边的条数。有向图的度数，顶点的入度、出度最大度最大度 最小度最小度相应地还有，设D是有向图27返回 结束7.1图的基本概念v如例1的(2)中，。28返回 结束7.1图的基本概念3.握手定理定理定理1 1：设图为无向图或有向图，为边数)，(则握手定理：推论：推论：任何图中，度为奇数的顶点个数为偶数。定理定理2 2：设为有向图，则，。29返回 结束7.1图的基本概念4.度数序列例例3是否可以画出一个简单的无向图，使得各点度数与下列的序列一致。（1）2,2,2,2,2,2（2）2,2,3,4,5,6（3）1,2,3,4,4,5解：（1）可以，如图7.1.5的G1或G2。（2）不可以。在6个结点的简单无向图中，其中每个结点最多与其余5个结点相邻，即(G)5。（3）不可以。任何图中，度数为奇数的结点只能有偶数个。设为图的顶点集，称 为的度数序列度数序列。提示：提示：根据握手定理，非负整数序根据握手定理，非负整数序列能够构成无向图的度数序列的充要列能够构成无向图的度数序列的充要条件是条件是 其和为偶数，即奇数度顶点其和为偶数，即奇数度顶点的数目为偶数个。但这些无向图未必的数目为偶数个。但这些无向图未必一定是简单图。一定是简单图。30返回 结束7.1图的基本概念例例4 下列各组数中，哪些能够构成无向图的度下列各组数中，哪些能够构成无向图的度数序列数序列?哪些能够构成简单无向图的度数序哪些能够构成简单无向图的度数序列列?(1)1，1，1，2，3(2)2，2，2，2，2(3)3，3，3，3(4)1，2，3，4，5(5)1，3，3，331返回 结束7.1图的基本概念5.图的同构定义定义：设两个无向图，若存在一一对应的映射函数，使得对于任意的，当且仅当并且与重数相同，则称与同构同构，记作。换句话说，当两个简单图同构时，两个图的结点之间具有保持相邻关系的一一对应。目前，判断两个图是否同构，还只能根据定义。也就是说，两个图是否同构还没有很简单的判别方法。两图同构的必要条件是：（1）两图结点数相等。（2）边数相等。（3）度数相同的结点个数相等。但这仅是必要条件，不是充分条件。32返回 结束7.1图的基本概念5.图的同构例例2、v1v2v3v4vavbvcvd33返回 结束7.1图的基本概念6.图的运算（1）子图定义：子图定义：设是两个图，若，且，则称是的子图子图，是的母图母图，记作。真子图真子图 且(即或)。生成子图生成子图且。34返回 结束7.1图的基本概念6.图的运算导出子图导出子图非空，以为顶点集，以两端均在中的边的全体为边集的的子图，称的导出子图，记做G。非空，以为边集，以中边关联的顶点的全体为顶点集的子图，称的导出子图，记作G。35返回 结束7.1图的基本概念例例3、上图中，(1)(6)都是(1)的子图，其中(2)(6)为真子图，(1)(5)为生成子图。36返回 结束7.1图的基本概念(2)并并图、交图、差图和环和图定义设G1和G2都是图G的子图。仅由G1和G2中所有边与结点组成的图称为G1和G2的并并(union），记作G1G2。仅由G1和G2的公共边组成的图称为G1和G2的交交（cap），记作G1G2。仅由G1中去掉G2中的边组成的图称为G1和G2的差差（difference），记作G1G2。在G1和G2的并中去掉G1和G2的交所得到的图称为G1和G2的环和环和（ringsum），记作G1G2，即G1G2(G1G2)(G1G2)(G1G2)(G1G2)37返回 结束7.1图的基本概念(3)补图定义设为无向完全图，为无向简单图，其中，则称，相对于互为补图，记，。如例3中(1)(2)(3)(4)(5)(6)38返回 结束概念巩固例例1：是否可以画出一个简单的无向图，使得各点度数与下列的序列一致。（1）2,2,2,2,2,2（2）2,2,3,4,5,6（3）1,2,3,4,4,5解：（1）可以，如图G1G2。（2）不可以。在6个结点的简单无向图中，其中每个结点最多与其余5个结点相邻，即(G)5。（3）不可以。任何图中，度数为奇数的结点只能有偶数个。谢谢观赏谢谢观赏