离散数学之图论（1）.ppt

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