离散数学之图论精.ppt
离散数学之图论第1页，本讲稿共25页内容n图的基本概念n通路、回路、连通性n欧拉图n汉密尔顿图n图的矩阵表示第2页，本讲稿共25页图论n图论已有二百多年历史，近四五十年来发展十分迅速，成为一个新兴的数学分支n计算机科学中许多概念、算法需要图论支持（如二叉树）n为计算机应用建模提供数学工具n图论研究图的逻辑结构与性质，不关注图的具体几何形态第3页，本讲稿共25页图的基本概念n哥尼斯堡桥问题第4页，本讲稿共25页图的基本概念n结点：用来表示事物n边：表示事物的联系（与结点对相关）n定义：图G是由非空结点集合V=v1,v2,vn和边集合E=e1,e2,em组成，其中ek用结点对表示即(vi,vj)n一个图可表示为G=第5页，本讲稿共25页图的基本概念n图有两种类型：有向图和无向图n有向图中结点对(vi,vj)有方向性，称为有向边n无向图中结点对(vi,vj)没有方向性，称为无向边，也常表示为vi,vj第6页，本讲稿共25页图的基本概念n一个有n个结点、m条边的图称为(n,m)图n零图：即（n,0）图n平凡图：即（1,0）图n其他概念n自圈(环)：(vi,vi)n孤立点：不与任何结点相连（包括自己）n平行边：(vi,vj)和(vi,vj)第7页，本讲稿共25页图的基本概念n有向图的关联与邻接ne=(vi,vj)，则结点vi,vj与e关联关联，vi,vj分别是e的起点起点和终点，终点，结点vi,vj是邻接邻接的n无向图的关联与邻接ne=(vi,vj)，则结点vi,vj与e关联关联，结点vi,vj是邻邻接接的ne1，e2跟同一个结点关联，则称e1，e2是邻接邻接的第8页，本讲稿共25页图的基本概念n结点的次数（度数）n无向图n结点的度数等于与之关联的边的条数n若有自圈，该结点的度数等于与之关联的边的条数+1n有向图n结点的出度：以之为起点的边的条数n结点的入度：以之为终点的边的条数n定理：图中所有结点的度数之和必为偶数，且是边数的两倍n所有结点的度数均为d的图称为d度正则图度正则图第9页，本讲稿共25页图的基本概念n子图：若有图G=和G=，若VV且EE，则称G是G的子图n真子图：EE n生成子图：V=Vn完全图n完全无向图：一个(n,m)图，若为n-1度正则图，且无自圈、无平行边n完全有向图：一个(n,m)图，每个结点的出度和入度均为n-1，且无自圈、无平行边第10页，本讲稿共25页图的基本概念n补图n有图G=及其生成子图G=，若是完全图，且EE=，则称G是G的补图nG的补图的补图是其自身第11页，本讲稿共25页图的基本概念n图的同构n有图G=和G=，若结点间存在一一对应关系，且这种对应关系也体现在表示边的结点对中，则G、G同构n有图G=和G=，若存在双射f：V V 和双射g：EE,使得对于任意eE及v1,v2 V都有：g(e)=(f(v1),f(v2),若e=(v1,v2)nP.120,图8.10,图8.11第12页，本讲稿共25页图的基本概念n多重图n含平行边的图叫做多重图n不含平行边且不含自圈的图叫做简单图nP.122 图8.13n带权图（加权图）n描述边的一些性质，因为边只代表结点间的连接关系；n举例：物流求最短路径第13页，本讲稿共25页通路、回路、连通性n先讨论有向图，若G=中有一个边的序列为(v1,v2)(v2,v3)(vk-1,vk)，即其中每条边均首尾相连，可简写为(v1,v2,v3vk-1,vk)，这是图G中的一个通路，其中v1叫起点、vk叫终点n允许出现相同的结点和边n各边全不同的通路叫做简单通路n各点全不同的通路叫做基本通路n基本通路必是简单通路，反之不然第14页，本讲稿共25页通路、回路、连通性n一条通路，若起点终点是同一个结点，则称之为回路；n各边全不同的回路叫做简单回路n各点全不同的回路叫做基本回路n一个通路，若删除其中所有回路，则得基本通路；一个回路，若删除除自己外的所有回路，则得基本回路n定理：对于有向(n,m)图中，任何基本通路长度均小于等于n-1，任何基本回路的长度小于或等于n第15页，本讲稿共25页通路、回路、连通性n可达性n从一个有向图的结点V1到V2之间若存在一个通路，则称从V1到V2是可达的n结点间的距离n两个可达结点间可能存在多条通路，最短的（经过的边数最少）那条通路中边的个数称为两结点间的距离第16页，本讲稿共25页通路、回路、连通性n对于无向图n可以化解为有向图，于是上述定义均可应用到无向图中第17页，本讲稿共25页通路、回路、连通性n连通性n无向图：若任何两个结点间均可达，则称为连通图连通图，否则叫做非连通图n有向图：若任何两个结点间均相互可达，则称为强连通图强连通图，若任何两个结点间至少有一个方向是可达的，则称为单向连通图单向连通图，若忽略掉边的方向得到的无向图是连通的，则称为弱连通图弱连通图nP127 图8.20第18页，本讲稿共25页欧拉图n图G的一个回路，若通过G的每条边一次，则称为欧拉回路，具有这种回路的图叫做欧拉图n定理：无向连通图G是欧拉图的充分必要条件是G的每个结点均有偶数度数n必要性：经过一个结点，该结点度数就加2n充分性：存在回路，存在简单回路，反证法证明最大简单回路是欧拉回路第19页，本讲稿共25页欧拉图n若通过G的每条边一次的通路（不是回路）称为欧拉通路n定理：无向连通图G中结点vi,vj间存在欧拉通路的充分必要条件是vi,vj的度数为奇数，而其他结点度数均为偶数n在vi,vj间加一条边，则可构造欧拉回路n图8.21第20页，本讲稿共25页欧拉图n欧拉图应用题n例8.6、8.7、8.8第21页，本讲稿共25页汉密尔顿图n欧拉回路(通路)是简单的回路(通路)n汉密尔顿回路(通路)是基本的回路(通路)n周游世界游戏：图8.25,8.26第22页，本讲稿共25页汉密尔顿图n定义：若图G的一个回路，通过G的每个点一次，则称为汉密尔顿回路，具有这种回路的图叫做汉密尔顿图n定义：若通过G的每个结点一次的通路（不是回路）称为汉密尔顿通路第23页，本讲稿共25页汉密尔顿图n一个图是汉密尔顿图的充分必要条件仍未解决n有一些充分条件和必要条件n考察右边的图第24页，本讲稿共25页作业nP140n8.2 按完全无向图n8.4n8.5第25页，本讲稿共25页
