离散数学之图论.ppt

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