5经典图论问题 5.1 一笔画问题 一笔画算法即是从起点a开始选择关联边（第一这条边不是往回倒，第二这条边在前面延伸路上没有出现过）向前延伸，如果到达终点b，得到a—b迹，判断路上的的边数是否为图的总边数，是就终止，否则选择迹上某个关联边没有用完的顶点v，用同样方式再搜索v—v的闭迹，添加到a—b迹上，即得到a—v---v—b迹，如果这个迹的边数还没有达到总边数，则再选择迹上某个关联边没有用完的顶点。。。。。。逐步扩展即可。
二、弗罗莱（Fleury ）算法 任取v 0∈V(G)，令P 0=v 0； 设P i =v 0e 1v 1e 2…e i v i 已经行遍，按下面方法从中选取e i+1： （a ）e i+1与v i 相关联； （b ）除非无别的边可供行遍，否则e i+1不应该为G i =G-{e 1,e 2, …, e i }中的桥（所谓桥是一条删除后使连通图不再连通的边）； （c ）当（b ）不能再进行时，算法停止。 5.2 中国邮递员问题（CPP ） 规划模型： 设ij x 为经过边j i v v 的次数，则得如下模型。 ∑∈= E v v ij ij j i x z ?min ∑ ∑ E ∈E ∈∈=j i i k v v i v v ki ij V v x x , E ∈∈≤j i ij v v N x ,1 ..t s
5.3旅行推销员问题（TSP，货郎担问题）（NPC问题） 定义：包含图G的所有定点的路（圈）称为哈密顿路（圈），含有哈密顿圈得图称为哈密顿图。 分析：从一个哈密顿圈出发， 算法一：（哈密顿圈的充要条件：一包含所有顶点的连通子图，二每个顶点度数为2） 象求最小生成树一样，从最小权边加边，顶点度数大于3以及形成小回路的边去掉。 算法二： 算法三：
第三章 匹配理论 §3.1 匹配与最大匹配 定义3.1.1 设G 是一个图, )(G E M ?，满足:对i e ?,M e j ∈，i e 与j e 在G 中不相邻，则称M 是G 的一个匹配。对匹配M 中每条边uv e =，其两端点 u 和 v 称为被匹配M 所匹配，而 u 和 v 都称为是M 饱和的(saturated vertex )。 注:每个顶点要么未被M 饱和, 要么仅被M 中一条边饱和。 定义3.1.2 设M 是G 的一个匹配, 若G 中无匹配M ′, 使得||||M M >′, 则称M 是G 的一个最大匹配；如果G 中每个点都是M 饱和的, 则称M 是G 的完美匹配(Perfect matching ). 显然, 完美匹配必是最大匹配。 例如，在下图G 1中，边集{e 1}、{e 1,e 2}、{e 1,e 2,e 3}都构成匹配，{e 1,e 2,e 3}是G 1的一个最大匹配。在 G 2中，边集{e 1,e 2,e 3,e 4}是一个完美匹配，也是一个最大匹配。 定义3.1.3 设M 是G 的一个匹配, G 的M 交错路是指其边M 和M G E \)(中交替出现的路。如果G 的一条M 交错路(alternating path)的起点和终点都是M 非饱和的，则称其为一条M 可扩展路或M 增广路(augmenting path)。 定理 3.1.1(Berge,1957) 图G 的匹配M 是最大匹配的充要条件是G 中不存在M 可扩展路。 证明:必要性:设M 是G 的一个最大匹配。如果G 中存在一个M 可扩展路P ,则将P 上所有不属于M 的边构成集合M ′。显然M ′也是G 的一个匹配且比M 多一条边。这与M 是最大匹配相矛盾。 充分性:设G 中不存在M 可扩展路。若匹配M 不是最大匹配，则存在另一匹配M ′,使 ||||M M >′. 令 ][M M G H ′⊕=，(M M M M M M ′?′=′⊕∩∪称为对称差)。 则H 中每个顶点的度非1即2(这是因为一个顶点最多只与M 的一条边及M ′的一条边相关联)。故H 的每个连通分支要么是M 的边与M ′的边交替出现的一个偶长度圈，要么是M 的边与M ′的边交替出现的一条路。 由于||||M M >′，H 的边中M ′的边多于M 的边，故必有H 的某个连通分支是一条路，且始于M ′的边又终止于M ′的边。这条路是一条M 可扩展路。这与条件矛盾。 证毕。
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论与数学的关系 图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。 图论的起源 图论起源于著名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸联结起来 问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。然而无数次的尝试都没有成功。欧拉在1736年解决了这个问题，他用抽像分析法将这个问题化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条线来代替，从而相当于得到一个“图”（如下图）。 欧拉证明了这个问题没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这就是后
来的欧拉路径和欧拉回路。这项工作使欧拉成为图论〔及拓扑学〕的创始人。 汉密尔顿的游戏与图论 1859年，英国数学家汉密尔顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即“绕行世界”。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个生成圈后来被称为汉密尔顿回路。这个问题后来就叫做汉密尔顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为汉密尔顿问题，从而引起广泛的注意和研究。 四色猜想 在图论的历史中，还有一个最著名的问题－－四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。这一问题最早于1852年由Francis Guthrie提出，最早的文字记载则现于德摩根于同一年写给哈密顿的信上。包括凯莱、肯普等在内的许多人都曾给出过错误的证明。泰特(Tait)、希伍德(Heawood)、拉姆齐和哈德维格(Hadwiger)对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969年，Heinrich Heesch发表了一
常见问题： 1、图论的历史 图论以图为研究对象的数学分支。图论中的图指的是一些点以及连接这些点的线的总体。通常用点代表事物，用连接两点的线代表事物间的关系。图论则是研究事物对象在上述表示法中具有的特征与性质的学科。 在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。例如，国家用点表示，有外交关系的国家用线连接代表这两个国家的点，于是世界各国之间的外交关系就被一个图形描述出来了。另外我们常用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系等等。 事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。由此经数学抽象产生了图的概念。研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。 图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段： 第一阶段是从1736年到19世纪中叶。当时的图论问题是盛行的迷宫问题和游戏问题。最有代表性的工作是著名数学家L.Euler于1736年解决的哥尼斯堡七桥问题(Konigsberg Seven Bridges Problem)。 东普鲁士的哥尼斯堡城(现今是俄罗斯的加里宁格勒，在波罗的海南岸）位于普雷格尔(Pregel)河的两岸，河中有一个岛，于是城市被河的分支和岛分成了四个部分，各部分通过7座桥彼此相通。如同德国其他城市的居民一样，该城的居民喜欢在星期日绕城散步。于是产生了这样一个问题：从四部分陆地任一块出发，按什么样的路线能做到每座桥经过一次且仅一次返回出发点。这就是有名的哥尼斯堡七桥问题。 哥尼斯堡七桥问题看起来不复杂，因此立刻吸引所有人的注意，但是实际上很难解决。 瑞士数学家(Leonhard Euler)在1736年发表的“哥尼斯堡七桥问题”的文章中解决了这个问题。这篇论文被公认为是图论历史上的第一篇论文，Euler也因此被誉为图论之父。 欧拉把七桥问题抽象成数学问题---一笔画问题，并给出一笔画问题的判别准则，从而判定七桥问题不存在解。Euler是这样解决这个问题的：将四块陆地表示成四个点，桥看成是对应结点之间的连线，则哥尼斯堡七桥问题就变成了：从A，B，C，D任一点出发，通过每边一次且仅一次返回原出发点的路线(回路)是否存在？Euler证明这样的回路是不存在的。 第二阶段是从19世纪中叶到1936年。图论主要研究一些游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题。一些图论中的著名问题如四色问题(1852年)和Hamilton环游世界问题(1856年)也大量出现。同时出现了以图为工具去解决其它领域中一些问题的成果。1847年德国的克希霍夫(G.R.Kirchoff)将树
数学竞赛中的图论问题
分类号密级 U D C 编号 本科毕业论文(设计) 题目数学竞赛中的图论问题 所在院系数学与数量经济学院 专业名称数学与应用数学 年级 08级 学生姓名李曼 学号 0850410013 指导教师孙静
二 0一二年三月 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在孙静老师的指导下独立进行研究所取得的研究成果. 除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品.本人完全意识到本声明的法律后果由本人承担. 作者：
日期：2012年3月29日 文献综述 一综述 在18世纪30年代，一个非常有趣的问题引起了欧洲数学家的浓厚兴趣，这个问题就是著名的哥尼斯堡七桥问题，即要求遍历哥尼斯堡七桥中的每一座桥恰好一次后回到出发点. 欧拉证明这是不可能完成的. 此后，欧拉发表了著名的论文《依据集合位置的阶梯方法》，这是图论领域的第一篇论文，标志着图论的诞生. 图论的真正发展始于20世纪五六十年代之间，是一门既古老又年轻的学科. 图论极有趣味性，严格来讲，它是组合数学的一个重要分支. 虽然图论只是研究点和线的学科,但是它的应用领域十分广泛，不仅局限于数学和计算机学科，还涵盖了社会学、交通管理等. 总的来说，图论这门科学具有以下特点：（1）图论蕴含了丰富的思想、漂亮的图形和巧妙的证明； （2）涉及的问题多且广泛，问题表明上简单朴素，本质上却十分深刻复杂； （3）解决问题的方法千变万化，非常灵活，常常是一种问题一种解法. 由以上三个特点可以看出，图论与其他的数学分支不同，它不像群论、拓扑等学科那样有一套完整的体系和解决问题的系统. 而且图论所研究的内容非常广泛，如图的连通性、遍历性、图的着色、图的可平面性等等. 二内容 由于图论具有蕴含了丰富的思想、漂亮的图形和巧妙的证明，涉及的问题多且广泛，问题表面上简单朴素，本质上却十分深刻复杂，解决问题的方法千变万化，非常灵活，常常是一种问题一种解法的特点. 随着数学竞赛越来越规范化，并且越来越考察考生的灵活运用知识的能力. 因此近年来，图论问题频繁的出现在数学竞赛中，如典型的一笔画问题、中国邮递员问题、旅游推销员问题、排课表问题等.
第二章 图的连通性 连通图：任二顶点间有路相连。 例 可见在连通图中，连通的程度也是有高有低。 本章的目的就是定义一种参数来度量连通图连通程度的高低。 §2.1 割边、割点与连通度 一、割点： 定义2.1.1 设)(G V v ∈，如果)()(G w v G w >?，则称v 为G 的一个割点。（该定义与某些著作有所不同，主要是在有环边的顶点是否算作割点上有区别）。 例 定理2.1.1 如果点v 是图G 的一个割点，则边集E (G)可划分为两个非空子集1E 和2E ，使得 ][1E G 和][2E G 恰好有一个公共顶点v 。 推论2.1.1 对连通图G ，顶点v 是G 的割点当且仅当v G ?不连通。 以上两个结论的证明留作习题。 定理2.1.2 设v 是树T 的顶点，则v 是T 的割点当且仅当1)(>v d 。 证明：必要性：设v 是T 的割点，下面用反证法证明1)(>v d 。 若0)(=v d ，则1K T ?，显然v 不是割点。 若1)(=v d ，则v T ?是有1)(??v T ν条边的无圈图，故是树。从而)(1)(T w v T w ==?。因此v 不是割点。 以上均与条件矛盾。 充分性：设1)(>v d ，则v 至少有两个邻点u ,w 。路uvw 是T 中一条),(w u 路。因T 是树，uvw 是T 中唯一的),(w u 路，从而)(1)(T w v T w =>?。故v 是割点。证毕。 推论2.1.2 每个非平凡无环连通图至少有两个顶点不是割点。 证明：设T 是G 的生成树，则T 至少有两个叶子u ,v ，由上一定理知，u ,v 都不是T 的割点，即1)()(==?T w u T w 。由于u T ?是图u G ?的生成树，故 )(1)()()(G w T w u T w u G w ===?=?，
第67讲图论问题(一) 本节主要内容是：把一个具体问题用图形表示出来，利用图形的直观性可能更有利于问题的解决． 有关的一些概念：由若干个不同的点及连接其中某些点对的线所组成的图形就称为图．图中的点的集合称为图的点集，记为V：V＝{v1，v2，…，v n，…}；图中的线的集合称为图的线集(边的集合)，记为E：E＝{v i v j}(v i，v j∈V)．故一个图由其点集V和线集E所决定，若用G 表示图，则记为G＝G(V；E)．含有n个点的图称为n阶图． 在一个图中，如果某点v共连了k条线，则说此点的“次数”(或“度数”)为k，记为deg v＝k.如果一个p阶图的每两个顶点间都连且只连了1条线，则称该图为p阶完全图，记为K p． 若对每条线确定一个方向(即确定了线的两个端点中一个为“起点”，另一个为“终点”．这时，线是点的“有序对”)，则得到“有向图”；对有向图的一个顶点v，deg v＝k，若v是其中n条边的起点，m条边的终点(m＋n＝k)，则称v的出次为n，入次为m．链：若在一个图G＝(V；E)中取n+1个顶点v1、v2、…、v n+1，每两个相邻的顶点v i、v i+1间连有一条边l i,则边l1,l2,…,l n就称为从v1到v n+1的一条链．n称为链的长度． A类例题 例1 ⑴证明任意的六人中一定有三个人互相认识或互不认识(约定甲认识乙就意味着乙认识甲)． ⑵ K6的边染成红蓝两色，求证：其中必有两个三角形，其三边同色． 分析⑴以点表示人，连红、蓝两色的线分别表示“认识”与“不认识”，问题转化成图的问题．要会把题目的语言转译成图的语言：“三人互相认识”就表示三点间都连红线，“三人互不认识”就表示三点间都连蓝线．⑵考虑每个异色三角形的三个角，其中两个角是异色角，而同色三角形的三个角都是同色角． 证明⑴用6个点v1，v2，…，v6表示这6个人，如果某两人相互认识，则在表示此二人的点间连一条红线，否则连一条蓝线．于是问题转化为证明此6点间一定连出了三边均为红色或蓝色的三角形． 在点v1连出的5条线中，由抽屉原理知，必有某色线连有3条或3条以上．不妨设红线连了至少3条．设v1与v2、v3、v4连的红线．现考虑点v2、v3、v4连线的情况，如果此三点间有任两点连的红线，则出现红色三角形(例如v2v3连红线，则v1v2v3是红色三角形)，如果这三点间都不连红线，则出现蓝色三角形(v2v3v4是蓝色三角形)．故证． ⑵考虑K6共连了C26＝15条线，共得到C36＝20个三角形．设第i个顶点连了r i(0≤i≤5) 条红线，5－r i条蓝线．由于r i(5－r i)≤6．所以，连出的异色角个数≤6×6＝36个．由于每个异色的三角形有2个异色角，所以图中异色三角形个数≤18，故图中同色三角形个数≥20－18＝2． 说明题⑴是早期匈牙利的一个图论竞赛题．解这类“实际问题”时，重要的是会用图的语言解释题意，把实际问题改写为图的问题． ⑵用异色角来解相关问题是较好的方法． 例2 由5人组成一个公司，其中任意三人总有2人彼此认识，也总有2人彼此不认识．证明：这五人可以围桌而坐，使每人两旁都是他认识的人．(1978年保加利亚数学竞赛) 证明用5个点表示这5个人，若两人互相认识，则在表示这2个人的点间连1条线．题
离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝
图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( )． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f
第68讲 图论问题(二) 本讲主要内容：本讲将继续研究用图来解决问题的方法． 偶图 取图G ＝(V ，E )，如果V ＝X ∪Y ，X ∩Y ＝ ，其中X ＝{x 1，x 2，…，x n }，Y ＝{y 1，y 2，…，y m }，且x i 与x j (1≤i ＜j ≤n )，y s 与y t (1≤s ＜t ≤m )均互不相邻，则称G 为偶图． 色数：将图G 的顶点涂上颜色，如果至少要k 种颜色才能使任意两个相邻的顶点颜色不同，则称G 的色数为k ．显然，偶图的色数≤2．即偶图色数不超过2． A 类例题 例1 在空间中给定2n 个不同的点A 1，A 2，…，A 2n ，n ＞1，其中任意三点不共线．设M 是n 2+1条以给定的点为端点的线段的集合．⑴证明：存在一个三角形，其顶点为给定的点，其 边都属于M ．⑵证明：若集合M 的元素不超过n 2个，则这样的三角形可能不存在．(1973年奥 地利数学竞赛) 分析 可以从简单的情况开始试验，发现规律再证明．从K 4(4阶完全图，见67讲)共有多少条线及多少个三角形、擦去1条线去掉几个三角形入手得出结论，对于K 5、K 6也能用此法得到结论，但对于p ＞6，K p 难用此法，如何过渡到一般情况？可以用数学归纳法． 证明：n ＝2时，在4个点间连了5条线，由于4阶完全图在4个点间共可连出6条线，这6条线连出了4个以此4点中的某3点为顶点的三角形．而每条线的两个端点与(除这条线的两个端点外的)另两个顶点可以连出共2个三角形，故去掉任何一条边都使连出三角形数减少2，于是在4个点间连5条线必连出了 以此4点中的3点为顶点的三角形． 设n ＝k 时，2k 个点间连有k 2＋1条线时，必有三角形出现．则当n ＝k ＋1时， 2(k ＋1)个点间连了(k ＋1)2＋1条线．此时，任取两个相邻的顶点v 1，v 2，如果在其余的顶点中有某个顶点与v 1，v 2都连了线，例如v 3与v 1，v 2都连了线(图4(1))， 则出现了三角形．如果其余所有的点与此二点都至多连出1条线(图4(2))，则去掉点v 1，v 2 及与这两点相邻的边，此时，余下2k 个点，至多去掉了2k ＋1条边，余下至少(k ＋1)2＋1－ (2k ＋1)＝k 2＋1条边，由归纳假设知，其中必有三角形． 综上可知，命题成立． 说明 若2n 个点间连了n 2条边，可以把这2n 个点分成两组，每组n 个点，规定同组的点 间都不连线，不同组的任何两点都连1条线，这样得到了一个完全偶图K n ，n ，此时共计连了n 2条线，但任取三点，必有两点在同一组，它们之间没有连线，于是不出现三角形． 例2 一个舞会有n (n ≥2)个男生与n 个女生参加，每个男生都与一些女生(不是全部)跳过舞，而每个女生都至少与1名男生跳过舞，证明，存在男生b 1，b 2与女生g 1，g 2，其中b 1与g 1跳过舞，b 2与g 2跳过舞．但b 1与g 2没有跳过舞，b 2与g 1没有跳过舞． 分析 就是要给出一种选择方法，按此方法操作，即可选出满足要求的两个男生与两个女生．可以用极端原理来证明这样的存在性命题． 证明 取所有男生中与女生跳舞人数最多的一个，设是b 1．b 1至少与1名女生没有跳过舞，取没有与b 1跳过舞的一名女生为g 2，g 2至少与1名男生跳过舞，设为b 2，显然b 1不是b 2，现在考虑所有没有与b 2跳过舞的女生，她们不能都没有与b 1跳过舞，(否则没有与b 1跳 (2)(1)图4 1212 2k (4)(3)(2) (1)21
图 论 大连市第二十四中学 邰海峰 重要的概念与定理 完全图 每两个顶点之间均有边相连的简单图称为完全图,有n 个顶点的完全图(n 阶完全图)记为n K . 顶点的度 图G 中与顶点v 相关联的边数(环按2条边计算)称为顶点v 的度(或次数),记为()d v .()G δ与()G ?分别表示图G 的顶点的最小度与最大度.度为奇数的顶点称为奇顶点,度为偶数的顶点称为偶顶点. 树 没有圈的连通图称为树,用T 表示,其中度为1的顶点称为树叶(或悬挂点).n 阶树常表示为n T . k 部图 若图G 的顶点集V 可以分解为k 个两两不相交的非空子集的并,即 1,()k i i j i V V V V i j == =?≠ 并且同一子集i V (1,2,,)i k =内任何两个顶点没有边相连,则称这样的图为k 部图,记作12(,,,;)k G V V V E =. 2部图又叫做偶图,记为(,;)G X Y E =. 完全k 部图 在一个k 部图12(,, ,;)k G V V V E =中,i i V m =(1,2,,)i k =,若对任意,,(,,1,2,,)i i j j v V v V i j i j k ∈∈≠=均有边连接i v 和j v ,则称图G 为完全k 部图,记为12,,,k m m m K . 欧拉迹 包含图中所有边的迹称为欧拉迹.起点与终点重合的欧拉迹称为闭欧拉迹. 欧拉图 包含欧拉迹的图为欧拉图. 欧拉图必是连通图. 哈密顿链(圈) 经过图上各顶点一次并且仅仅一次的链(圈)称为哈密顿链(圈).包含哈密顿圈的图称为哈密顿图. 平面图 若一个图G 可画在平面上,即可作一个与G 同构的图G ',使G '的顶点与边在同一平面内,且任意两边仅在端点相交,则图G 称为平面图. 一个平面图的顶点和边把一个平面分成若干个互相隔开的区域,称为平面图的一个面,在所有边的外面的面称为外部面,其余的称为内部面. 竞赛图 有向完全简单图称为竞赛图.有n 个顶点的竞赛图记作n K . 有向路 在有向图(,)D V U =中,一个由不同的弧组成的序列12,, ,n u u u ,其中i u 的起点为i v ,终点为1(1,2,,)i v i n +=,称这个序列为从1v 到1n v +的有向路(简称路),n 为这个路的长,1v 为路的起点,1n v +为路的终点.若11n v v +=,则称这个路为回路.
v v v ,,...,129n 4 []2 ∈∈≠=u V v V i j i j K i j ,,;,1,2,...,=G V V V E k (,,...,;)12=G V V V E k (,,...,;)12==?≠≤≤=V U V V V i j i j k i i i j k ,,,1,1=-C n n n 2 (1)12K n K n v v v n ,,...,12v v v n ,,...,12 一.知识与方法 1.图 平面上给定n 个点，其中某些点之间用边相连，得到的就是图，记作G 。叫做图G 的顶点。其集合记作V(G)，G 中所含的顶点个数n 叫做图G 的阶。两个顶点u 和v 之间有边相连，则称所连得的边为uv 或（U,V ），而且说u 和v 相邻。G 中的所有边构成的集合记作E （G ）。所有以v 为端点的边数叫做顶点v 的度，记作d （v ）。 在本讲中，除非特别说明，任一条边的两个顶点不同，且两点之间最多有一条边，这样的图称为简单图。 定理1 设G 是n 阶图，则G 中n 个顶点的度数之和等于边数的两倍。 如果一个简单图中，每两个顶点之间都有一条边，这样的图称为完全图，通常将有n 个顶点的完全图记为。完全图的边的数目是。 2.K 部图 如果图G 的顶点集V 可以分解为K 个两两不交且非空的子集的并，即，并且没有一条边其两个端点都在上述同一子集内，我们称这样的图G 为K 部图，记作。 如果在一个K 部图中，任何两点，均有u 和v 相邻，则称G 是完全K 部图。 定理2. 有n 个顶点且不含三角形的图G 的最大边数为. 3.染色问题 数学竞赛中的染色问题主要有两类：一类是问题本身就是用染色的方式给出的；另一类是借助于染色方式来解决问题。这些问题通常涉及到组合中的存在性问题、最值问题、构造问题等。常用的方法有抽屉原理、极端原理、数学归纳法、反证法、算两次或整体处理等。 二、典型例题选讲 例1. 九名数学家在一次国际数学会议上相遇，发现他们中的任意三个人中，至少有两个人可以用同一种语言对话。如果每个数学家至多可说三种语言，证明至少有三名数学家可以用同一种语言对话。（1978年美国数学奥林匹克试题） 证明：用九个点表示这九名数学家，如果某两个数学家能用第i 种语言对话，则在它们相应的顶点之间连一条边并涂以相应的第i 种颜色，这样就得到了一第一讲图论与染色问题
图论问题题目分类 Foj：福州大学oj，https://www.doczj.com/doc/c117481726.html, Hdu：杭州电子科大oj：https://www.doczj.com/doc/c117481726.html, Hoj的题目我都分在另一个题目分类里了，这里就不写了 1.生成树问题 poj 1258（入门） poj 2421（入门） poj 1679 poj 2728 poj 3164 poj 1639 poj 3522 2.最短路问题（包括差分约束系统） poj 3660（入门） poj 3159（入门） poj 1511 poj 3653 poj 1252 poj 3013 poj 3259 poj 1860 poj 3463 poj 2983 poj 1275 poj 1716（入门） poj 1201（入门） poj 3635（较难） 3.强连通，2-sat问题（包括拓扑排序） （重点：对于2-sat问题，理解好合取范式的意义就不难了）poj 2553（入门） poj 2723（入门） poj 1094（入门） hdu 1824 poj 3687 poj 3678 poj 3648 poj 2749 poj 3683 poj 3352
4.欧拉路径问题 poj 2513j poj 2337 5.连通性问题 poj 1144（入门） poj 1236 poj 2762 poj 2942 poj 1659 poj 3697（难） 6.网络流问题（包括最小割，01分数规划，费用流）poj 1459（入门） poj 1273（入门） zoj 2314（入门） poj 2396 poj 1149（难） poj 2186 poj 3498 poj 1637 poj 2125 poj 2516 hdu 2426 hdu 2435（较难） poj 2112 poj 3469 7.2分图问题 （重点：匈牙利算法，km算法） poj 3041（入门） poj 2226（有点难） hdu 2389 (得优化) poj 2771 poj 2195 poj 2516 poj 3020 foj 1202 8.最大团，图着色问题 poj 1129 zoj 1492
5经典图论问题 一笔画问题 中国邮递员问题（CPP）
规划模型： 设ij x 为经过边j i v v 的次数，则得如下模型。 ∑E ∈j i v v ij ij x w max ∑∑ E ∈E ∈∈=j i i k v v i v v ki ij V v x x , E ∈∈≤j i ij v v N x ,1 5.3 旅行推销员问题（TSP ） 分析： ..t s
算法一：象求最小生成树一样，从最小权边加边，顶点度数大于3以及形成小回路的边去掉。 算法二： 算法三：
规划模型： 先将一般加权连通图转化成一个等价的加权完全图，设当从i v 到j v 时，1=ij x ，否则， 0=ij x ，则得如下模型。 ∑∑==n i n j ij ij x w 11 min ∑===n j ij n i x 1 ,,1,1Λ ∑===n i ij n j x 1 ,,1,1Λ 1,,2-=n k Λ n i i k x x x k i i i i i i k ΛΛΛ1,,,1113221=-≤+++ 0=ij x 或1，j i n j i ≠=,,,1,Λ 排课表问题 问题一 定理：最小边色数()G χ'等于最大顶点度数()G ?。 以下加边循环算法为多项式时间算法：就是加边让每个顶点的度数一样（为最大度数），然后求一组完美匹配M ，着同样颜色，然后从图中去掉M 中的边,再求第二组完美匹配。。。。。。。。 ..t s
问题二：
基本思想是：由给定的教室数与总课时数确定教学时间长度（即匹配数--色数），在没有考虑教室数限制所计算的匹配数基础上，增加空匹配至时间长度个，然后调节匹配边差大于1的匹配，直到满足要求。