图论基础(信息学奥赛)

《图论基础(信息学奥赛)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论及其算法吴闻第一章基本概念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

2、看成公路网的一个站点，若这个公路网目前被敌方占领。请分析一下，最少需要破坏其公路网的几个站点，就可摧毁敌方整个运输线1.1引言例2属于图的连通性问题。找出图中的割顶集，就是问题的解。军事指挥中很多此类问题。1.1引言例3飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员。由于种种原因，例如相互配合的间题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员，才能使出航的飞机最多。1.1引言例3用V1,V2,...,V10代表这10个驾驶员。如果两个人可以同机飞行，就在代表他们两个之间连一条线;两个人不能同机飞行，就不连。例如V1

3、和V2可以同机飞行，而V1和V3就不行。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图的定义环：如果一条边，它的起点和终点相同，这样的边称为环。平行

4、边：若连接两个顶点的边有多条，则这些边称之为平行边。孤立点：不与任何边关联的顶点称为孤立点。1.2图的定义简单图：如果一个图没有环，并且每两个顶点之间最多只有一条边，这样的图称之为简单图。在简单图中，连接Vi与Vj的边可以记成(Vi,Vj)完全图：如果G是一个简单图，并且每两个顶点之间都有一条边，我们就称G为完全图。通常将具有n个顶点的完全图记为Kn。二分图：如果G是一个简单图，它的顶点集合V是由两个没有公共元素的子集X={X1,X2,...,Xn}与Y={Yl,Y2,...,Ym}组成的，并且Xi与Xj(1

5、有边连接，则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引出的边的条数，称

6、为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。依题意，图的顶点个数是奇数，

7、而且每个顶点的度数d(V)是奇数，从而也是奇数，与结论1相违，故这种多面体不存在。1.2图的定义例2、晚会上大家握手联欢，问是否会出现握过奇次手的人是奇数的情况?分析:一个图，以人为顶点，两人握手时，则相应的两个顶点之间连一条边，于是每人握手的次数即相应顶点的度数。由结论2，奇次顶点的个数总是偶数，所以握过奇次手的人数是奇数的情况不可能出现。1.3道路与回路道路：在图G中，一个由不同的边组成的序列e1,e2...,eg，如果ei是连接Vi-1与Vi(i=1,2,..,g)的，我们就称这个序列为从V0到Vg的一条道路，数g称为路长，V0与Vg称为这条道路的两个

8、端点，Vi(1<=i<=g-1)叫做道路的内点。如果