2022年图论教案final

《2022年图论教案final》由会员分享，可在线阅读，更多相关《2022年图论教案final（22页珍藏版）》请在装配图网上搜索。

1、学习必备欢迎下载1 图论的著名问题与历史图论是数学中一个既古老又年轻的数学分支欧拉 1736 年关于哥尼斯堡七桥问题论文的发表标志着图论的诞生自二十世纪五十年代开始，由于运筹学、计算机科学的促进，以及应用领域的扩大，图论已成为一个独立的数学分支特别在近三十年，图论正经历着一个蓬勃发展的时期，表现出年轻学科所具有的强大生命力一.图论中的几个著名问题例 1.哥尼斯堡七桥问题哥尼斯堡历史上曾是德国东普鲁士的省会，第二次世界大战后归苏联所有，也就是现在的加里宁格勒市.普列格尔（Pregel）河穿城而过，河中有两个小岛，岛与河岸及岛与岛之间有七座桥.当时流行很广的一个难题是：能否从河岸或两个小岛中的任一

2、处出发，经过每一座桥一次且仅一次再回到出发地呢？这个问题被瑞士数学家欧拉解决了.如下图所示，A、B、C、D表示陆地.1736 年，欧拉（1707-1783）在俄国彼得堡科学院院报上发表了一篇论文.他在论文中引进了图的概念和方法，用抽象分析法将这个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个图，将七桥问题转化为一笔画问题.欧拉证明了这个问题没有解这是由于此图与每个顶点相关联的边数均为奇数，并且推广了这个问题.给出了对于一个给定的图可以某种方式一笔画的判定法则.这项工作使欧拉成为图论及拓扑学的创始人.引深：图 G是欧拉图的充要

3、条件是什么？例 2哈密尔顿多面体问题1856 年英国数学家哈密尔顿（1790-1868）提出了这样一个问题：用一个规则的实心十二面体，它的二十个顶点标出世界著名的二十个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即绕行世界.用图论的语言来说，游抽象成精选学习资料 -名师归纳总结-第 1 页，共 22 页学习必备欢迎下载戏的目的是在十二面体的图中找出一个包含所有顶点的圈.这个问题后来就叫做哈密顿问题.由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的注意和研究.引深：什么图是哈密尔顿图呢？其判定条件如何？例 3.四色问题在一个平面或球面上的任何地图能

4、够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色.每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点.四色猜想有一段有趣的历史.每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接.所以四色猜想是图论中的一个问题.它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用.问题转化为：给平面图G的顶点着色，使任一对相邻顶点具有不同的颜色，那么至少要多少种颜色？1852 年，英国的弗兰西斯提出了四色问题；1878 年凯莱在伦敦数学会宣布了此问题，引起了数学界的广泛重视.肯佩和泰特分别与1879 年和 18

5、80 年发表文章，声明证明了四色问题；11 年后，希伍德于1890 年指出了肯佩证明中的错误，却利用肯佩的方法证明了五色定理；1891 年彼得森又指出了泰特证明中的错误，却利用泰特的方法证明了四色猜想的一个等价命题.世界上许多数学家为四色猜想倾注了大量心血.经过一百多年后，这个貌似简单的四色猜想被美国的阿佩尔和哈肯于1976年借助于电子计算机给出了证明.他们的证明用计算机大约需要1200 小时，要作出100 亿个独立的逻辑判断！他们的工作无疑具有开创性，是值得称赞的.给出四色定理一个无需借助于计算机的证明乃是一个未能解决的问题.二、图论发展简史1736 年，欧拉关于哥尼斯堡七桥问题的论文的发表

6、，人们普遍认为图论由此诞生.1847年，德国数学家、物理家克希荷夫应用图论方法来分析电网络，奠定了现代网络理论的基础.1852年，佛兰西斯提出了四色猜想，引起了数学界的广泛注意，使许多数学家对图论产生了浓厚的兴趣，极大地推动着图的着色理论的发展.1856 年，爱尔兰数学家哈密尔顿提出了正十二面体游戏问题，引出了哈密尔顿的理论.精选学习资料 -名师归纳总结-第 2 页，共 22 页学习必备欢迎下载1857 年，英国数学家凯莱在研究饱和碳氢化合物的同分异性体时，发现了“树”的概念和理论，并由此预见了未知化合物的存在.1936 年，匈牙利数学家哥尼科，总结前人的成果，发表了第一部图论专著有限图和无限

7、图的理论.自二十世纪五十年代开始，由于运筹学、计算机的促进以及应用领域的扩大，图论已成为了一个独立的数学分支.特别在近二十年，图论正经历着一个蓬勃发展的时期，表现出年轻学科所具有的强大生命力.许多大学的系，如数学系、计算机科学系、运筹系、组合优化系、电机系等都开设了图论这门课.图论是一门应用广泛的数学分支，它不但在自然科学的许多领域有重要的应用，还应用于社会科学的诸多方面.许多实际问题（离散）所建立的数学模型就是一个图论模型.图论不但与大学生数学建摸竞赛联系甚紧，而且在中小学数学竞赛中经常出现来源于图论的题目.2 图 的 基 本 概 念一.无向图、有向图、子图1.（无向）图无向图G是指三元组f

8、EV,，其中V是一个非空集合，称为顶点集；E是任意集合，称为边集；f是E到Vvvvvjiji,的映射，记作fEVG,或EVG,在 E 中重复k次的边称为k重边；两端点重合的边称为环2.有向图有向图D是指三元组fEV,，其中V是非空顶点集，E是边的集合，f是E到VvvvvVVjiji,的 映 射,记 作fEVD,或EVD,有向图与无向图的差别仅在于VV中元素是V中元素的有序对还是无序对然而，无序对yx,可以视为两个有序对yx,和xy,也就是说，对于无向图G，将G中每条边e用两条与e有相同端点的对称边a和a来替代后得到一个有向图D，这样得到的有向图D称为G的对称有向图于是无向图可以视为特殊的有向图

9、.例如，城市交通中，双行道可以视为对开的两个单行道以下我们只对无向图来叙述精选学习资料 -名师归纳总结-第 3 页，共 22 页学习必备欢迎下载图可以画出它的直观图形，称为此图的图形表示3.简单图无重边也无环的无向图称为简单图 4.子图如果EEVV11,，那么图11,EVH称为图EVG,的子图，记作GH如果H是G的子图，且GEHEGVHV,，则称H是G的生成子图或支撑子图若,VvuEvuEVV，则子图,EV称为由V导出子图，记为VG设VV，记VV的导出子图VVG为VG设EE，V是E中的边的所有端点所成的集，则G的子图,EV称为由E导出的子图，记为EG，又记EGEEG两个图可以引入交、并、联的运

10、算二.顶点的度1.设EVG,是图，GVv，G中与v关联的边数（重边按重数计）称为顶点v的度，记作vdv为奇（偶）顶点dfvd为奇（偶）数2.对于有向图D，可定义出度vd与入度vd3.结论2e1ev3e4ey8e7ew5ex精选学习资料 -名师归纳总结-第 4 页，共 22 页学习必备欢迎下载握手引理：设EVG,是任意图，则EvdVv2任意一个图的奇顶点的个数是偶数三.正则图、完全图、二部图1.若GVv，有kvd（常数），则称G为k正则图 2.设nGV，则G的任意两顶点均邻接的简单图称为n阶完全图，记为nK3.G是单点图1GVdf；G是空图GEdf4.若图G的顶点集V有一个划分212121,:,

11、VVVVVVV，且iVG是空图2,1i，则称G是（具有二划分21,VV的）二部图，记作EVVG,21，二部图亦称为 偶图 对于简单二部图EVVG,21，若1V的任一顶点与2V的任意顶点都相邻，则称G为完全二部图，记为nmK,，其中21,VnVm3 路 与 连 通 性一.链、迹、路、圈链图G的链GVvGEeveevevWiikk,2110是G中顶点与边交替出现的有序序列.0v称为起点，kv称为终点，W中边的条数k称为W的长度迹图G中任意两边均不相同的链称为迹路图G中任意两顶点均不相同的链称为路，显然，路必是迹，但反之不然在上面的链、迹、路中，当起点与终点重合时，分别称为闭链、闭迹、闭路 闭路亦称

12、为 圈，圈的长度定义为其中边的条数，长度为奇数的圈称为奇圈；长度为偶数的圈称为 偶圈 二部图的刻划：图G为二部图G中不含奇圈二.连通与连通分解考虑图EVG,，设GVvu,，若存在u与v间的路，则称u与v是连通的若图G的任意两顶点都连通，则称G为 连通图 精选学习资料 -名师归纳总结-第 5 页，共 22 页学习必备欢迎下载任意图G均可表成若干个两两顶点不重复，边也不重复的连通子图的并，这些连通子图称为G的连通分支，G的连通分支数 记为Gw考虑有向图EVD,，可定义D的有向路 若有向路D中，DVvu,，存在u到v的有向路或存在v到u的有向路，则称D是单向连通的 若有向图D中，DVvu,，既存在u

13、到v的有向路又存在v到u的有向路，则称D是强连通的 有向图的D顶点集V中元素之间的强连通关系是V上元间的等价关系 由这种关系得到V的等价类iV在D中导出子图iVD称为D的强连通分支 D的强连通分支数记为Dw若1Dw，则称D为强连通图，反之，称D为非强连通图 三.可靠通信网问题在战争状态，我方要构作一个有线通讯网，使得敌方炸毁我方几个通讯站后，其余的通讯仍然可以彼此通话，自然希望不怕被敌方炸毁的通讯站要尽可能多.但限于施工的条件、时间、造价等.要每两个通讯站间均架设直通线路是有困难的，那么满足一定可靠程度的通讯网该如何构作呢？这就涉及到一个连通度、边连通度问题.若图 G 中存在不相邻的顶点，则)

14、(GVV使 GV不连通.V称为图 G 的顶点割.图 G 的连通度定义为：；不连通或为平凡图，若存在不相邻的顶点，若的顶点割是的任何两顶点都相邻；若GGGvvG，VGX0min1)(设 S与S是 V 的非空子集，用SS,表示图 G 中一端属于S，一端属于S的一切边所构成的边集.特别地当VS，S,而非空且SSESVS,.则称E是 G 的边割.对于一个非平凡连通图G，去掉其中任何一个边割后得到的图必不连通.于是可定义图G 的边连通度如下：是非平凡连通图；，若的边割是是平凡图或非连通图；若GGEEGG|min,0)(精选学习资料 -名师归纳总结-第 6 页，共 22 页学习必备欢迎下载四.通知球员问题

15、某足球俱乐部职业队新聘A 为主教练，A 确定了全队队员名单，需通知所有队员到俱乐部报到，A 通知每一名队员所需费用不同，A 知道有的队员可以转告其他队员A 通知每个队员的费用（元）及可以转告队员名单1v2v3v4v5v6v7v8v9v10v11v12v费 用5 6 4 12 10 7 8 5 0.5 10 4 3 可 转 告队 员3v1v4v2v4v5v6v4v4v6v8v12v7v9v9v10v问：A 应通知哪些队员，使费用最少？我们用图的顶点nvvv,21来表示全队n 名队员若iv可以直接转告jv，则连以有向边jivv，A 通知iv所需的费用为ia，记作顶点iv所带的权，这就得到一个顶点赋

16、权有向图D，于是，问题转化为求D的顶点集V的一个子集B，满足：（1）Vvj，有Bvj或者有Bvi，使D中存在iv到jv的有向路；（2）B所含的顶点数最少；（3）B中顶点的权和最少这就是通知球员问题的图论模型设D=),(EV是 有 向 图，VB,若Vj,都 有Bvj或 者 存 在Bi,使D中存在iv到jv的有向路，则称B是D的一个 点基 D中含顶点数最小的点基称为最小点基 又设D是顶点赋权有向图，iiavf是顶点iv的权，B3v1v2v4v5v6v12v7v8v9v10v11v精选学习资料 -名师归纳总结-第 7 页，共 22 页学习必备欢迎下载是D的点基，则vfBfBv称为B的权，于是通知球员

17、问题的解就是相应有向图D的具有最小权的最小点基设1VD是D的一个强连通分支，若D中不存在终点jv在1V中而始点iv不在1V中的有向边jivv，则称1VD是D的一个 最高强连通分支由最高强连通的定义，可以证明：从D中的每一个最高强连通分支中各任取一个顶点，所组成的集合就是D的一个最小点基，并取一个最小权的顶点（求出强连通分支，后代集R，前代集S，SRV1）五.最短路问题考虑 n 个城市的公路网络，试求一个城市到其余各城市的最短路以城市为顶点，公路为边，得到一个图EVG,，每条公路都有长度（公里数），这样GEe，给e赋以一个实数ew称为e的权，于是得到一个赋权图wEVG,，设nvvvvV,210，

18、路的权（或子图的权）为其各边的权和，试求0v到iv的权和最小的路，亦称为最短路 求最短路的算法Dijkstra 算法：(i)令00,0vvvlvl，又令0,00ivS(ii)对 每 个iiSVSv，用vvwvlvlii,m i n代 替vl，计 算vliSvmin，把达到这个最小值的顶点记为1iv，令11iiivSS(iii)若1Vi，则停止；若1Vi，则用1i代替i，转向（ii）例 1：求下图中0v到各顶点的最短路例 2:求天然气管道最优路径7 8 2 6 1 1 2 2 4 3 3 6 9 4 2 4 6 4 4 2 7 5 6 1 0v精选学习资料 -名师归纳总结-第 8 页，共 22

19、页学习必备欢迎下载筹建中的天然气管道网设计如图所示：LCBA、表示压缩机站，流动主向用箭头表示，每个管道旁的数字表示管段长度，现需要求该网络从起点A 到终点 L 的最短通道，并确定沿最优路径相应的压缩机站所处的节点解为：LJGEDA4 树一.树的概念及性质连通的无圈图称为 树，常用T表示无圈图称为 林 若1vd,TVv,则称顶点v为树T的树叶 例如2 ABEJLKHIFDCG3 4 4 3 5 2 1 3 1 5 4 6 5 4 4 2 3 3 3 HCHHHHCCHHHHH甲烷乙烷精选学习资料 -名师归纳总结-第 9 页，共 22 页学习必备欢迎下载生成树（支撑树）若树T是图G的生成子图，则

20、称T是G的 生成树（或支撑树）树的若干充要条件：设EVT,是图，记VvE,，则以下诸命题等价：(i)T是树；(ii)T中任意两顶点间恰有一条路；(iii)T中无圈，且1v(iv)T连通,且1v(v)T连通,但TEe，eT不连通（极小连通图）；(vi)T无圈但TEe，eT必有圈（极大无圈图）二、有向树、二元树设有向图EVD,，DVu0，若DVv均存在有向路vuP,0，则称0u是D的一个 根有向图D的基础图是指去掉各边的方向后所得到的无向图有向树：若有向树T的基础图是树，且T有根0v，则称是T以0v为根的有向树家族树2 顶点的树3 顶点的树4 顶点的树精选学习资料 -名师归纳总结-第 10 页，共

21、 22 页学习必备欢迎下载易知：有向树恰有一个根在有向树中，出度为0 的顶点称为树叶若有向树T的每一顶点间都排有顺序，则称T为有序树 在有序树T中，若TVv，均有kvd，则称T为k元树，当2k时，称T为二元树若在T中除叶外均有kvd，则称T为完全k元树 三、连线问题、最优树1.连线问题考虑连接若干个城镇的铁路网络，如何设计才能使总造价最少？以这些城市为顶点，可修铁路为边，每边都赋以权ijw，ijw为两城镇iv与jv间的铁路造价，得到一个赋权连通图G试在G中，求具有最小权的连通的生成子图，由于要求权最小，这样的子图必不含圈，故此生成子图必是G的生成树，赋权图G的具有最小权的生成树称为最优树2.求

22、赋权图G的最优树的Kruskal算法：（i）选择GEe1，使1ew最小（ii）若已选出边keee,21，则从keeeE,21中选择1ke满足：121,kkeeeeG无圈有向树完全k元树3k精选学习资料 -名师归纳总结-第 11 页，共 22 页学习必备欢迎下载1keW是满足的尽可能小的权（iii）当第（ii）步不能继续执行时停止例如5 E 图、H图及其推广这是由哥尼斯堡七桥问题和Hamilton周游世界问题引出的图论问题一、Euler 图（E图）若图G中有包含一切边的闭迹，则称G为Euler图，而这样的闭迹称为G的Euler闭迹 若G中有包含一切边的迹，则称G为半Euler图，而这样的迹称为E

23、uler迹显然，每一个Euler图都是半Euler图Euler图简称为E图，形象地说，E图就是从任一顶点出发通过每一条边恰好一次又能回到出发点的图，下面的结果给出E图的特征.设G是连通图，则下列三命题相互等价：（i）G是E图；（ii）G的每个顶点都是偶顶点；（iii）G可表成若干个边不交的圈之并，即itiCG1，iC是圈，且当ji时，jiCECE.设G是连通图，则G中存在E迹的充要条件是G中的奇顶点个数为0 或 2二、中国 邮递员问题一个邮递员每天投递邮件都要走遍他所负责投递区域内的每条街道，完成投5x5 8 16 6 9 10 1 2 4 15 3 7 4x6x2x3x0 x1x精选学习资料

24、 -名师归纳总结-第 12 页，共 22 页学习必备欢迎下载递任务后回到邮局他应怎样选择路线，才能使他所走的总路线最短？国际上称这个问题为中国邮递员问题，它是由我国数学家管梅谷教授于1960 年首先提出并进行研究的我们把邮递员所负责投递区域看作一个连通的加权有向图wD,，其中街道的交叉口视为D的顶点，街道（单向）视为边，街道的长度视为边的权经过wD,中每条边至少一次的有向闭链称为邮路，具有最小权的邮路称为最优邮路 解中国邮递员问题就是在连通的加正权有向图wD,中找出一条最优邮路在现实生活中，有许多问题，比如城市里的洒水车、扫雪车、垃圾清洁车和参观展览馆等最佳行走路线问题都可以归结为中国邮递员问

25、题中国邮递员问题的广泛应用，引起了人们极大研究兴趣，提出了许多有效算法.三、Hamilton 图（H图）包含图G的所有顶点的路称为Hamilton路 或H路；包含图G的所有顶点的圈称为Hamilton圈或H圈若一个图G存在Hamilton圈，则称G为Hamilton图或H图H图的研究起源于1856 年Hamilton提出的“周游世界问题”，与Euler图的情况相反，Hamilton图的能方便应用的充要条件目前尚未找到，这是图论中尚未解决的主要问题之一由于它的重要性，吸引了不少图论学者对它进行研究关于Hamilton图的性质有以下结果：1 （H图 的 必 要 条 件）若G图 是H图，则S，且GV

26、S，有SSGw2（H图的充要条件，OreO.定理）若G是3nn个顶点的简单图，且GVvu,，vu,不相邻,有nvdud，则G是Hamilton图3设G是有3nn个顶点的简单图，若GVv有2nvd，则G是Hamilton图4 设G是简单图，vu,是G中不相邻的顶点，且适合GVvdud，则G是H图uvG是H图5设GC为简单图G的闭包，则G是H图的充要条件为GC是H图精选学习资料 -名师归纳总结-第 13 页，共 22 页学习必备欢迎下载6设G是3nn个顶点的简单图，若GC是完全图，则G是H图四、货郎担问题（旅行推销员问题）货郎担问题是与H图有关的著名问题.它的提法是：一个货郎挑着担子从家里出发到各

27、村去卖货，然后回到家里，各村有远有近，应怎样选择他的路线，使他到每个村至少一次而总路程最短，这个问题称为货郎担问题我们以货郎家及各村为图的顶点，各村间的道路为边，道路的长度定义为边的权，得到一个赋权连通图G，于是货郎担问题就转化为在给定的赋权连通图G中找一条最小权的H圈或找一条经过G中每个顶点至少一次的最小权闭链，分别称为最优圈和最优链，一般的连通赋权图未必存在最优圈，然而最优链总是存在的.我们用图的顶点来表示货郎家及各村，各村间的道路用边来表示，道路的长度定义为边的权，边e 的权记作)(ew.于是得到一个赋权图G.于是货郎担问题就是要在给定的赋权连通图G 中找一条最小权的H 圈或找出一条经过

28、G 中每个顶点并且有最小权的闭链，分别称为最优圈和最优链，一般的连通赋权图未必存在最优圈.然而最优链总是存在的.关于一个连通赋权图的最优链算法参见：1、徐俊明图论及其应用，中国科大出版社，1998，第五章，52、杜端甫运筹图论，北京航空航天大学出版社，1990，第十二章美国大学生数学建模竞赛90 年 B 题“扫雪问题”就要用到“中国投递员问题”的理论.中国大学生数学建模竞赛98 年 B 题“灾情巡视路线”，用到“货郎担问题”的理论.6 匹配与独立集一、匹配.匹配问题的研究是由工作分配问题、配偶问题等实际问题引深的.工作分配问题 某单位要从m 位职工中挑选n 位职工来分别承担n 项不同的新工作.

29、用 L=nlll,21表示 n 项新工作的集，用G=mggg,21表示这 m 位职工之集.设 G 中能承担il这一工作的职工的集合为iG(i=1,2,n).试问在什么条件精选学习资料 -名师归纳总结-第 14 页，共 22 页学习必备欢迎下载下，能从 G 中找出 n 位职工来分别承担这n 项不同的新工作.il(即要这 n 位职工分别属于iG)(i=1,2,n).如果找不到n 位职工来分别承担这n 项不同的新工作，那么最多能使 n 项工作的几项分别有人承担？2.匹配的有关概念（1）设 G 是一个图，（），.若 M 中的边都是连杆（即不是环），且任意两边都不相邻.则称 M 为 G 的一个 匹配.（

30、2）设 M 是图 G 的匹配，v V(G).若 v 是 M 中某条边的端点，则称v 是 M 的饱和点.（3）设0M是图 G 的一个匹配，若G 的匹配 M，均有0MM则称0M是 G 的一个 最大匹配（最大）匹配：（4）若图 G 的匹配 M 满足：M=2)(GV，则称 M 是 G 的一个 完美匹配.（并不是每个图都有完美匹配）（5）设 M 是图 G 的一个匹配，P 是 G 一条路，若从P 的起点到终点所经过的边依次交错地属于E(G)M 与 M，则称 P是一条 M 交错路.3.若干结论和定理（1）完美匹配必是最大匹配，而最大匹配未必是完美匹配.（2）M 是 G 的完美匹配M 是 G 的匹配且 G 的

31、每个顶点都是M 的饱和点.（3）任何图都有最大匹配，但却未必有完美匹配.一个图 G 有完美匹配的必要条件是)(GV为偶数.（4）设 M 是图 G 的一个匹配.则 M 是 G 的最大匹配的充要条件为：G 中不存在连接两个不同的M 非饱和点的M 交错路.（5）设 G(X,Y)是二部图（偶图），则 G 存在饱和X 中每个顶点的匹配的充要条件为：XS,有SSN)(.这里 N(S)表示 G 中与 S中的顶点相邻的顶点集合.精选学习资料 -名师归纳总结-第 15 页，共 22 页学习必备欢迎下载（6）若 G 是 k(k0)正则二部图，则G 有完美匹配.二、独立集、覆盖.独立集设 G 一简单图，S V(G)

32、，若 S 中任意两个顶点在G 中都不相邻.即 GS是空图，则称S 是 G 的一个 点独立集 或独立集.图 G 的满足顶点数最多的独立集称为G 的最大独立集.图 G 的最大独立集的基数称为 G 的独立数.记为G）.图 G 的匹配亦称为边独立集，图G 的最大匹配称为G 的最大边独立集.图 G 的最大边独立集的基数（即G 的最大匹配数）称为G 的独立数.记为(G).2.覆盖设 G 是图，KV(G)，若 G 的每一条边中至少有一个端点属于K，则称 K 为 G的一个 覆盖.图 G 的顶点数最少的覆盖称为最小覆盖.图 G 的最小覆盖基数称为G 的覆盖数.记为(G).设 G是图.LE(G).若 G的每个顶点

33、都是L 中某条边的端点，则称L 是 G的一个边覆盖.边数最少的边覆盖称为G的最小边覆盖.G 的最小边覆盖的条数称为G的边覆盖数.记为(G).3.结论或定理设G是图，）（GVS，则S是G的独立集的充要条件为SGV）（是G的覆盖.任 意 一 个 图G的 独 立 数 与 覆 盖 数 之 和 等 于 图G的 阶，即GVGG）（）（.若图G没有孤立点，则GVGG.设,GG是二部图，则GG.匹配、独立集、覆盖理论有许多实际应用,工作分配问题、配偶问题、防止罪犯串供捉拿方案问题、公路配备消防车问题、收款台的设置问题等都是其理论应用的例子.全国大学生数学建模竞赛试题94 年 B题、99 年 B题都涉及到匹配、

34、独立集理论.精选学习资料 -名师归纳总结-第 16 页，共 22 页学习必备欢迎下载7 图的着色一引入如果某两种化学药品接触后会产生有害反应，为了避免意外，它们就不宜存放在一起.假定有 n 种化学药品，问至少把它们分多少处存放，才能保证安全？现将此问题转化为图论问题.用顶点nvvv,.,21表示 n 种药品，若药品iv与jv不宜放在一起，就把顶点iv与jv连一条边，于是得到一个图G，给此图G的顶点进行染色，使得相邻的顶点染上不同的颜色.于是：至少要把这些化学药品分多少处存放至少要用多少种颜色去染图G的顶点，使任意两个相邻的顶点的颜色不同.二顶点着色的有关概念给图G的顶点染上颜色，使得任一对相邻

35、的顶点具有不同颜色称为图G的顶点着色.若图G的某一个顶点着色中所用的颜色数目k，则称此着色为k着色.若图G存在k着色，则称G是k可着色的.使得G是k可着色的k的最小值称为G的点色数，简称为色数，记作G.若图G满足kG，则称G是k色图.求图的色数G是图的着色理论中一个重要问题，也是最难的问题.三几个结论空图的色数是1；非空二部图的色数为2.图G的色数kGG为k部图但不是1k部图.若G表示图G的最大度，则1GG当12nCG为奇圈时，2G，3G，有1GG；当nKG为完全图，1Gn，nG，有1GG.（布鲁克斯定理）若G是简单连通图，并且不是奇圈，也不是完全图，则GG.四四色问题精选学习资料 -名师归纳

36、总结-第 17 页，共 22 页学习必备欢迎下载在 1 提到了四色问题，现把四色问题作如下转化：若把至少属于三个国家的边界上的点看成图的顶点，连接两个顶点的两个国家的公共边界看成边，又当一个国家被另一个国家全部包围时，就在其公共边界的闭曲线上任取一点作为顶点，则地图就成为了一个平图，国家对应于此平图的面.注：所谓平图是指画在平面上且交点均为顶点的图.此平图G是一个无割边的图.这是因为一条边界的两侧总是不同的国家.作此平图G的对偶图（对偶图的概念参见有关图论教材）*G，则*G是一个无环的平图.G的面与*G的顶点相对应，G的两面相邻*G的相应顶点相邻，给G的面（国家）染色给*G的顶点染色.四色猜想

37、即为：对于任意简单平面图G，有4G.五色定理：若G是任意简单平面图，则5G.8 网 络 流1、网络所谓网络是指具有两个不同的特定顶点x和y的赋权连通有向图wD,，记为wDNxy,，其中x和y分别称为发点和收点.若w为非负的函数c，则称网络cDNxy,为容量网络，其中c在边a上的值ac称为边a的容量.若对任何DEa，ac都是非负整数，则称N为整容量网络.2、流约定：设D为一有向图，snaaaDEvvvDV,.,.,2121，令DE到实数集R中的所有映射的集合对于函数（映射）的加法、数量乘法所成的线性空间为sDRDEfDDdim,:,.又令uEDVuD,表示D中所有以u为起点的边集，uED表示D中

38、所有以u为终点的边集.设Df，这样wD,就是一个赋权图，而f为权函数，令uEauEaDDafufafuf,.设cDNxy,为容量网络，若Df使得精选学习资料 -名师归纳总结-第 18 页，共 22 页学习必备欢迎下载（）acafDEa0,有；（）ufufyxDVu有,则称f是N中从x到y的流，简记为yx,流.易知，对于cDNxy,中任何一个yx,流f均有：yfyfxfxf上式中等号两边的值称为yx,流f的流量，记为valf.N中具有最大流量的yx,流称为N中最大流.3、最大流与最小截设cDNxy,为 容 量 网 络.SGVSGVS,，SySx,且，SSB,表示D中起点在S而终点在S的边集，则称

39、B为yx,截边集，而BaacBc称为B的容量，记为capB.具有最小容量的yx,截边集称为N中的最小截.最大流最小截定理：在任何容量网络N中，最大流量等于最小截容量.整数最大流最小截定理：任何整容量网络中都存在整数最大流，而且其流量等于最小截容量.最大流最小截定理是网络分析方法的基础.由此定理不仅可以求出网络中的最大流和最小截，而且可以导出图论中许多著名的定理.9 网络流的应用一、运输方案的设计商品从产地运到销地必经之途构成一个交通系统.假定此交通系统多段运输容量给定.试设计一个运输方案，由此方案将产地运到销地有最大的输送量.如果再想提高输送量，需要增加那些路段的运输容量.试将此交通系统看作是

40、一个容量网络),(cDNxy，其中 D 是由这个交通系统精选学习资料 -名师归纳总结-第 19 页，共 22 页学习必备欢迎下载构成的简单连通图，发点x和收点y分别看作商品的产地和销地，容量函数)(Dc看成是运输容量.于是上述问题归结为在N 中求一个最大（yx,）流和最小容量的（yx,）截边集.设)(Df是 N=),(cDxy中的),(yx流，u是 D 中顶点，xu，并设 P是 D中一条连接x和u的路（未必是有向路）.给定 P 从 x 到 u 的方向为正向，用P和P分别表示E（P）中与 P的正向和反向一致的边集.令PaafPaafaca若若),(),()()(并令)(|)(min)(pEaau

41、P若0)(uP.则称 P 是f的饱和路；若0)(uP，则称 P 是非f饱和路.非f饱和的xy路 P 称为f增广路.之所以称为增广路,是由于流 f 的流量沿此路是可以增加的.事实上，由其它若若),(),()(),()()(afPayafPayafafPP所定义的)(Df是N中的),(yx流并且)(yfvalfvalP此处f称为基于f的增广路P的修正流.定理),(,cDNyx中的),(yx流f是最大流N 中不含f增广路.此定理提供了一个求整容量网络中最大流（最小截）的有效算法.算法的基本思想是从 N 中任何一个已知（x,y）流f（例如零流）开始，递归地构造出一个其流量不断增加的序列，并且终止于最大

42、流.在每个新的流f作出之后.如果存在f增广路 P，则作出基于P 的修正流f，然后将f作为初始流重新执行算法.如果不存在f增广路，则算法停止，由定理知f是最大流.二、最优运输方案的设计在前面设计运输方案时，我们考虑的仅仅是流量，而没有考虑到费用（或者说仅考虑在各路段中单位输送量的费用都相等）.在实际问题中，费用的因素很重要.由于在各路段中运输设备的不同，因此单位输送量的费用不尽相等.这就要求我们设计一个输送量最大且总的运输费用最小的运输方案，这样的运输方案称为最优运输精选学习资料 -名师归纳总结-第 20 页，共 22 页学习必备欢迎下载方案.用一个被称为费用容量网络),(cbDNXY表示该交通

43、系统，其中)(Db表示单位流量费用函数，)(Dc是容量函数.边 上 的 有 序对 分 别表 示 该边上 的 费用（单位流）和容量.费用容量网络),(,cbDNyx设 f 是 N 中（x,y）流，则)()()()(DEaabaffb定义为 f 的费用.用网络的语言来说，最优运输方案的设计就是在费用容量网络),(,cbDNyx中求最大（x,y）流f且使费用)(fb最小，这样的流就称为最小费用最大流.设),(,cbDNyx为费用容量网络，f是 N 中（x,y）的流，C 是 D 中有指定正向的圈.令CaafCaafaca若若),(),()()()(|)(min)(CEaaC若 D 中的圈 C 存在一个

44、定向使)(C0，则称 C 为 f 增广圈，对于f增广圈 C，定义)(Df如下：，其它，若若)()()(),()()(afCaCafCaCafaf易证f是 N 中（x,y）流而且valffval.f称为基于f增广圈 C 的修正值.精选学习资料 -名师归纳总结-第 21 页，共 22 页学习必备欢迎下载设 C 是 f 增广圈，则定义f 增广圈 C 的费用为CaCaababfcb)()(),(若对 N 中其流量等于valf的任何一个),(yx流f均有)()(fbfb，则称f为最小费用流.定理 N 中),(yx流f是最小费用流N 中每条增广圈C 都有0),(fCb.此定理提供了解最小费用最大流问题的一个算法，其基本思想是：从N 中任何一个),(yx最大流f出发，检查每个f增广圈.若所有f增广圈的费用都是非负的，则f就是所求的最小费用最大流.若存在f增广圈 C 使得0),(fCb，则用修正流f替代f再重复上述过程.关于寻找费用为负的f增广圈，可以通过作辅助图)(fD及其负圈来解决，具体作法从略.精选学习资料 -名师归纳总结-第 22 页，共 22 页