图论及其应用ch1-2

主讲：张丽丽图论及其应用E-mail:lilzhang@2/7/20231DerenChen,ZhejiangUniv.两个有趣的问题1.任意一群人中（人数不小于2），总有两人在该人群中认识相同的朋友数。2.在一次象棋比赛中，任意两名选手间至多下一盘，试证总存在两名选手，他们下过的盘数相同。问题1：如何用学过的知识解答上述问题？问题2：上述问题的解答是否相同？若不同，区别在哪？2/7/20232DerenChen,ZhejiangUniv.Keyweb/AMuseum/math/index.htm中国数字科技馆，数学，信息科学等2/7/20233DerenChen,ZhejiangUniv.1图的基本概念/1.1图论发展史

图论是组合数学的一个分支，也是近几十年来最活跃的数学分支之一.到目前为止，它已有二百六十多年的发展历史.图论的发展历史大体可以分为三个阶段：第一阶段是图论的萌芽阶段，它从十八世纪中叶到十九世纪中叶.这时，图论的多数问题是围绕游戏而产生的，其代表性的工作就是Königsberg七桥问题.1736年L.Euler发表了他著名的Königsberg七桥问题的论文，这是图论的第一篇文章.2/7/20234DerenChen,ZhejiangUniv.第二阶段从十九世纪中叶到二十世纪中叶.在此阶段，图论问题大量出现.如著名的四色问题、Hamilton问题以及图的可平面问题等.在第二个阶段还应该特别提到Cayley把树应用于化学领域，Kirchhoff用树去研究电网络的分析问题.在漫长的300年中，图论几乎停留在数学游戏阶段.虽然这阶段里21岁的G.Kirchhoff在1847年从电网络问题，A.Cayley在1857年从计算有机化学的同分异构等不止一次地建立起图论的基本概念，但是直到1936年D.König发表的经典著作<<有限图与无限图理论>>才有了图论的第一本专著.

2/7/20235DerenChen,ZhejiangUniv.二十世纪中叶以后是图论发展的第三阶段，即图论的应用阶段.由于生产管理、军事、交通运输、计算机网络、计算机科学、数字通讯、线性规划、运筹学等方面提出的实际问题的需要，特别是许多离散性问题的出现、刺激和推动，以及由于有了大型电子计算机，而使大规模问题的求解成为可能，图论及其应用的研究得到了飞速的发展.这个阶段的开创性工作是以Ford和Fulkerson建立的网络流理论为代表的.图论与其它学科的相互渗透，以及图论在生产实际中广泛地应用，都使图论的发展更加充满活力.2/7/20236DerenChen,ZhejiangUniv.几个有趣的图论问题

Königsberg七桥背后的故事Königsberg七桥位于前苏联的加里宁格勒，历史上曾是德国东普鲁士省的省会，霹雷格尔横穿城堡，河中有两个小岛B与C，并有七座桥连接岛与河岸及岛与岛（见图）。是否存在一种走发，从四块陆地中的任意一块开始，通过每一座桥恰好一次再回到起点。这就是著名的Königsberg七桥问题，即一笔画问题；也是图论的起源。2/7/20237DerenChen,ZhejiangUniv.2/7/20238DerenChen,ZhejiangUniv.四色问题为了能够迅速地区分一个平面地图或球面地图上的各个国家（假设这些国家在地图上都是连通的），需要用若干种颜色对这些国家着色，使得具有公共边界的两个国家涂染不同的颜色.那么，要保证每张地图都能如此着色，最少需要多少种颜色？这个问题是1850年被一名刚毕业的大学生FrancisGuthrie首先提出的，直到1976年，四色问题被美国Illinois大学的K.Appel和W.Haken用计算机证明是正确的，这个证明令数学界震惊，它用了1200多小时，作出100亿个独立的逻辑判断.尽管有了这个机器证明，但它仍然是数学上未解决的问题之一.2/7/20239DerenChen,ZhejiangUniv.Hamilton问题Hamilton问题是图论中一直悬而未解的一大问题。它起源于1856年，当时英国数学家Hamilton设计了一种名为周游世界的游戏。他在一个实心的正十二面体的十二个顶点上标以世界上著名的二十座城市的名字，要求游戏者沿十二面体的棱从一个城市出发，经过每座城市恰好一次，然后返回到出发点，即“绕行世界”。正十二面体的顶点与棱的关系可以用平面上的图表示，把正十二面体的顶点与棱分别对应图的顶点与边，就得到正十二面体图。2/7/202310DerenChen,ZhejiangUniv.正十二面体Peterson图2/7/202311DerenChen,ZhejiangUniv.旅行售货员问题给出城市之间的距离，要求一位推销员从某一城市出发，周游每个城市一次，然后回到出发的城市，并且选的路径最短。这是一个图论优化问题，最早由美国数学家威特涅于1934年在普林斯顿一次讨论班上提出。1954年几位美国数学家写了第一篇论文，用线性方程的方法解决了49个城市的旅行售货员问题。后来也有不少论文讨论这个问题，在理论和应用上都很有价值。2/7/202312DerenChen,ZhejiangUniv.生活中，人们常常需要考虑一些对象之间的某种特定的关系.如某区域内，两城市之间有无交通线；一群人中，两个人之间相识或不相识等等.这种关系是对称的，即如果甲对于乙有某种关系，则乙对于甲也有这种关系.可以用一个图形来描述给定对象之间的某个关系：我们用平面上的点分别表示这些对象，若对象甲和乙有关系，就用一条线连接表示甲和乙的两个点.这种由一些点与连接其中某些点对的线所构成的图形就是图论中所研究的图.图/Graph：可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。1.2图的定义2/7/202313DerenChen,ZhejiangUniv.无向图（简称图）:一个图是指一个有序三元组(V(G),E(G),),其中V(G)是一个非空有限集，Ｅ(G)是与Ｖ(G)不相交的有限集合,是关联函数，它使E(G)中每一元素对应于V(G)中的无序元素对（可以相同）几个重要定义有A(D)有实际上,有向图即将无向图中的无序对看成有序对.其中有向图对应的无向图称为有向图的基础图。其中V(G)称为顶点集,E(G)称为边集（A(D)又称为弧集）.令p(G)=|V(G)|,q(G)=|E(G)|,分别称为图的阶和边数。举例说明。A(D)A(D)有向2/7/202314DerenChen,ZhejiangUniv.如果一个图的顶点集和边集都是有限集则称该图为有限图,否则称为无限图.只有一个顶点所构成的图称为平凡图,其它的称为非平凡图.如果一个图中没有环也没有重边称为简单图。2/7/202315DerenChen,ZhejiangUniv.图/graph;有向图/directedgraph;相邻/adjacent，关联/incident；顶点/vertex;孤立的/isolated，环/loop。在有向图G中，若e=（ａ，ｂ）∈Ｅ，即箭头由ａ到ｂ，称ａ相邻到ｂ，或a关联或联结b。a称为e的起点/initialvertex，b称为e的终点/terminalorendvertex。2/7/202316DerenChen,ZhejiangUniv.1.严格有向图：既无自回路又无平行边的有向图。2.非对称有向图：在两点间最多有一条有向边，但允许有自回路的有向图。3.对称有向图：对于图中每一边(a,b),总存在另一边(b,a)的有向图。4.完全有向图:(1)完全对称有向图：一个从任一点到其他点有一条且仅有一条有向边的简单图；(2)完全非对称有向图：任何两点有一条且只有一条有向边的非对称图。有向图的种类：2/7/202317DerenChen,ZhejiangUniv.有向图在成对比较中的应用

在很多实验中，特别在社会科学领域，要求人们通过对事物的两两比较排出它们的名次。这种方法称为成对比较法。例如，测定对音乐作品的个人爱好时，每一次对一个主题取出两个作品，问一个人他喜欢哪一个。记录了n个作品成对比较所有n(n-1)/2种可能的结果后，实验者就能根据某人的爱好排出n个作品的品次。Kendall在1948年做的一个分类实验时，对六种不同的狗食排名次。每天在六种食品中任选两种喂狗。实验安排了15天，所有可能配对的食物都被试过，在图中，一条边是从喜欢的食物引向比较不喜欢的食物，这样的图称为优化图。2/7/202318DerenChen,ZhejiangUniv.

有向图在竞赛中的应用在单循环赛中，每个运动员和所有其他运动员比赛，比赛结果可以用有向图表示。图中一条顶点a指向b的边表示运动员a胜过运动员b。所以完全非对称图又称为竞赛图。按得分排名次：根据运动员得分排名次，得分是运动员在比赛中胜的局数，反映在有向图中是点的出度。2/7/202319DerenChen,ZhejiangUniv.1.3顶点的度顶点的度：在无向图G中,与a相邻的顶点的数目称为v的度/degree,记为d(v)。分别用表示G中的最小度和最大度。度为零的顶点称为孤立顶点。在有向图G中,以v为终点的边的条数称为v的入度/in-degree,记为d–(v)。以v为起点的边的条数称为v的出度/out-degree,记为d+(v)。有向图中，V的度数=d–(v)+d+(v),2/7/202320DerenChen,ZhejiangUniv.定理1.3.1(Handshaking)设无向图G=（V，E）有e条边，则G中所有顶点的度之和等于e的两倍。证明思路：考虑每条边在求和中的贡献。定理1.3.2无向图中度为奇数的顶点个数恰有偶数个。证明思路：将图中顶点的次分类，再利用定理1。定理1.3.3设有向图G=（V，A）有e条边，则G中所有顶点的入度之和等于所有顶点的出度之和，也等于e。证明思路：考虑每条边在求和中的情况。即Σd(v)=2e即Σd¯(v)=Σd+(v)=e记住了吗？几个重要定理2/7/202321DerenChen,ZhejiangUniv.推论2/7/202322DerenChen,ZhejiangUniv.例1证明任何一群人中，有偶数个人认识其中奇数个人.(匈牙利数学竞赛试题)[证]用n个顶点表示n个人.如果两个人相识，就用一条线把他们对应的一对顶点连起来，这样就得到了一个图G.每一个人所认识的人的数目就是他对应的顶点的次，于是问题就转化为证明图G中奇点的个数为偶数，而这正是定理1.3.2的结论.2/7/202323DerenChen,ZhejiangUniv.例2设是平面上n个点，其中任意两点的距离至少是1，证明至多有3n对点，每对点的距离恰好是1.[证]以这n个点为顶点作图G，使得与相邻当且仅当与的距离恰好是.于是，距离恰为1的点对的数目就是G的边数q.显然，在G中的邻点一定在以为圆心，以1为半径的圆周上.由于任一对点的距离至少是1,于是，所以即.结论成立例22/7/202324DerenChen,ZhejiangUniv.例3在一次围棋擂台赛中，双方各出n名选手。比赛的规则是双方先各自排定一个次序，设甲方排定的次序为乙方排定的次序为2/7/202325DerenChen,ZhejiangUniv.1.4子图与图的运算子图：Ｇ＝(Ｖ,E)是图,若Ｇ’=(Ｖ’,Ε’)也是图且满足:(1)Ｖ’Ｖ；(2)Ｅ’Ｅ；则称Ｇ’为Ｇ的子图/subgraph。生成子图：当Ｖ’＝Ｖ时,称Ｇ’为Ｇ的生成子图。真子图:当Ｅ’≠Ｅ或Ｖ’≠Ｖ时,称Ｇ’为Ｇ的真子图。导出子图:设Ｖ’Ｖ,由Ｖ’内的所有顶点及其顶点之间的所有边得到的子图称为G的导出子图（由顶点确定）；边导出子图：设Ｅ’Ｅ,由边集E’的所有边及其边的顶点集得到的子图称为G的边导出子图(由边确定）.举例说明其区别。2/7/202326DerenChen,ZhejiangUniv.相对补图/complementarygraph：Ｇ＝（Ｖ，Ｅ）是图，Ｇ’＝（Ｖ’，Ε’）是Ｇ的子图，Ｅ”＝Ｅ－Ｅ’，Ｖ”＝V－V’或是Ｅ”中边所关联的所有顶点集合，则Ｇ”＝（Ｖ”，Ｅ”）称为Ｇ’关于Ｇ的相对补图。补图：关于完全图的子图的补图称为此子图的绝对补图，若子图记为Ｇ，则补图记为。2/7/202327DerenChen,ZhejiangUniv.图的运算图的并/union：Ｇ＝（Ｖ，Ｅ）和Ｇ’＝（Ｖ’，Ε’）是两个简单无向图，它们的并图ＧＧ’定义为ＧＧ’=（Ｖ’Ｖ，Ｅ’Ｅ）.图的和：Ｇ＝（Ｖ，Ｅ）和Ｇ’＝（Ｖ’，Ε’）是两个不相交的简单无向图，称Ｇ+Ｇ’为G和G’的和，其中Ｇ+Ｇ’=（Ｖ’Ｖ，Ｅ’ＥＥ’’).图的交：Ｇ＝（Ｖ，Ｅ）和Ｇ’＝（Ｖ’，Ε’）是两个简单无向图，称ＧＧ’为G和G’的交，其中ＧＧ’=（Ｖ’Ｖ，Ｅ’Ｅ).举例说明。2/7/202328DerenChen,ZhejiangUniv.1.5特殊图类完全图/completegraph：图G中的每对不同顶点之间恰有一条边。空图/emptygraph：边集为空的图。问题：完全图的补图是怎样的图？设G=(V,E)是p阶图,若V可以划分为m个非空2/7/202329DerenChen,ZhejiangUniv.补充特殊图类练习：画出一个完全二部图/bipartitegraph。轮图/wheel:由一个圈添加一个新顶点,并且把这个顶点与圈的所有顶点相连得到的图称为轮，新的边称为辐。正则图：每个顶点的度都等于k的图。线图（边图）/linegraph：图G的线图是以为E(G)顶点集的图,其中两个顶点相邻当且仅当它们在G中是相邻的边。练习:各类特殊图所含边数的情况如何？2/7/202330DerenChen,ZhejiangUniv.1.6图的矩阵表示与同构图G表示的三种方法：（1）集合表示（2）邻接表（adjacencylist）表示（3）矩阵（matrix）表示1、邻接矩阵（adjacencymatrix）表示2、关联矩阵（incidencematrix）表示2/7/202331DerenChen,ZhejiangUniv.关联矩阵及其举例说明关联矩阵：设G=(V,E)的顶点集和边集分别为关联矩阵的性质:(1)B(G)的每一列元素之和均为2；(2)B(G)的每一行元素之和等于对应顶点的度数。举例说明。2/7/202332DerenChen,ZhejiangUniv.邻接矩阵及同构2/7/202333DerenChen,ZhejiangUniv.邻接矩阵的性质(1)主对角线所有元素都是0<=>图中无回路;(2)若无环,顶点的度等于M中对应行或列中的1的个数。(3)M是对称的,所以如果两行交换位置，那末相应的列也应交换位置。(4)图G是分离图,且有两个分支G1和G2<=>它的邻接矩阵能划分成分块对角矩阵。(5)给出任何一个n阶对称（0，1）方阵Q,总能构造一个具有n个顶点的图G，使得Q是G的邻接矩阵。2/7/202334DerenChen,ZhejiangUniv.从定义可以看出，两个同构图必然具备下列性质：（1）具有相同的顶点数；（2）具有相同的边数；（3）对于一个给定的度数具有相同的顶点数。反之不成立。举例说明。同构图的性质2/7/202335DerenChen,ZhejiangUniv.例1下面两个图不同构.2/7/202336DerenChen,ZhejiangUniv.例2证明：图G和图H同构.2/7/202337DerenChen,ZhejiangUniv.同构判定算法（用邻接矩阵）1、根据图确定其邻接矩阵（I)2、计算行次：矩阵每行１的个数，（对应于出次）和列次：（对应于入次）3、不考虑出现的次序不同，若行次与列次不同，则必不同构，否则继续4、同时交换其一矩阵的ｉ行和ｊ行，ｉ列和ｊ列。若此矩阵能变成与另一矩阵相同，则同构。对所有顶点的排列都试过，仍不相同，则不同构。2/7/202338DerenChen,ZhejiangUniv.性质：两个图G与H是同构的充要条件是存在一个置换矩阵P,使得M(G)=P'M(H)P.2/7/202339DerenChen,ZhejiangUniv.作业：每人做一题，其中学号为1-15号对应1-15题；其它学号的同学按照学号最后一位数字与题目最后一位数字对应。注意：下次上课全部上交，作业写在纸上，自己保管好。2/7/202340DerenChen,ZhejiangUniv.2图的连通性/2.1途径、路和圈途径：Ｇ中相邻边的序列（Ｖ0,Ｖ1），（Ｖ1,Ｖ2），…（Ｖk-1,Ｖk）称为一条途径.此途径长度为ｋ.也可以（Ｖ0，Ｖ1，…，Ｖk）表示道路,Ｖ0为起点，Ｖk为终点，起点与终点相同时称为闭途径。迹/trace：一条边不重复出现的途径称为迹,当Ｖ0=Ｖk时称为闭迹。路/Path

:一条内部顶点不重复出现的途径称为路；路所含的边数称为路的长度。回路（圈）/Cycle：一条内部顶点不重复出现的闭路称为圈。长度为奇数的圈称奇圈，否则称偶圈。2/7/202341DerenChen,ZhejiangUniv.其他概念顶点间的距离：任意两点u与v之间的最短路。图的直径:指G的两个顶点之间的最大距离。完全图的直径是？其他特殊图类呢？练习。图的围长：图中最短圈的长度。图的周长：图中最长圈的长度。有向图的相关概念可以类似定义。2/7/202342DerenChen,ZhejiangUniv.相关定理及其证明2/7/202343DerenChen,ZhejiangUniv.有向图中路的应用例有A,B,C三个瓶，分别能装油8L,5L和3L.如果A装满油，B和C是空的，怎样以最快的速度平分A中的油？[解法]我们用三位数码表示A,B,C三个瓶子装油的情况，又因为三位数码之和不变，所以可以用后两位数码表示三个瓶子装油的情况.例如：（0，0）表示初始状态.根据题意：共有十六种可能的状态，用这16个状态为顶点作图G，使得两个状态相邻当且仅当它们可以经过一次倒油相互转化.于是，问题就是要求从（0，0）到（4，0）的一条最短路.2/7/202344DerenChen,ZhejiangUniv.容易作出图G（如下图）：2/7/202345DerenChen,ZhejiangUniv.通过观察图得知共有两条从（0，0）到(4,0)的路：第一条:(0,0)(5,0)(2,3)(2,0)(0,2)(5,2)(4,3)(4,0);第二条:(0,0)(0,3)(3,0)(3,3)(5,1)(0,1)(1,0)(1,3)(4,0);从而，最快的速度平分即是最短的路所对应的过程，即第一条路的过程就是以最快的速度平分油的过程。能说出具体操作吗？2/7/202346DerenChen,ZhejiangUniv.连通/connectivity:设Ｇ＝(Ｖ,Ｅ),若存在一条从Ｖ0，到Ｖk的一条道路，则称Ｖ0到Ｖk连通。无向图的连通性:若图Ｇ中任两个不同顶点都连通，则称此无向图是连通的/connected,否则称为非连通图(分离图)。连通分支/connectedcomponents：图Ｇ可分为几个不相连通的子图，每一子图本身都是连通的。称这几个子图为Ｇ的连通分支。

2.2连通图、非连通图和成分

2/7/202347DerenChen,ZhejiangUniv.说明：对无向图而言，若Ｖ0到Ｖk可达，则Ｖk到Ｖ0也可达。对有向图而言则未必。有向图的连通性：(1)弱连通：Ｇ＝（Ｖ，Ｅ）对应的无向图是连通图，则称Ｇ为弱连通/weaklyconnected。(2）强连通：若Ｇ＝（Ｖ，Ｅ）中任两点间都有路，即对ａ与ｂ，ａ到ｂ可达，ｂ到ａ可达，称Ｇ为强连通/stronglyconnected。(3)单向连通：如果有向图D的任何两个顶点至少由一个顶点到另一个顶点可达,则称D是单向连通的。

有向图的连通性

2/7/202348DerenChen,ZhejiangUniv.例：用图描述一台自动售货机，只用５分，１０分二种硬币，满１５分后压按钮，选择一块巧克力，钱多了不找还。2/7/202349DerenChen,ZhejiangUniv.

顶点:ａ：０分边：５：投５分ｂ：５分１０：投１０分ｃ：１０分ｐ：压按扭动作ｄ：≥１５分表示已投入钱的状态表示一种动作自动售货机：有向加权图描绘得很清楚（1）钱数不够，压按扭，不起作用（2）钱数够了,压按扭,给过糖果回到０分状态（3）钱超过１５分，再加钱白加2/7/202350DerenChen,ZhejiangUniv.一个简单定理的应用定理2.2.1:设G是p阶简单图,每个顶点的度至少是[p/2],则G是连通图。例1:用一些圆面覆盖平面上取定的2n个点。试证：若每个圆面至少覆盖n+1个点则任两个点能由平面上的一条折线所连接，而这条折线整个地被某些圆面覆盖。证明：构造相应的图，得到顶点的最小度，应用定理即可证明。2/7/202351DerenChen,ZhejiangUniv.附加定理定理2如果一个图只有两点的度数是奇数，那末这两点间必有一条通路。2/7/202352DerenChen,ZhejiangUniv.定理2.2.2：一个有n个顶点和k个成分的简单图最多有(n-k)(n-k+1)/2条边.2/7/202353DerenChen,ZhejiangUniv.

在邻接矩阵中，若ａij＝１，表明Ｖi到Ｖj有一条边，即Ｖi到Ｖj可达；若ａij＝０说明Ｖi到Ｖj没有道路.若通过其他点中转，也有可能连通。作邻接矩阵的普通矩阵乘法：用邻接矩阵讨论连通性2/7/202354DerenChen,ZhejiangUniv.

ｂij的值表示Ｖi到Ｖj长为２的途径的条数;一般地，就有：Ａm的元素ｍij表示Ｖi到Ｖj长为ｍ的途径的条数。定理2.2.3:设M(G)是G的邻接矩阵，则G中连接Ｖi到Ｖj长为ｍ的途径的条数等于Ａm的元素ｍij，其中Ａm是矩阵A自身作m次乘法得到的矩阵。推论:若G是简单图，则对每一个顶点vi,i=1,2,…,p有dG(vi)=aii(2)，即矩阵A自身作2次乘法得到的矩阵的对角线元素。2/7/202355DerenChen,ZhejiangUniv.邻接矩阵与连通性定理2.2.4:阶至少为3的图G是连通的充要条件为R(G)中的每个元素都不等于零，其中R(G)=M(G)+M2(G)+…+Mp-1(G)。定理2.2.5：设D是连通的有向图，则D是强连通的当且仅当D的每条弧都含在一个有向回路中。（了解）2/7/202356DerenChen,ZhejiangUniv.顶点割:若V的子集V’使得G-V’不连通,则V’称为G的顶点割.k顶点割是指有k个元素的顶点割.

连通度:若G不是完全图,则G所有顶点割中的最小的k,称为G的连通度,记为;否则定义为v-1.若 ,则称G为k连通的.2.3连通度2/7/202357DerenChen,ZhejiangUniv.边割:若E(G)的子集E’使得G-E’不连通,则E’称为G的边割.K边割是指有k个元素的边割.边连通度:G的所有k边割中最小的k.若G是平凡的,则定义为0.若 ,则称G为k边连通的.边连通度2/7/202358DerenChen,ZhejiangUniv.连通度和边连通度的等价定义（更实用）等价定义1：图G是k连通的当且仅当对任意一个点数不超过k-1的顶点子集V'，G-V'仍然连通。等价定义2.1：图G是k边连通的当且仅当对任意一个边数不超过k-1的边子集E'，G-E'仍然连通。等价定义2.2：图G是k边连通的当且仅当对任一非空真子集S,均有|[S,Ŝ]|≥k，其中[S,Ŝ]表示一个顶点在S中一个顶点在Ŝ中的所有边集,Ŝ是S的补集。2/7/202359DerenChen,ZhejiangUniv.几者之间的联系2/7/202360DerenChen,ZhejiangUniv.几者之间的联系定理2.3.1:对任意简单图，有（定理证明无需掌握,要记熟三者之间的关系）问题：怎样的图可以取到等号呢？设G是p阶简单连通图，若对于G的任意四个顶点u,v,x,y,若|[{u,v},{x,y}]|=0就有d(u)+d(v)+d(x)+d(y)≥2p-3,则事实上，还有很多图类满足第一个不等式中的等号关系，你能自己找到吗？(课后自己练习)2/7/202361DerenChen,ZhejiangUniv.几个重要定理G中一族路称为内部不相交的:如果G中任意两条路除起点和终点外没有公共顶点。定理2.3.2

一个阶不小于3的图是2连通的,当且仅当G的任意两个顶点至少被两条内部不相交的路所连.推论1若G是2连通图