离散课件图论

1、离 散 数 学图 论主讲教师：李欢 2图 论主要内容1.图论的基本概念2. 通路问题 3. 图的矩阵表示4.欧拉图和哈密顿图5. 二分图与图匹配 6. 树、有向树和有序树第九章 图的基本概念3图 论4图 论图论已有二百多年历史 (以Euler研究歌尼斯堡七桥问题为发端)。近四十年来发展十分迅速，成为一个新兴的数学分支。1、计算机科学中许多概念、算法需要图论支持(如二叉树)。2、为计算机应用建模提供数学工具3. 2012年ACM两个最佳博士论文提名均涉及图理论Honorable Mentionwinner Aleksander Madry, nominated by the Massachuse

2、tts Institute of Technology for his dissertation From Graphs to Matrices, and Back: New Techniques for Graph Algorithms.Honorable Mentionwinner David Steurer, nominated by Princeton University for his dissertation On the Complexity of Unique Games and Graph Expansion.总而言之，“ 图论之为用 大矣哉！”The 7 Bridges

3、of KonigsburgKonigsburg (now called Kalingrad) is a city on the Baltic Sea wedged between Poland and Lithuania.A river runs through the city which contains a small island.There are 7 bridges which connect the various land masses of the city.The ProblemThe people of Konigsburg made a sport during the

4、 18th century of trying to cross each and every one of the 7 bridges exactly once.This was to be done in such a way that one would always end up where one began.Graph Theory - HistoryLeonhard Eulers paper on “Seven Bridges of Knigsberg” , published in 1736. Euler (pronounced “oiler”)Euler was one of

5、 the greatest mathematicians of all time.He contributed to virtually every field of mathematics that existed in his time.The publication of his collected works (Opera Omnia) is presently up to volume 73 and still not complete.Euler and Graph TheoryEulers solution to the Konigsburg bridge problem was

6、 more than a trivial matter.He didnt just solve the problem as stated; he made a major contribution to graph theory. Indeed, he essentially invented the subject.His contribution has many practical applications.Famous problems“The traveling salesman problem” A traveling salesman is to visit a number

7、of cities; how to plan the trip so every city is visited once and just once and the whole trip is as short as possible ? Famous problemsIn 1852 Francis Guthrie posed the “four color problem” which asks if it is possible to color, using only four colors, any map of countries in such a way as to preve

8、nt two bordering countries from having the same color. This problem, which was only solved a century later in 1976 by Kenneth Appel and Wolfgang Haken, can be considered the birth of graph theory. ExamplesFlow of material liquid flowing through pipescurrent through electrical networksinformation thr

9、ough communication networksparts through an assembly lineIn Operating systems to model resource handling (deadlock problems)In compilers for parsing and optimizing the code.ExamplesCost of wiring electronic componentsShortest route between two cities.Shortest distance between all pairs of cities in

10、a road atlas.Matching / Resource AllocationTask schedulingVisibility / Coverage14图 论7.1 图论的基本概念15图 论图论的基本概念目的：了解图论的基本概念；重点：图论的基本概念；难点：度、图同构。What is a Graph?Informally a graph is a set of nodes joined by a set of lines or arrows.11234455662317图 论无向图、有向图A graph G consists of a finite set V of objects

11、called vertices, a finite set E of objects called edges, and a function that assigns to each edge a subset v1，v2, where v1and v2 are vertices (and may be the same).设 V 和 E 是有限集合，且 V 如果 ：E v1，v2v1 且v2 V， 则称 G = ，为 无向图。如果 ：E VV，则称 G ，为 有向图。注意： E 可为空 零图 一个 E 中元素可对应二个相同的 V 中元素 自圈(自环） 多个 E 中的元素可对应 V 中相同的

12、二元素 平行边 18图 论无向图和有向图 统称为图，其中 V的元素称为图 G 的结点 (顶点)，E 的元素称为图 G 的边，图 G 的结点数目称为它的 阶。Example: Let V=1,2,3, E=e1,e2,e3,e4,e5. Let be defined by (e1)= (e5)=1,2, (e2)=4,3, (e3)=1,3, (e4)=2,4Then, G=(V,E, ) is a graph. V:=1,2,3,4,5,6 E:=1,2,1,5,2,3,2,5,3,4,4,5,4,6 20图 论图的最本质内容：结点和边的对应关系。用几何图形表示图： 小圆圈表示结点无向图：若

13、(e) = v1，v2，就用一条连接结点v1和v2的 无向线段 表示边 e 有向图：若 (e) v1，v2，就用一条由v1指向v2的 有向线段 表示边ev1v2v321图 论关联、邻接 结点和边的关系设无向图 G =，e，e1，e2E且v1，v2V如果(e) =v1，v2，则称 e 与 v1 (或v2) 互相关联，e 连接 v1和 v2，v1和 v2 既是 e 的起点，也是 e 的终点， 也称 v1 和 v2 邻接。如果两条不同边 e1 和 e2 与同一个结点关联， 则称 e1 和 e2 邻接。22图 论关联、邻接 结点和边的关系设有向图 G =，e E 且 v1，v2 V。 若(e) =v1

14、，v2，则称 e 连接 v1和v2 ，e 与 v1 (或v2)互相关联，分别称 v1和 v2 是 e 的起点和终点，也称 v1 和 v2 邻接。 23图 论自圈、平行边、简单图设图 G =，e1 和 e2 是 G 的两条不同边。如果与 e1关联的两个结点相同，则称 e1为自圈 (self loop)；ii) 如果 (e1) = (e2)，则称 e1 与 e2 平行；如果图 G 没有自圈，也没有平行边，则称 G为简单图(simple graph)我们一般只讨论有限图。v1v2v324图 论 度设 v 是图 G 的结点。如果 G 是无向图，G中与 v 关联的边和与 v 关联的自圈的数目之和称为 v

15、 的度，记为 dG(v) 。如果 G 是有向图，G中以 v 为起点的边的数目称为 v 的出度，记为 d(v)； G中以 v 为终点的边的数目称为v的入度, 记为 d(v)； v 的出度与入度之和称为 v 的度，记为 dG(v)。注意： 在计算无向图中结点的度时，自圈要考虑两遍，因为自圈也是边。（例） 每增加一条边，都使图中所有结点的度数之和增加 2。25图 论定理7.1.1、定理7.1.2定理7.1.1 设无向图 G =， ，有 m 条边，则 vV dG (v) = 2m 证: 因为每条边为图中提供次数均为2定理7.1.2 设有向图 G ， ，有 m 条边， 则 vV dG(v) = vV d

16、G(v) = m，且 vV dG (v) = 2m 。 26图 论奇结点、偶结点度为奇数的结点称为奇结点；度为偶数的结点称为偶结点。 27图 论任何无向图中都有偶数个奇结点。（An undirected graph has an even number of vertices of odd degrees.)Proof: Let V1 and V2 be the set of vertices of even degree and the set of vertices of odd degree, respectively, in an undirected graph G = (V, E)

17、 with m edges. Then 2m = vV deg (v) = vV1 deg (v) + vV2 deg (v) 定理7.1.328图 论孤立点、端点度为 0 的结点 称为 孤立点；度为 1 的结点 称为 端点。 29图 论定义以下特殊图：结点都是孤立点的图称为零图(For each integer n=1, we let Dn denote the graph with n vertices and no edges. We call Dn the discrete graph on n vertices.)。 D2：一阶零图称为平凡图。所有结点的度均为自然数 d 的无向图称为

18、 d 度正则图(Regular)。设 n I+ ，如果 n 阶简单无向图 G 是 n-1 度正则图，则称 G 为 完全无向图 （Complete Graph)，记为 Kn 。 Kn的边数m = n(n-1)/2 。(A complete graph on n vertices, denoted by Kn, is a simple graph that contains exactly one edge between each pair of distinct vertices.)设 n I+ ，每个结点的出度和入度均为 n-1 的 n 阶简单有向图称为 完全有向图。零图、平凡图、d度正则图

19、、完全图 30图 论注意： 1. 完全图必是正则图，但正则图不一定是完全图。2. Dn零图也是正则图31图 论图的最本质内容：结点和边的关联关系。32图 论定义： 设无向图G =V，E和G= V，E ，如果存在双射函数 : v v, 并且当且仅当 e =（ ui ，uj ）E, 有e=(ui )，(uj ) E ，则称 G 和 G同构，记做 G 。(有向图的同构定义类似，只是边改为弧即可。）同 构 单射：指将不同的变量映射到不同的值的函数。满射：指陪域等于值域的函数。即：对陪域中任意元素，都存在至少一个定义域中的元素与之对应。双射（也称一一对应）：既是单射又是满射的函数。直观地说，一个双射函数形成一个对应，并且每一个输入值都有正好一个输出值以及每一个输出值都有正好一个输入值33图 论Ingrap