离散数学图论.

第八章图论图论起源：哥尼斯堡七桥问题：能否从一处出发，经过七座桥一次，又回到出发点？图论的应用非常广泛，主要有运筹学、网络理论、信息论、控制论、及计算机科学等等。世界数学难题——哥尼斯堡七桥问题18世纪时，欧洲有一个风景秀丽的小城哥尼斯堡(今俄罗斯加里宁格勒)，那里的普莱格尔河上有七座桥,将河中的两个岛和河岸连结，城中的居民经常沿河过桥散步，于是提出了一个问题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？大家都试图找出问题的答案，但是谁也解决不了这个问题。这就是哥尼斯堡七桥问题，一个著名的图论问题。1727年在欧拉20岁的时候，被俄国请去在圣彼得堡（原列宁格勒）的科学院做研究。他的德国朋友告诉了他这个曾经令许多人困惑的问题。欧拉并没有跑到哥尼斯堡去走走。他把这个难题化成了这样的问题来看：把二岸和小岛缩成一点，桥化为边，于是“七桥问题”就等价于下图中所画图形的一笔画问题了，这个图如果能够一笔画成的话，对应的“七桥问题”也就解决了。哥尼斯堡七桥问题城的四个陆地部分分别表以A，B（大岛），C，D（小岛)，将陆地设想为图的顶点，把桥画成相应的边，则问题等价于在图中从某一顶点出发找一条回径，通过它的每条边一次且仅一次，并回到原顶点。（你能否看出，此问题无解，即这样的走法不存在呢？）ABCD主要内容1.图的基本概念2.路径与回路3.图的矩阵表示4.几种特殊的图5.无向树,有向树8.1图的基本概念定义1一个图G是一个三重组V,E,，其中V是图G的顶点集合，E是图G的边集合，是从边集E到顶点偶对集合的函数，即边与点的对应关系。例1设G=V,E,,其中:V={a,b,c,d,e},E={e1,e2,e3,e4,e5,e6,e7}(e1)={a,d},(e2)={c,d},(e3)={b,d}(e4)={a,c},(e5)={b,c},(e6)={a,d},(e7)={b,b}则G可用图表示为:acbde1e2e3e4e5e6e7e基本概念若边e对应的是有序偶a,b，则称e为有向边。在画图形时，有向边a,b,就画一条从a出发箭头指向b的弧。有向边e称为弧，a叫弧e的起点，b叫弧e的终点，统称为端点。称e关联于顶点a和b；称a和b是邻接的。若边e对应的是无序偶{a,b},则称e为无向边。同样称a,b是端点，称e关联于顶点a和b；称a和b是邻接的。每一条边都是有向边的图，称为有向图。每条边都是无向边的图，称为无向图。图中不与任何顶点邻接的点称为孤立点。全都是孤立点的图称为零图。关联于一个顶点的边称为自回路，也称为自圈。在有向图中，若同始点和同终点的边多于一条，则这几条边称为平行边。没有平行边和自圈的图称为：简单图。在无向图中，两顶点间若多于一条边，则称这几条边为平行边。图G中，顶点的个数称为图G的阶基本概念定义2对图G的每条边都赋以一个数值的图，称为加权图。定义3在有向图中，对于顶点v，以v为起点的边的数目，称为v的出度（引出次数）。记为：deg+(v),以v为终点的边的数目称为v的入度（引入次数）,记为：deg-(v)，v的出度和入度之和称为v的度。记为deg(v)。即deg(v)=deg+(v)+deg-(v)对于无向图，顶点v的度就是与v相关联的边的条数。孤立点的度为0.约定：含有n个顶点和m条边的图，记为（n,m）图。定理1设G是有m条边，则它的所有顶点的度之和为2m基本概念定理2在图中，度为奇数的顶点有偶数个。定义4各顶点的度都相同的图，称为正则图。各顶点的度都为k的图，称为k度正则图。对于n阶无向图，n-1度正则图称为n阶无向完全图。简称为n阶完全图。记为：Kn（在完全图中，每两个顶点之间都有边相连）对于n阶有向图，若每个顶点的出度和入度都为n-1,则称之为n阶有向完全图。图的同构对于两个图G和G,如果它们的顶点之间存在一一对应关系，而且这种关系保持了两顶点间的邻接关系（在有向图中，还保持了边的方向）和边的重数，则这两个图是同构的。同构的图除了点和边的名称不同外，实际上代表同样的组织结构。由于图形的顶点位置和连线长度都可任意选择，同一个图可能画出不同的形状来，因而引出图同构的概念。如下面两个图同构:abcdacbd图的运算图的常见运算有并、交、差、环和，补图等。定义如下：定义5设图G1=V1,E1和图G2=V2,E2。（1）G1与G2的并：记为:G1∪G2=V1∪V2,E1∪E2（2）G1与G2的交：记为：G1∩G2=V1∩V2,E1∩E2（3）G1与G2的差：定义为图：G3=V3,E3,E3=E1-E2,V3=(V1-V2)∪{E3中边与V3所关联的点}。记为：G1-G2（4）G1与G2的环和，记为G1G2=G1∪G2-G1∩G2子图与补图定义6设G=V,E,G=V,E都是图，如果非空集合VV或EE，则称G是G的子图；如果VV或EE，则称G是G的真子图；如果V=V,EE,则称G是G的生成子图。(3)为(1)的生成子图，(2)为(1)的真子图。123补图定义7设图G=V,E,若G是n阶无向图，则G的补图为：KnG。即为n阶完全无向图与G的差。若G是n阶有向图，则G的补图为：n阶有向完全图与G的差。（这一节介绍了图的一些基本概念，如图的定义，图中顶点的度，图的所有顶点的度为边的2倍，且一个图中有偶数个奇顶点，简单图等的定义，图的运算，子图，补图的一些概念。要掌握这些简单的定义）8.2路径与回路这一节将要引入路径的概念，以后还要引用简单路径、基本路径、简单回路、基本回路、及路径的长度概念及与路径相关的连通图，连通子图，及在有向图中的单向连通，强连通与弱连通的概念。求加权图中的最短路径的算法也是本节的一个重点。路径的基本概念定义1给定图G=V,E，设G中顶点和边的交替序列：=0e11e22…ell若满足：i-1和i是ei的端点(i=1,2,…l),则称之为从顶点0到l的路径，0和l分别称为此路径的起点和终点，中边的数目称为的长度。若中的所有边互不相同，则称为简单路径。若中所有顶点0,1,2,…,l互不相同，则称此路为径为基本路径。当0=l时，称为回路。若回路中所有的边互不相同，则称此回路为简单回路。通过各顶点不超过一次的回路为基本回路。路径长度定义2路径P中所含边的条数称为路径P的长度。长度为0的路径就是单独的点。定理：在一个具有n个顶点的简单图中，如果存在v1到v2的路径，则存在从v1到v2的长度不大于n-1的基本路径。如果从v1到v2的路径P不是基本路径，即表示里边有重复的点，那么删去P中所有的回路，直到没有重复点为止，即变为基本路径。而每个点至多在这基本路径中出现一次。所以这基本路径的长度至多为n-1.设vi,vj是两个不同顶点，若存在从vi到vj的路径，则称vi,vj是连接的，称连接的所有路径中长度最小者为vi,vj的最短路径，最短路径的长度称为vi,vj之间的距离，记为d(vi,vj)，若不存在连接的路径时，定义d(vi,vj)=连通图定义3设G=V,E，且vi,vjV.如果存在从vi到vj的路径，则称从vi可达vj.(因vi可看作长度为0的路径，即从vi可达vi,即任何顶点都是自己可达)。定义4在无向图中，如果任何两个顶点都可达，则称之为连通图。如果G的子图是连通图，称之为连通子图。一个无向图如果不是连通图，就是由若干个连通子图构成。定义5在有向图G中，如果在任两个顶点中，存在从一个顶点到另一个顶点的路径，则称图G为单向连通的。如果在G中，任何两个顶点都互相可达，则称G为强连通的。如果它的基础图（底图）是连通的，则称之为弱连通的。显然，强连通的，也是单向连通的，也是弱连通的。强分图（单向分图，弱分图）定义6在有向图G=V,E中，G′是G的子图，若G′是强连通的（单向连通的，弱连通的），且没有包含G′的更大的强连通子图（单向连通子图，弱连通子图），则称G′是G的强分图（单向分图，弱分图）图的连通性的应用有向图的连通性问题在计算机中是经常用到的。例1此例说明图的连通性在计算机中的应用设At={P1,P2,P3,P4}是t时刻运行的程序集合，Rt={r1,r2,r3,r4}是t时刻所需的资源集合。P1据有r4且请求资源r1;P2据有r1且请求资源r2和r3P3据有r2且请求资源r3，P4据有资源r3且请求资源r1和r4则资源分配图可表示如下：r3r2r1r4P2P1P41P31P4P2显然，当且仅当分配图Gt包含多于一个顶点的强分图时，计算机系统在t时刻死锁。显然图示状态是死锁状态。以后我们可用矩阵方法来识别是否包含多于一个顶点的强分图。求加权图中的最短路径问题定义7设图G=V,E,。若W:ER,则称G,W为加权图。若e∈E,称W(e)为边e的加权长度。路径中所有边的加权长度之和称为该路径的加权长度。从顶点v到顶点s的路径中加权长度最小者称为从v到s的最短路径。最短路径的加权长度为从v到s的加权距离。若从v不可达s,则称它们的加权距离为Dijkstra算法Dijkstra给出了求从顶点s至顶点t的加权距离的如下算法：1）若v≠s,则（v）=,否则（v）=0；T=V（顶点集合）//初如化顶点的值,初如化集合T2)在T中寻找值最小的顶点u.3）如果u=t,则算法结束。4)考虑在集合T中且与u邻接的顶点v,若（v）（u）+W(e)(e连接u和v)，则修改顶点v的值。即（v）=（u）+W(e)(要考虑所有在T中又与u邻接的点)5）T=T-{u}(不再考虑顶点u)；转向2当算法结束时，（t）即为从s到t的加权距离。Zhengjin,CentralSouthUniversity23Zhengjin,CentralSouthUniversity24Zhengjin,CentralSouthUniversity25Zhengjin,CentralSouthUniversity26Zhengjin,CentralSouthUniversity27Zhengjin,CentralSouthUniversity28Zhengjin,CentralSouthUniversity29Zhengjin,CentralSouthUniversity30Zhengjin,CentralSouthUniversity31Zhengjin,CentralSouthUniversity32Zhengjin,CentralSouthUniversity338.3图的矩阵表示定义1设G=V,E是无向图，且无平行边，其中V={v1,v2,…,vn},定义一个nn的矩阵A,其中各元素aij为：1如果vi,vjEaij=0如果vi,vjE称这样的矩阵为图G的邻接矩阵。（即若两点间有边相连，则对应的为1，无边相连，则对应的为0）图的邻接矩阵设图G如右图所示，则其邻接矩阵为：0000000111010110111101110edcbaedcbaA=bde1e2e3e4e5e6e7eac有向图的矩阵表示与无向图相对应，有向图也有类似的矩阵表示。如右图：v2v3v4v1010100011100001143214321vvvvvvvvA=有向图的邻接和可达性矩阵性质1A不一定是对称矩阵。性质2A的第i行元素之和为:deg+(vi)，的第j列元素之和为deg-(vj).定义设v1,v2,…,vn是简单有向图的顶点，则称P是G的可达矩阵，其中：Pij=1若vi,vj可达0,若vi,vj不可达有向图的可达性矩阵特点性质1P是以0，1为元素的矩阵，其主对角线上的元素全为1，但不一定是对称的。性质2设A是G的邻接矩阵，则(还记得关系的幂运算吗?！！)P=A0∨A1∨…∨An-1性质3（1）P的元素全为1是为强连通的充分必要条件（2）PPT的元素全为1是为单