图论基础(信息学奥赛).pptVIP

图论及其算法 吴闻 第一章 基本概念 1.1 引言 1.2 图的定义 1.3 道路和回路 1.4 树 1.1 引言 图论是一个应用十分广泛而又极其有趣的数学分支。物理、化学、生物、科学管理、计算机等各个领域都可找到图论的足迹。 介绍几个图论有关的简单例子 1.1 引言 例1 下图是一个公路网，V1 ,V2,...,V10是一些城镇，每条线旁边的数字代表这一段公路的长度。现在问，要从V1把货物运到V10，走哪条路最近? 1.1 引言 例1实际上，就是图论中的求最短路径问题。在现实中有很多此类问题，所以图论中求最短路径算法是一个非常经典和重要的算法。 1.1 引言 例2 下图是一个公路网，V1 ,V2,...,V10看成公路网的一个站点，若这个公路网目前被敌方占领。请分析一下，最少需要破坏其公路网的几个站点，就可摧毁敌方整个运输线 1.1 引言 例2属于图的连通性问题。找出图中的割顶集，就是问题的解。军事指挥中很多此类问题。 1.1 引言 例3 飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员。由于种种原因，例如相互配合的间题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员，才能使出航的飞机最多。 1.1 引言 例3 用V1 ,V2,...,V10代表这10个驾驶员。如果两个人可以同机飞行，就在代表他们两个之间连一条线;两个人不能同机飞行，就不连。例如V1和V2可以同机飞行，而V1和V 3就不行。 1.1 引言 例3此类问题属于图的最大匹配问题 将实际生活中的事物分析转化为图论问题的实例还很多... 1.2 图的定义 图：由若干个不同顶点与连接其中某些顶点的边所组成的图形。 图的表示：通常用一个大写字母G来表示图，用V来表示所有顶点的集合，E表示所有边的集合，并且记成G=(V,E)。 1.2 图的定义 子图：如果对图G=(V,E)与G=(V,E),G的顶点集是G的顶点集的一个子集(V?V),G的边集是G的边集的一个子集(E?E)，我们说G是G的子图 1.2 图的定义 环：如果一条边，它的起点和终点相同，这样的边称为环。 平行边：若连接两个顶点的边有多条，则这些边称之为平行边。 孤立点：不与任何边关联的顶点称为孤立点。 1.2 图的定义 简单图：如果一个图没有环，并且每两个顶点之间最多只有一条边，这样的图称之为简单图。在简单图中，连接Vi与Vj的边可以记成(Vi,Vj) 完全图：如果G是一个简单图，并且每两个顶点之间都有一条边，我们就称G为完全图。通常将具有n个顶点的完全图记为Kn。 二分图：如果G是一个简单图，它的顶点集合V是由两个没有公共元素的子集X= {X1,X2,...,Xn}与Y= {Yl ,Y2, ...,Ym}组成的，并且Xi与Xj (1i , jn ) ,Ys与Yt(1s,tm)之间没有边连接，则G叫做二分图。 1.2 图的定义 简单图、完全图、二分图 1.2 图的定义 完全二分图：如果在二分图G中，IXI=N, IYI=M，每一个Xi∈X与每一个Yj∈Y有一条边相连，则G叫做完全二分图 1.2 图的定义 如果G是一个N个顶点的简单图，从完全图Kn中把属于G的边全部去掉后，得到的图称为G的补图，通常记为G。 一个图的补图的补图就是自身。 1.2 图的定义 相邻：如果图G的两个顶点Vi与Vj之间有边相连，我们就说Vi与Vj是相邻的，否则就说Vi与Vj是不相邻的。如果顶点V是边e的一个端点，就说顶点V与边e是相邻的，e是从V引出的边。 度数：从一个顶点V引出的边的条数，称为V的度数，记作d(V)。 1.2 图的定义 下图中，d(V1)=d(V2)=d(V3)=d(V4)=d(V5)=5-1=4,d(Y3)=2等等。 1.2 图的定义 K度正则图：把每个顶点的度数为常数K的图叫做K度正则图。 经常使用下面两个符号: 1.2 图的定义 从顶点度数问题的讨论中，引出一些有趣的结论: 1. 2.对于任意的图G，奇次顶点的个数一定是偶数。 1.2 图的定义 例1、空间是否有这样的多面体存在，它们有奇数个面，而每个面又有奇数条边? 分析:根据题意，可以构造一个图，以面为顶点，当且仅当两个面有公共棱时，则在G的相应两顶点间连一条边，得到图G。依题意，图的顶点个数是奇数，而且每个顶点的度数d(V)是奇数，从而 也是奇数，与结论1相违，故这种多面体不存在。 1.2 图的定义 例2、晚会上大家握手联欢，问是否会出现握过奇次手的人是奇数的情况? 分析:一个图，以人为顶点，两人握手时，则相应的两个顶点之间连一条边，于是每人握手的次数即相应顶点的度数。由结论2，奇次顶点的个数总是偶数，所以握过奇次手的人数是奇数的情况不可能出现。 1.3 道路与回路 道路：在图G中，一个由不同的边