图论及其应用ch1-2.ppt

《图论及其应用ch1-2.ppt》由会员分享，可在线阅读，更多相关《图论及其应用ch1-2.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Graph TheoryGraph Theory/图图图图论论论论E-mail:12/25/20221Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论两个有趣的问题两个有趣的问题1.任意一群人中（人数不小于任意一群人中（人数不小于2），总有两人），总有两人在该人群中认识相同的朋友数。在该人群中认识相同的朋友数。2.在一次象棋比赛中，任意两名选手间至多下在一次象棋比赛中，任意两名选手间至多下一盘，试证总存在两名选手，他们下过的一盘，试证总存在两名选手，他们下过的盘数相同。盘数相同。问题问题1：如何用学过的知识解答上述问题？：如何用学过的知识解答上述问题？问

2、题问题2：上述问题的解答是否相同？若不同，：上述问题的解答是否相同？若不同，区别在哪？区别在哪？12/25/20222Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论Key webKey webhttp:/ ZhangGraph TheoryGraph Theory/图图图图论论论论1 图的基本概念图的基本概念/1.1 图论发展史图论发展史 图图论论是是组组合合数数学学的的一一个个分分支支，也也是是近近几几十十年年来来最最活活跃跃的的数数学学分分支支之之一一.到到目目前前为为止止，它它已已有有二二百百六六十十多多年年的的发发展展历历史史.图图论论的的发发

3、展展历历史大体可以分为三个阶段：史大体可以分为三个阶段：第第一一阶阶段段是是图图论论的的萌萌芽芽阶阶段段，它它从从十十八八世世纪纪中中叶叶到到十十九九世世纪纪中中叶叶.这这时时，图图论论的的多多数数问问题题是是围围绕绕游游戏戏而而产产生生的的，其其代代表表性性的的工工作作就就是是KnigsbergKnigsberg七七桥桥问问题题.1736.1736年年L.EulerL.Euler发发表表了了他他著著名名的的KnigsbergKnigsberg七七桥桥问问题题的的论论文文，这这是是图图论论的第一篇文章的第一篇文章.12/25/20224Li-Li ZhangGraph TheoryGraph

4、Theory/图图图图论论论论第二阶段第二阶段从十九世纪中叶到二十世纪中叶从十九世纪中叶到二十世纪中叶.在此阶段，在此阶段，图论问题大量出现图论问题大量出现.如著名的四色问题、如著名的四色问题、HamiltonHamilton问题问题以及图的可平面问题等以及图的可平面问题等.在第二个阶段还应该特别提在第二个阶段还应该特别提到到CayleyCayley把树应用于化学领域，把树应用于化学领域，KirchhoffKirchhoff用树去研究用树去研究电网络的分析问题电网络的分析问题.在漫长的在漫长的300300年中，图论几乎停留年中，图论几乎停留在数学游戏阶段在数学游戏阶段.虽然这阶段里虽然这阶段里

5、2121岁的岁的G.KirchhoffG.Kirchhoff在在18471847年从电网络问题，年从电网络问题，A.CayleyA.Cayley在在18571857年从计算有机年从计算有机化学的同分异构等不止一次地建立起图论的基本概念，化学的同分异构等不止一次地建立起图论的基本概念，但是直到但是直到19361936年年D.KnigD.Knig发表的经典著作发表的经典著作才有了图论的第一本专著才有了图论的第一本专著.12/25/20225Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论二二十十世世纪纪中中叶叶以以后后是是图图论论发发展展的的第第三三阶阶段段

6、，即即图图论论的的应应用用阶阶段段.由由于于生生产产管管理理、军军事事、交交通通运运输输、计计算算机机网网络络、计计算算机机科科学学、数数字字通通讯讯、线线性性规规划划、运运筹筹学学等等方方面面提提出出的的实实际际问问题题的的需需要要，特特别别是是许许多多离离散散性性问问题题的的出出现现、刺刺激激和和推推动动，以以及及由由于于有有了了大大型型电电子子计计算算机机，而而使使大大规规模模问问题题的的求求解解成成为为可可能能，图图论论及及其其应应用用的的研研究究得得到到了了飞飞速速的的发发展展.这这个个阶阶段段的的开开创创性性工工作作是是以以FordFord和和FulkersonFulkerson建

7、建立立的的网网络络流流理理论论为为代代表表的的.图图论论与与其其它它学学科科的的相相互互渗渗透透，以以及及图图论论在在生生产产实实际际中中广广泛泛地地应用，都使图论的发展更加充满活力应用，都使图论的发展更加充满活力.12/25/20226Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论 几个有趣的图论问题几个有趣的图论问题 KnigsbergKnigsberg七桥背后的故事七桥背后的故事 KnigsbergKnigsberg七七桥桥位位于于前前苏苏联联的的加加里里宁宁格格勒勒，历历史史上上曾是德国东普鲁士省的省会，霹雷格尔横曾是德国东普鲁士省的省会，霹雷

8、格尔横穿穿城城堡堡，河河中中有有两两个个小小岛岛B B与与C C，并并有有七七座座桥桥连连接接岛岛与与河河岸岸及及岛岛与与岛岛（见见图图）。是是否否存存在在一一种种走走发发，从从四四块块陆陆地地中中的的任任意意一一块块开开始始，通通过过每每一一座座桥桥恰恰好好一一次次再再回回到到起起点点。这这就就是是著著名名的的KnigsbergKnigsberg七七桥桥问问题题，即即一一笔笔画问题；也是图论的起源。画问题；也是图论的起源。12/25/20227Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论12/25/20228Li-Li ZhangGraph The

9、oryGraph Theory/图图图图论论论论四色问题四色问题为了能够迅速地区分一个平面地图或球面地图上的各为了能够迅速地区分一个平面地图或球面地图上的各个国家（假设这些国家在地图上都是连通的），需要个国家（假设这些国家在地图上都是连通的），需要用若干种颜色对这些国家着色，使得具有公共边界的用若干种颜色对这些国家着色，使得具有公共边界的两个国家涂染不同的颜色两个国家涂染不同的颜色.那么，要保证每张地图都那么，要保证每张地图都能如此着色，最少需要多少种颜色？这个问题是能如此着色，最少需要多少种颜色？这个问题是18501850年被一名刚毕业的大学生年被一名刚毕业的大学生Francis Guthr

10、ieFrancis Guthrie首先提出首先提出的，直到的，直到19761976年，四色问题被美国年，四色问题被美国IllinoisIllinois大学大学的的K.AppelK.Appel和和W.HakenW.Haken用计算机证明是正确的，这个证明用计算机证明是正确的，这个证明令数学界震惊，它用了令数学界震惊，它用了12001200多小时，作出多小时，作出100100亿个独亿个独立的逻辑判断立的逻辑判断.尽管有了这个机器证明，但它仍然是尽管有了这个机器证明，但它仍然是数学上未解决的问题之一数学上未解决的问题之一.12/25/20229Li-Li ZhangGraph TheoryGraph

11、 Theory/图图图图论论论论Hamilton问题HamiltonHamilton问问题题是是图图论论中中一一直直悬悬而而未未解解的的一一大大问问题题。它它起起源源于于18561856年年，当当时时英英国国数数学学家家HamiltonHamilton设设计计了了一一种种名名为为周周游游世世界界的的游游戏戏。他他在在一一个个实实心心的的正正十十二二面面体体的的十十二二个个顶顶点点上上标标以以世世界界上上著著名名的的二二十十座座城城市市的的名名字字，要要求求游游戏戏者者沿沿十十二二面面体体的的棱棱从从一一个个城城市市出出发发，经经过过每每座座城城市市恰恰好好一一次次，然然后后返返回回到到出出发发

12、点点，即即“绕绕行行世世界界”。正正十十二二面面体体的的顶顶点点与与棱棱的的关关系系可可以以用用平平面面上上的的图图表表示示，把把正正十十二二面面体体的的顶顶点点与与棱棱分分别别对对应应图图的的顶顶点点与与边边，就就得到正十二面体图得到正十二面体图。12/25/202210Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论正十二面体正十二面体 PetersonPeterson图图12/25/202211Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论旅行售货员问题旅行售货员问题给出城市之间的距离，要求一位推销员从某一

13、给出城市之间的距离，要求一位推销员从某一城市出发，周游每个城市一次，然后回到出发城市出发，周游每个城市一次，然后回到出发的城市，并且选的路径最短。的城市，并且选的路径最短。这是一个图论优化问题，最早由美国数学家威这是一个图论优化问题，最早由美国数学家威特涅于特涅于19341934年在普林斯顿一次讨论班上提出。年在普林斯顿一次讨论班上提出。19541954年几位美国数学家写了第一篇论文，用线年几位美国数学家写了第一篇论文，用线性方程的方法解决了性方程的方法解决了4949个城市的旅行售货员问个城市的旅行售货员问题。后来也有不少论文讨论这个问题，在理论题。后来也有不少论文讨论这个问题，在理论和应用上

14、都很有价值和应用上都很有价值。12/25/202212Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论生生活活中中，人人们们常常常常需需要要考考虑虑一一些些对对象象之之间间的的某某种种特特定定的的关关系系.如如某某区区域域内内，两两城城市市之之间间有有无无交交通通线线；一一群群人人中中，两两个个人人之之间间相相识识或或不不相相识识等等等等.这这种种关关系系是是对对称称的的，即即如如果果甲甲对对于于乙乙有有某某种种关关系系，则则乙乙对对于于甲甲也也有有这这种种关关系系.可可以以用用一一个个图图形形来来描描述述给给定定对对象象之之间间的的某某个个关关系系：我

15、我们们用用平平面面上上的的点点分分别别表表示示这这些些对对象象，若若对对象象甲甲和和乙乙有有关关系系，就就用用一一条条线线连连接接表表示示甲甲和和乙乙的的两两个个点点.这这种种由由一一些些点点与与连连接接其其中中某某些些点点对对的的线线所所构构成的图形就是图论中所研究的图成的图形就是图论中所研究的图.图图/GraphGraph：可可直直观观地地表表示示离离散散对对象象之之间间的的相相互互关关系系，研究它们的共性和特性，以便解决具体问题。研究它们的共性和特性，以便解决具体问题。1.2 图的定义图的定义12/25/202213Li-Li ZhangGraph TheoryGraph Theory/

16、图图图图论论论论无无向向图图（简简称称图图）:一一个个图图是是指指一一个个有有序序三三元元组组(V(G),E(G),V(G),E(G),),),其其中中V(G)V(G)是是一一个个非非空空有有限限集集，(G)G)是是与与(G)G)不不相相交交的的有有限限集集合合,是是关关联联函函数数，它它使使E(G)E(G)中中每每一一元元素素对对应应于于V(G)V(G)中中的的无无序序元元素素对对（可可以以相相同）同）几个重要定义几个重要定义有有A(D)有有实际上实际上,有向图即将无向图中的无序对看成有序对有向图即将无向图中的无序对看成有序对.其中有向图对应的无向图称为有向图的基础图。其中有向图对应的无向图

17、称为有向图的基础图。其中其中V(G)称为顶点集称为顶点集,E(G)称为边集称为边集（A(D)又称为又称为弧集）弧集）.令令p(G)=|V(G)|,q(G)=|E(G)|,分别称为图的分别称为图的阶和边数。举例说明。阶和边数。举例说明。A(D)A(D)有向有向12/25/202214Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论 如果一个图的顶点集和边集都是有限集则称如果一个图的顶点集和边集都是有限集则称该图为该图为有限图有限图,否则称为否则称为无限图无限图.只有一个顶点只有一个顶点所构成的图称为所构成的图称为平凡图平凡图,其它的称为其它的称为非平凡图非

18、平凡图.如果一个图中没有环也没有重边称为如果一个图中没有环也没有重边称为简单图简单图。12/25/202215Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论图图/graph;有向图有向图/directed graph;相邻相邻/adjacent，关联关联/incident；顶点顶点/vertex;孤立的孤立的/isolated，环环/loop。在有向图在有向图G中，若中，若e=（，），），即箭头由，即箭头由到，称相邻到，或到，称相邻到，或a关联或联结关联或联结b。a称为称为e的的起点起点/initial vertex，b称为称为e的的终点终点/term

19、inal or end vertex。12/25/202216Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论1.严格有向图严格有向图：既无自回路又无平行边的有向图。既无自回路又无平行边的有向图。2.非对称有向图非对称有向图：在两点间最多有一条有向边，但允：在两点间最多有一条有向边，但允许有自回路的有向图。许有自回路的有向图。3.对称有向图对称有向图：对于图中每一边：对于图中每一边(a,b),总存在另一边总存在另一边(b,a)的有向图。的有向图。4.完全有向图完全有向图:(1)完全对称有向图：一个从任一点到完全对称有向图：一个从任一点到其他点有一条且仅有

20、一条有向边的简单图；其他点有一条且仅有一条有向边的简单图；(2)完全完全非对称有向图：任何两点有一条且只有一条有向边的非对称有向图：任何两点有一条且只有一条有向边的非对称图非对称图。有向图的种类：有向图的种类：12/25/202217Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论 有向图在成对比较中的应用有向图在成对比较中的应用 在很多实验中，特别在社会科学领域，要求人们通在很多实验中，特别在社会科学领域，要求人们通过对事物的两两比较排出它们的名次。这种方法称为过对事物的两两比较排出它们的名次。这种方法称为成对比较法成对比较法。例如，测定对音乐作品的个

21、人爱好时，。例如，测定对音乐作品的个人爱好时，每一次对一个主题取出两个作品，问一个人他喜欢哪每一次对一个主题取出两个作品，问一个人他喜欢哪一个。记录了一个。记录了n n个作品成对比较所有个作品成对比较所有n(n-1)/2n(n-1)/2种可能种可能的结果后，实验者就能根据某人的爱好排出的结果后，实验者就能根据某人的爱好排出n n个作品个作品的品次。的品次。KendallKendall在在19481948年做的一个分类实验时，对六种不同年做的一个分类实验时，对六种不同的狗食排名次。每天在六种食品中任选两种喂狗。实的狗食排名次。每天在六种食品中任选两种喂狗。实验安排了验安排了1515天，所有可能配

22、对的食物都被试过，在图天，所有可能配对的食物都被试过，在图中，一条边是从喜欢的食物引向比较不喜欢的食物，中，一条边是从喜欢的食物引向比较不喜欢的食物，这样的图称为这样的图称为优化图优化图。12/25/202218Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论 有向图在竞赛中的应用有向图在竞赛中的应用在在单循环赛中，每个运动员和所有其他运动员单循环赛中，每个运动员和所有其他运动员比赛，比赛结果可以用有向图表示。图中一条比赛，比赛结果可以用有向图表示。图中一条顶点顶点a a指向指向b b的边表示运动员的边表示运动员a a胜过运动员胜过运动员b b。所所以完

23、全非对称图又称为竞赛图。以完全非对称图又称为竞赛图。按得分排名次：按得分排名次：根据运动员得分排名次，得分根据运动员得分排名次，得分是运动员在比赛中胜的局数，反映在有向图中是运动员在比赛中胜的局数，反映在有向图中是点的出度。是点的出度。12/25/202219Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论1.3 顶点的度顶点的度顶点的度顶点的度：在无向图在无向图G G中中,与与a a相邻的顶点的数目称为相邻的顶点的数目称为v v的度的度/degree,/degree,记为记为d(v)d(v)。分别用分别用 表示表示G G中的中的最小度和最大度最小度和最

24、大度。度为零的顶点称为。度为零的顶点称为孤立顶点孤立顶点。在有向图在有向图G G中中,以以v v为终点的边的条数称为为终点的边的条数称为v v的入度的入度/in-/in-degree,degree,记为记为d d(v)(v)。以。以v v为起点的边的条数称为为起点的边的条数称为v v的出的出度度/out-degree,/out-degree,记为记为d d+(v)(v)。有向图中，有向图中，V V的度数的度数=d=d(v)+d(v)+d+(v),(v),12/25/202220Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论定理定理1.3.1(Hands

25、haking)设无向图设无向图G=（V，E）有）有e条条边，则边，则G中所有顶点的度之和等于中所有顶点的度之和等于e的两倍。的两倍。证明思路：考虑每条边在求和中的贡献。证明思路：考虑每条边在求和中的贡献。定理定理1.3.2 无向图中度为奇数的顶点个数恰有偶数个。无向图中度为奇数的顶点个数恰有偶数个。证明思路：将图中顶点的次分类，再利用定理证明思路：将图中顶点的次分类，再利用定理1。定理定理1.3.3 设有向图设有向图G=（V，A）有）有e条边，则条边，则G中所有中所有顶点的入度之和等于所有顶点的出度之和，也等于顶点的入度之和等于所有顶点的出度之和，也等于e。证明思路：考虑每条边在求和中的情况。

26、证明思路：考虑每条边在求和中的情况。即即d(v)=2e即即d(v)=d d+(v)=e记住了吗记住了吗？几个重要定理几个重要定理12/25/202221Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论推论推论12/25/202222Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论例例1 1 证证明明任任何何一一群群人人中中，有有偶偶数数个个人人认认识识其其中中奇数个人奇数个人.(.(匈牙利数学竞赛试题匈牙利数学竞赛试题)证证 用用n n个个顶顶点点表表示示n n个个人人.如如果果两两个个人人相相识识，就就用用一一条

27、条线线把把他他们们对对应应的的一一对对顶顶点点连连起起来来，这这样样就就得得到到了了一一个个图图G G.每每一一个个人人所所认认识识的的人人的的数数目目就就是是他他对对应应的的顶顶点点的的次次，于于是是问问题题就就转转化化为为证证明明图图G G中中奇奇点点的的个个数数为为偶偶数数，而而这这正正是是定定理理1.3.21.3.2的结论的结论.12/25/202223Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论例例2 设设是是平平面面上上n个个点点，其其中中任任意意两两点点的的距距离离至至少少是是1，证证明明至至多多有有3n对对点点，每每对对点点的的距距离

28、离恰恰好好是是1.证证 以以这这n个个点点为为顶顶点点作作图图G，使使得得 与与 相相邻邻当当且且仅仅当当 与与 的的距距离离恰恰好好是是 .于于是是，距距离离恰恰为为1的的点点对对的的数数目目就就是是G的的边边数数q.显显然然，在在G中中的的邻邻点点一一定定在在以以 为为圆圆心心，以以1为为半半径径的的圆圆周周上上.由由于于任任一一对对点点的的距距离离至至少少是是1,于于是是，所以所以 即即 .结论成立结论成立例例212/25/202224Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论例例3在在一次围棋擂台赛中，双方各出一次围棋擂台赛中，双方各出n名

29、选手。比名选手。比赛的规则是双方先各自排定一个次序，设甲方赛的规则是双方先各自排定一个次序，设甲方排定的次序为排定的次序为 乙方排定的次序为乙方排定的次序为12/25/202225Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论1.4 子图与图的运算子图与图的运算子子图图：(,E),E)是是图图,若若=(=(,)也也是是图图且且满满足足:(1):(1)；(2)(2)；则则称称为为的子图的子图/subgraphsubgraph。生成子图生成子图：当当时时,称称为的生成子图。为的生成子图。真真子子图图:当当或或时时,称称为为的的真真子子图。图。导导出出子子图

30、图:设设,由由内内的的所所有有顶顶点点及及其其顶顶点点之之间间的的所所有有边边得得到到的的子子图图称称为为G G的的导导出出子子图图（由由顶顶点点确定）；确定）；边边导导出出子子图图：设设,由由边边集集E E的的所所有有边边及及其其边边的顶点集得到的子图称为的顶点集得到的子图称为G G的边导出子图的边导出子图(由边确定）由边确定）.举例说明其区别举例说明其区别。12/25/202226Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论相相对对补补图图/complementary complementary graphgraph ：（，）是是图图，（，）是是

31、的的子子图图，”，”V VV V或或是是”中中边边所所关关联联的的所所有有顶顶点点集集合合，则则”（”，”）称称为为关于的关于的相对补图相对补图。补补图图：关关于于完完全全图图的的子子图图的的补补图图称称为为此此子子图图的的绝绝对补图，若子图记为，则补图记为对补图，若子图记为，则补图记为 。12/25/202227Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论图的运算图的运算图图的的并并/union/union：（，）和和（，）是是两两个个简简单单无无向向图图，它它们们的的并并图图 定定义义为为 =（，）.图图的的和和：（，）和和（，）是是两两个个不不

32、相相交交的的简简单单无无向向图图，称称+为为G G和和G G的的和和，其中其中+=（，).).图图的的交交：（，）和和（，）是是两个简单无向图，称两个简单无向图，称 为为G G和和G G的交的交，其中，其中 =（，).).举例说明。举例说明。12/25/202228Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论1.5 特殊图类特殊图类完全图完全图/complete graph：图：图G中的每对不同顶点中的每对不同顶点之间恰有一条边。之间恰有一条边。空图空图/empty graph：边集为空边集为空的图。的图。问题：完全图的补图是怎样的图？问题：完全图的

33、补图是怎样的图？设设G=(V,E)是是p阶图阶图,若若V可以划分为可以划分为m个非空个非空12/25/202229Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论补充特殊图类补充特殊图类练习：画出一个完全练习：画出一个完全二部图二部图/bipartite graph。轮图轮图/wheel:由一个圈添加一个新顶点由一个圈添加一个新顶点,并且把这并且把这个顶点与圈的所有顶点相连得到的图称为轮，新个顶点与圈的所有顶点相连得到的图称为轮，新的边称为辐。的边称为辐。正则图正则图：每个顶点的度都等于每个顶点的度都等于k k的图。的图。线图（边图）线图（边图）/lin

34、e graph：图图G G的线图是以为的线图是以为E(G)E(G)顶点集的图顶点集的图,其中两个顶点相邻当且仅当它其中两个顶点相邻当且仅当它们在们在G G中是相邻的边。中是相邻的边。练习练习:各类特殊图所含边数的情况如何？各类特殊图所含边数的情况如何？12/25/202230Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论1.6 图的矩阵表示与同构图的矩阵表示与同构图图G表示的三种方法：表示的三种方法：（1）集合表示）集合表示（2）邻接表（）邻接表（adjacency list）表示表示（3）矩阵（）矩阵（matrix）表示表示 1、邻接矩阵（、邻接矩阵

35、（adjacency matrix）表示表示 2、关联矩阵（、关联矩阵（incidence matrix）表示表示12/25/202231Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论关联矩阵及其举例说明关联矩阵及其举例说明关联矩阵关联矩阵：设：设G=(V,E)的顶点集和边集分别为的顶点集和边集分别为关联矩阵的性质关联矩阵的性质:(1)B(G)的每一列元素之和均为的每一列元素之和均为2；(2)B(G)的每一行元素之和等于对应顶点的度数。的每一行元素之和等于对应顶点的度数。举例说明。举例说明。12/25/202232Li-Li ZhangGraph Th

36、eoryGraph Theory/图图图图论论论论邻接矩阵及同构邻接矩阵及同构12/25/202233Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论邻接矩阵的性质邻接矩阵的性质(1)(1)主对角线所有元素都是主对角线所有元素都是00图中无回路图中无回路;(2)(2)若无环若无环,顶点的度等于顶点的度等于M M中对应行或列中的中对应行或列中的1 1的个数。的个数。(3)M(3)M是对称的是对称的,所以如果两行交换位置，那末所以如果两行交换位置，那末相应的列也应交换位置。相应的列也应交换位置。(4)(4)图图G G是分离图是分离图,且有两个分支且有两个分支

37、G1G1和和G2 G2 它的它的邻接矩阵能划分成分块对角矩阵。邻接矩阵能划分成分块对角矩阵。(5)(5)给出任何一个给出任何一个n n阶对称（阶对称（0 0，1 1）方阵）方阵Q,Q,总能总能构造一个具有构造一个具有n n个顶点的图个顶点的图G G，使得使得Q Q是是G G的邻接的邻接矩阵。矩阵。12/25/202234Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论从定义可以看出，两个同构图必然具备下列性质：从定义可以看出，两个同构图必然具备下列性质：（1 1）具有相同的顶点数；）具有相同的顶点数；（2 2）具有相同的边数；）具有相同的边数；（3 3）

38、对于一个给定的度数具有相同的顶点数。）对于一个给定的度数具有相同的顶点数。反之不成立。反之不成立。举例说明。举例说明。同构图的性质同构图的性质12/25/202235Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论例例1 下面两个图不同构下面两个图不同构.12/25/202236Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论例例2 证明：证明：图图G和图和图H同构同构.12/25/202237Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论同构判定算法（用邻接矩阵）同构判定

39、算法（用邻接矩阵）1 1、根据图确定其邻接矩阵（、根据图确定其邻接矩阵（I)I)2 2、计算行次：矩阵每行的个数，（对应于出次）计算行次：矩阵每行的个数，（对应于出次）和列次：（对应于入次）和列次：（对应于入次）3 3、不考虑出现的次序不同，若行次与列次不同，、不考虑出现的次序不同，若行次与列次不同，则必不同构，否则继续则必不同构，否则继续4 4、同时交换其一矩阵的行和行，列和列。、同时交换其一矩阵的行和行，列和列。若此矩阵能变成与另一矩阵相同若此矩阵能变成与另一矩阵相同，则同构。对所则同构。对所有顶点的排列都试过，仍不相同，则不同构有顶点的排列都试过，仍不相同，则不同构。12/25/2022

40、38Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论性质性质：两个图：两个图G G与与H H是同构的充要条件是是同构的充要条件是存在一个置换矩阵存在一个置换矩阵P,P,使得使得M(G)=PM(G)=P M(H)P.M(H)P.12/25/202239Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论作业作业：每人做一题，其中学号为：每人做一题，其中学号为1-151-15号对应号对应1-1-1515题；题；其它学号的同学按照学号最后一位数字与题目其它学号的同学按照学号最后一位数字与题目最后一位数字对应。最后一位数字对应

41、。注意注意：下次上课全部上交，作业写在纸上，自：下次上课全部上交，作业写在纸上，自己保管好己保管好。12/25/202240Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论2 图的连通性图的连通性/2.1 途径途径、路和圈路和圈途径途径：中相邻边的序列（：中相邻边的序列（0 0,1 1），（），（1 1,2 2），），（k-1k-1,k k）称称为为一一条条途途径径.此此途途径径长长度度为为.也也可可以（以（0 0，1 1，k k）表示道路表示道路,0 0为起点，为起点，k k为为终点，起点与终点相同时称为终点，起点与终点相同时称为闭途径闭途径。迹迹/t

42、race trace：一一条条边边不不重重复复出出现现的的途途径径称称为为迹迹,当当0 0=k k时称为闭迹。时称为闭迹。路路/PathPath :一一条条内内部部顶顶点点不不重重复复出出现现的的途途径径称称为为路路；路所含的边数称为路的长度。路所含的边数称为路的长度。回回路路（圈圈）/Cycle/Cycle：一一条条内内部部顶顶点点不不重重复复出出现现的的闭闭路路称为圈。长度为奇数的圈称奇圈，否则称偶圈。称为圈。长度为奇数的圈称奇圈，否则称偶圈。12/25/202241Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论 其他概念其他概念顶点间的距离顶点间

43、的距离：任意两点：任意两点u与与v之间的最短路。之间的最短路。图的直径图的直径:指指G的两个顶点之间的最大距离。的两个顶点之间的最大距离。完全图的直径是？其他特殊图类呢？练习。完全图的直径是？其他特殊图类呢？练习。图的围长图的围长：图中最短圈的长度。：图中最短圈的长度。图的周长图的周长：图中最长圈的长度。：图中最长圈的长度。有向图的相关概念可以类似定义。有向图的相关概念可以类似定义。12/25/202242Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论 相关定理及其证明相关定理及其证明12/25/202243Li-Li ZhangGraph Theor

44、yGraph Theory/图图图图论论论论有向图中路的应用有向图中路的应用例例有有A,B,CA,B,C三三个个瓶瓶，分分别别能能装装油油8L,5L8L,5L和和3L.3L.如如果果A A装装满满油，油，B B和和C C是空的，怎样以最快的速度平分是空的，怎样以最快的速度平分A A中的油？中的油？解解法法 我我们们用用三三位位数数码码表表示示A,B,CA,B,C三三个个瓶瓶子子装装油油的的情情况况，又又因因为为三三位位数数码码之之和和不不变变，所所以以可可以以用用后后两两位位数数码码表表示示三三个个瓶瓶子子装装油油的的情情况况.例例如如：（0 0，0 0）表表示示初初始始状状态态.根根据据题题

45、意意：共共有有十十六六种种可可能能的的状状态态，用用这这1616个个状状态态为为顶顶点点作作图图G G，使使得得两两个个状状态态相相邻邻当当且且仅仅当当它它们们可可以以经经过过一一次次倒倒油油相相互互转转化化.于于是是，问问题题就就是是要要求从（求从（0 0，0 0）到（）到（4 4，0 0）的一条最短路）的一条最短路.12/25/202244Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论容易作出容易作出图图G（如下图）：如下图）：12/25/202245Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论通过观察图

46、得知共有两条从（通过观察图得知共有两条从（0 0，0 0）到）到(4,0)(4,0)的路：的路：第一条第一条:(0,0):(0,0)(5,0)(5,0)(2,3)(2,3)(2,0)(2,0)(0,2)(0,2)(5,2)(5,2)(4,3)(4,3)(4,0);(4,0);第二条第二条:(0,0):(0,0)(0,3)(0,3)(3,0)(3,0)(3,3)(3,3)(5,1)(5,1)(0,1)(0,1)(1,0)(1,0)(1,3)(1,3)(4,0);(4,0);从而，最快的速度平分即是最短的路所对应的从而，最快的速度平分即是最短的路所对应的过程，过程，即第一条路的过程就是以最快的速度

47、平分油的即第一条路的过程就是以最快的速度平分油的过程过程。能说出具体能说出具体操作吗？操作吗？12/25/202246Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论连通连通/connectivity:connectivity:设设(,),),若存在一若存在一条从条从0 0，到，到k k的一条道路，则称的一条道路，则称0 0到到k k连通。连通。无向图的连通性无向图的连通性:若图中任两个不同顶点都若图中任两个不同顶点都连通，则称此无向图是连通的连通，则称此无向图是连通的/connected,connected,否则否则称为非连通图称为非连通图(分离图分离

48、图)。连通分支连通分支/connected componentsconnected components：图可分为图可分为几个不相连通的子图，每一子图本身都是连通几个不相连通的子图，每一子图本身都是连通的。称这几个子图为的连通分支。的。称这几个子图为的连通分支。2.2 2.2 连通图、非连通图和成分连通图、非连通图和成分 12/25/202247Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论说说明明：对对无无向向图图而而言言，若若0 0到到k k可可达达，则则k k到到0 0也可达。对有向图而言则未必。也可达。对有向图而言则未必。有向图的连通性：有向图

49、的连通性：(1)(1)弱弱连连通通：（，）对对应应的的无无向向图图是是连连通图，则称为弱连通通图，则称为弱连通/weakly connectedweakly connected。(2(2）强强连连通通：若若（，）中中任任两两点点间间都都有有路路，即即对对与与，到到可可达达，到到可可达达，称为强连通称为强连通/strongly connectedstrongly connected。(3)(3)单单向向连连通通：如如果果有有向向图图D D的的任任何何两两个个顶顶点点至至少少由由一一个个顶顶点点到到另另一一个个顶顶点点可可达达,则则称称D D是是单单向向连通的。连通的。有向图的连通性有向图的连通性

50、 12/25/202248Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论例例：用用图图描描述述一一台台自自动动售售货货机机，只只用用分分，分分二二种种硬硬币，满分后压按钮，选择一块巧克力，钱多了不找还。币，满分后压按钮，选择一块巧克力，钱多了不找还。12/25/202249Li-Li ZhangGraph TheoryGraph Theory/图图图图论论论论 顶点顶点:：分边：分边：投分：投分 ：分：分 ：投分：投分 ：分：分 ：压按扭动作：压按扭动作 ：分分 表示已投入钱的状态表示已投入钱的状态 表示一种动作表示一种动作自动售货机：有向加权图描绘得