第七章图论与网络优化模型
图论与网络优化是数学建模的一个重要方面，经济管理、工业工程、通讯与网络技术等诸多领域中的问题都可以化为图论和网络模型进行研究。本章在介绍有关图的一些基本概念的基础上，主要介绍图与网络中的最短路、最小生成树、最大匹配等数学模型及其解法，最后，给出几个应用实例。
第一节图的概念和最小生成树
一、图与网络优化的例子
上述三个实例有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优方案或安排，数学称这种问题为优化问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络，与图和网络有关的优化问题称为网络优化。
二、图的概念
图的理论研究已经有了200多年的历史。早期的研究与数学游戏有关，哥尼斯堡七桥问题就是其中之一。
18世纪德国哥尼斯堡有一条河，河中有两个岛，
两岸与两岛间共架有七座桥。那时候，哥尼斯堡市民
生活很富足，市民们喜欢四处散步，于是便产生这样
的问题：是否可以设计一种方案，使得人们从自己家
里出发，经过每座桥恰好一次，最后回到家里。即一
个人能否不重复地走遍七座桥而回到原地。这便是著
名的“哥尼斯堡七桥问题”。
图7-1-1（a）
热衷于这个有趣问题的人们试图解决它，但一段
时间内竟然没有人能给出答案。后来，问题传到了著
名数学家欧拉那里，居然也激起了他的兴趣。他从人
们寻求路线屡遭失败的教训中敏锐地领悟到，也许这
样的方案根本就不存在。欧拉经过悉心的研究，1736年，年方29岁的欧拉终于解决了这个问题，并向圣
彼得堡科学院递交了一份题为《哥尼斯堡的七座桥》
的论文。论文不仅仅是解决了这一难题，而且引发了
一门新的数学分支——图论的诞生。
欧拉解决七桥问题时采用了图的方法。既然岛与
陆地无非是桥梁连接的，那么就不妨把A、B、C、D
4处抽象成4个点。并把7座桥抽象成7条边，便得到了七桥问题的模拟图。这样当然并未改变问题的实质，于是无重复地走过7座桥的问题就等价于一笔画出上述图形的问题，每条边必须且只能经过一次，即“一笔画”问题。
图7-1-1（b）
欧拉解决七桥问题时先考虑一般化的情况：如果任意给定一个河与任意多座桥，可否判断每座桥能否恰好走过一次呢？一般化的问题就要有一个一般解法，才有实际的意义。对此欧拉给出一般结论：
欧拉结论：连接奇数个桥的陆地仅有两个时，可实现要求。则从两者任一陆地出发，可以实现恰好经过每座桥一次，又回到家中。
可见，图论中所研究的图是由实际问题抽象出来的逻辑关系，这种图的画法具有一定的随意性，在保持相对位置和相互关系不变的前提下，点的位置不一定要按实际要求画，线的长度也不一定表示实际长度，而且画成直线或曲线都可以。通俗地说，这种图是一种关系示意图。
图：是由顶点集和边集组成的集合对(),G V E =，其中12(){,,,}V G v v v ν= 为节点集合， 12(){,,,}m E G e e e = 为边集合，图的节点可以表示城市、车站、计算机、人等，图的边可以是铁路、公路、输电线路、网线等，也可以是一种关系。
例1 图7-1-2（a ）(b)表示6家企业间的业务往来关系，其中点a,b,c,d,e,f 分别表示6家企业，两点的连线表示两家企业之间的业务联系。
子图：对于图(),G V E =，若有11,,V V E E ??则称1G 是G 的子图；
生成子图：如果，11,V
V E E =?，则称1G 是G 的生成子图； 有向图：对于图(),G V E =，()()12{,,,},,m k i j j i E e e e e v v v v ==≠ ，反之，无向图；
赋权图：若图(),G V E =中的每条边(),i j v v 都赋予一个数ij ω，称为赋权图，记为(),,G V E W =;
链：图(),G V E =中节点和边交替出现的序列称为链，记为()0112k k
v e v e e v 。 圈：两个端点重合的链称为圈。
路：有向图(),G V A =中的节点和边交替出现的序列称为路，()0112k k v e v e e v 称为从0v 到k
v 的路；两个端点重合的路称为回路。
连通图：若图(),G V E =中任意两点i v 到j
v 间至少有一条链，则称(),G V E =为连通图。
树:连通且不含圈的无向图称为树。树有以下显而
易见的性质：
（1）树是连通图，但无圈；
（2）树中任意两个顶点间必有且仅有一条链；（3）在树的两个不相邻的顶点间添上一条边，就得到一个圈；
（4）在树中去掉任何一条边，图就不连通；
（5）含有p个顶点的树有1
p 个边。
生成树：任意一个连通图或者是树，去掉一些边后可形成一棵树，这样的树称为连通图的生成树。生成树一般不唯一。
例2 图7-1-4（b）是7-1-4（a）的一个生成树。
三、最小生成树
在赋权图()
G V E W
=的所有生成树中，权数最小的生
,,
成树称为最小生成树，最小生成树的背景是线路最短、费用最小等问题。
例3 图7-1-5（a）表示5个村庄的线路图，每边旁的数字表示村庄之间道路的长度，现要求沿道路架设有线广播线，不仅使各村都能听到有线广播，而且使广播总长度最短。
显然，这个问题不光是要找出连接5个村庄的生成树，而且要找到一个广播总长最短的生成树，即最小生成树。
最小生成树用Kruskal（克鲁斯卡尔）算法（避圈法）计算，其步骤如下：
（1）把图()
=中的所有边按其权数大小排列，将
,,
G V E W
权数最小的边取进生成树T中。
（2）从剩下的边中按（1）的方法取下一条边，若该边与前面所取的边形成回路，则舍去该边，否则，就将这条边放进T中。
（3）重复这一过程，直到边数比节点数目少1. 例4 求图7-1-6所示的赋权图的最小生成树。
解：最小生成树示意图：
注：最小生成树不唯一，但不同的最小生成树的边权之和是唯一的。
练习：（最小生成树应用练习）：要在11个城市间建立通讯联络网，顶点----表示城市，权---城市间建立通讯线路所花费代价。问题：希望找到一个最小生成树，使它的每条边上的权值之和（即建立通讯网所需花费的总代价）最小----最小代价生成树（最小生成树）。
第二节 最短路
在生产实践、运输管理和工程建设的很多活动中，诸如物资的运输线路、各种工艺路线的安排、管道线网的铺设等等问题，都与寻找一个图的最短路密切相关，最短路问题是网络分析中的一个基本问题，它不仅可以直接应用于解决实际中的许多问题，而且经常被作为一个基本工具用于其它的优化问题。
一、两点之间的最短路
设给定赋权图(),,G V E W =，12(){,,,}k V G v v v = ，(){,},i j E v v = (),i j ij v v ωω=，求从一个节点i v 到另个节点j v 的最短距离。 我们的目的就是在图(),,G V E W =中找到一条节点i v
到另一个节点j v 的路径，并使其长度之和最短。
Dijkstra 在1959年提出了一种算法，是目前公认的求最短路径的较好的算法之一。
Dijkstra 算法的基本思路是动态规划的最优化原理：若1231,,,,,k k v v v v v - 是1v 到k v 的最短的路径。
()()()()112231,,,,min k k k d v v v v v v v v ωωω-=+++=
则1231,,,,k v v v v - 是1v 到1
k v -之间距离最短的路径。 ()()()()11122321,,,,min k k k d v v v v v v v v ωωω---=+++=
事实上，如果这个结论不成立，便可以找到从1v 到1
k v -的
更短路径，将原来的路径换掉以后就可以得到更短的路径，从而产生矛盾。
Dijkstra 算法其实是一种标号法，适用于所有权数大于零的情形。它的基本思想是从起点1v 出发，逐步向外探寻最短路，每一步都在寻找1
v 到这一个点的最小距离。执行过程中，给每一个顶点j
v 标号，使用临时标号和永久性标号，反复修改临时标号，并且把某一个具有临时标号的点改变为永久标号的点，从而使G 中具有永久标号的顶点数多一个。这样至多经过1k -步，就可以求出从1v 到k v 的最短的路径。
Dijkstra 算法的具体步骤为：
（1）给始点1v 标上永久标号1
()0p v =，给其余各点标上临时标号()j t v ，2,3,4,,j n = ，其中，j v 与1
v 直接相连，()1(),j j t v v v ω=；若j v 与1v 不直接相连，则()j t v =∞。这里()j t v 表示从j v 一步到1
v 的距离。令 {}{}123,,,,c n S v S v v v == （complementary set ）
（2）寻找1v 到c
s 距离最短的点1
j v ，赋予永久标号 {}1()()min c
j j j v S p v t v ∈=，
令 {}11,j S v v =，\c S V S =
修改c S 中各临时标号，对c j v S ∈
(){}11()min (),(),j j j j j t v t v p v v v ω=+
新的()j t v 是c j v S ∈一步直接到1v ，
或者经过1j v 两步到达1v 的最短距离。
（3）重复（2），直到k
v 进入S 停止，找到最短路径和距离。
例5 图7-2-1所示是某地区交通运输路线的示意图。用Dijkstra 算法分别求从0v 到3v ，0v 到4v ，0v 到7v 的最短路。
解：利用Dijkstra 算法进行计算。第一次临时标号的值如表7-2-1的第一行所示。{}0,S v = {}1237,,,,c S v v v v = 在这些临时标号中，1()t v 最小，给1v 赋予永久标号1
()1p v =。令 {}{}01
237,,,,,,c S v v S v v v == 重新计算c S 种各节点的临时标号
在这一轮的临时标号中，最小的是2
()t v ，给它赋予永久标号2
()2p v =。调整集合 {}{}01237,,,,,,c S v v v S v v ==
重新计算c
S 种各节点的临时标号
在这一轮的临时标号中，最小的是3
()t v ，给它赋予永久标号3
()3p v =。调整集合 {}{}01234567,,,,,,,,c S v v v v S v v v v ==
重复这样的过程，直到4567
,,,v v v v 进入集合S 结束。具体计算用表格7-2-1的形式给出。
表7-2-1
根据表7-2-1中()j p v 出现的情况，可以求出从0v 到3v 的最优路径为023v v v ，最短路长度为3；0v 到4
v 的最优路径为0234v v v v ，最短路长度为6，0v 到7v 的最优路径为0237v v v v ，最短路长度为9。事实上，表7-2-1已经给出了从0v 所有点的最优路径及其长度，见图7-2-2.
练习：最短路应用举例
图论复习题答案 一、判断题，对打，错打 1．无向完全图是正则图。 () 2．零图是平凡图。() 3．连通图的补图是连通图.() 4．非连通图的补图是非连通图。() 5．若连通无向简单图G中无圈，则每条边都是割边。() 6．若无向简单图G是（n，m）图，并且m=n-1，则G是树。() 7．任何树都至少有2片树叶。() 8．任何无向图G都至少有一个生成树。() 9．非平凡树是二分图。() 10．所有树叶的级均相同的二元树是完全二元树。() 11．任何一个位置二元树的树叶都对应唯一一个前缀码。() 12． K是欧拉图也是哈密顿图。() 3,3 13．二分图的对偶图是欧拉图。() 14．平面图的对偶图是连通图。() 页脚内容1
15．设G*是平面图G的对偶图，则G*的面数等于G的顶点数。() 二、填空题 1．无向完全图K6有15条边。 2．有三个顶点的所有互不同构的简单无向图有4个。 3．设树T中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T中有10片树叶。 4．若连通无向图G是（n，m）图，T是G的生成树，则基本割集有n-1个，基本圈有m-n+1个。 5．设连通无向图G有k个奇顶点，要使G变成欧拉图，在G中至少要加k/2条边。 6．连通无向图G是（n，m）图，若G是平面图，则G有m-n+2个面。 三、解答题 1．有向图D如图1所示，利用D的邻接矩阵及其幂运算 求解下列问题： （1）D中长度等于3的通路和回路各有多少条。 （2）求D的可达性矩阵。 （3）求D的强分图。 解：（1） a b c d e 图1 页脚内容2
页脚内容3 M=????????????????000101000000001 010*******M 2=?? ? ? ??????? ?????010******* 000101000001000 M 3=????????????????10000 01000010000001010000M 4=??? ???? ? ??? ?????00010 01000 100000100000010 由M 3可知，D 中长度等于3的通路有5条，长度等于3的回路有3条。 （2） I+M+M 2+M 3+M 4=????????????? ???100000100000100 0001000001 +??????????? ?? ???000101000000001 010******* +??????????? ?? ???010000001000010 1000001000 +??? ???? ? ??? ?? ???100000100001000 0001010000 + ????????????????00010 01000100000100000010 =??? ???? ???? ?? ???21020 1301011111 020******* D 的可达性矩阵为 R=B （I+M+M 2+M 3+M 4）=??? ???? ? ????? ???110101********* 1101011011 b c d e 图1
图论练习题 一、基本题 1、设G是由5个顶点构成的完全图，则从G中删去（）边可以得到树。 A．6 B．5 C．8 D．4 2、下面哪几种图不一定是树（）。 A．无回路的连通图 B．有n个结点，n-1条边的连通图 C．对每对结点间都有通路的图 D．连通但删去任意一条边则不连通的图。 3、5阶无向完全图的边数为（）。 A．5 B．10 C．15 D．20 4、把平面分成x个区域，每两个区域都相邻，问x最大为（） A．6 B．4 C．5 D．3 5、设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是（） A．n/2 B．n(n+1) C．nk-2m D．n(k+1)-2m 6、设G=
第八讲图论中的匹配与逻辑推理问题 先看一个例题.中、日、韩三个足球队进行比赛，已知A不是第一名，B不是韩国队，也不是第二名，第一名不是日本队，中国队第二.问A、B、C各代表哪国队？各是第几名？ 一般解这类题都归于逻辑推理类问题. 我们先来降低难度.先只要求你判断出中、日、韩各是第几名（不必判断A、B、C）.可以把中、日、韩各用一个点代表，列于上一行.第一、二、三名各用一个点代表，列于下一行，记为： V1=｛中，日，韩｝，V2=｛第1名，第2名，第3名｝. V1中的点与V2中某一个点有肯定关系的，就画一条实线，如和②.否定关系的两点之间画一条虚线，如不是②；不是①.把已知条件不加任何推理地表现于图上.虚线2条，实线1条，共3条线. 现在，有两个明显的事实；第一，V1中每点有且只有一条实线与V2中相应点配对，V2中每点有且只有一条实线与V1中相应点配对.V1内部点之间不会有线相联结，V2内部点之间也不会有线相联结.第二，从V1（或V2）中某一个点，例如说a点如发出了一条实线向着V2（或V1）中某一个点，例如说x点，那么a点与V2（或V1）中其他点之间必然只能用虚线联结.（这是逻辑推理中的排它性） 由此，我们很容易将中、日、韩的名次判出. 这样的问题，抽象起来可归属于图论中称之为“二分图的匹配”问题. 图论的名词术语太多，这里不作详细定义，只是描述性介绍一下，大家以前在“一笔画”等讲中已初步接触.所谓二分图，就是顶点集合可以划分成两个部分，V=V1＋V2，如V1有p个点，记为V1=｛v1，v2…，v p｝，V2有q个点，记为V2=｛v p+1，v p+2…，v p+q｝，而V1中任意一点，不会
学号：0441 姓名：张倩 习题1 4．证明图1-28中的两图是同构的 证明：将图1-28的两图顶点标号为如下的(a)与(b)图 作映射f : f(v i )?u i (1? i ? 10) 容易证明，对?v i v j ?E((a)),有f(v i v j )?u i u j ?E((b)) (1? i ? 10, 1?j? 10 ) 由图的同构定义知，图1-27的两个图是同构的。 5.证明：四个顶点的非同构简单图有11个。 证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： m=2： m=3： (a) v 1 v 2 v 3 v v 5 v 6 v 7 v 8 v 9 v 10 u 1 u 2 u 3 u 4 u 5 u 6 u 7 u 8 u 9 u 10 (b)
m=4： m=5： m=6： 因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1）不是图序列。 证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列； （6,6,5,4,3,3,1）是图序列 ()1 1 123121,1,,1,,,=d d n d d d d d π++---是图序列 （5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 12.证明：若δ≥2，则G 包含圈。 证明 只就连通图证明即可。设V(G)=｛v1,v2,…,vn｝,对于G 中的路v1v2…vk,若vk 与v1邻接，则构成一个圈。若vi1vi2…vin 是一条路，由于?? 2，因此，对vin ，存在点vik 与之邻接，则vik?vinvik 构成一个圈 。 17.证明：若G 不连通，则G 连通。 证明 对)(,_ G V v u ∈?,若u 与v 属于G 的不同连通分支，显然u 与v 在_ G 中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点，则u 与w ，v 与w 分别在_ G 中连通，因此，u 与v 在_ G 中连通。
数学建模常用的十大算法==转 (2011-07-24 16:13:14) 转载▼ 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MA TLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MA TLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的
本系列共14讲 第八讲图论中的匹配与逻辑推理问题 . 文档贡献者：与你的缘 先看一个例题.中、日、韩三个足球队进行比赛，已知A不是第一名，B 不是韩国队，也不是第二名，第一名不是日本队，中国队第二.问A、B、C 各代表哪国队？各是第几名？ 一般解这类题都归于逻辑推理类问题. 我们先来降低难度.先只要求你判断出中、日、韩各是第几名（不必判断A、B、C）.可以把中、日、韩各用一个点代表，列于上一行.第一、二、三名各用一个点代表，列于下一行，记为： V1=｛中，日，韩｝，V2=｛第1名，第2名，第3名｝. V1中的点与V2中某一个点有肯定关系的，就画一条实线，如和②.否定关系的两点之间画一条虚线，如不是②；不是①.把已知条件不加任何推理地表现于图上.虚线2条，实线1条，共3条线. 现在，有两个明显的事实；第一，V1中每点有且只有一条实线与V2中相应点配对，V2中每点有且只有一条实线与V1中相应点配对.V1内部点之间不会有线相联结，V2内部点之间也不会有线相联结.第二，从V1（或V2）中某一个点，例如说a点如发出了一条实线向着V2（或V1）中某一个点，例如说x点，那么a点与V2（或V1）中其他点之间必然只能用虚线联结.（这是逻辑推理中的排它性）
由此，我们很容易将中、日、韩的名次判出. 这样的问题，抽象起来可归属于图论中称之为“二分图的匹配”问题. 图论的名词术语太多，这里不作详细定义，只是描述性介绍一下，大家以前在“一笔画”等讲中已初步接触.所谓二分图，就是顶点集合可以划分成两个部分，V=V1＋V2，如V1有p个点，记为V1=｛v1，v2…，v p｝，V2有q个点，记为V2=｛v p+1，v p+2…，v p+q｝，而V1中任意一点，不会与V1中其他点联结，而只能与V2中某些点联结；V2也如此.大家看几个例. 一般的图记为G＝（V，E），V是顶点集合，E是边（也可称为线）的集合.大家在哥尼斯堡七桥问题中已领略过这种抽象.现在的二分图是一类特殊的图，只不过顶点集V划分为两部分，而这只能“跨越”于V1中某个点和V2中另一个点.二分图的匹配问题，就是找一个边的集合，这些边之间都没有公共的端点. 关于二分图的匹配，要研究的是“最大匹配”，即找一个边最多的匹配. 就本讲开始引入的问题看，我们还没有解完，因为还有A、B、C三个代号到底如何归于中、日、韩三队的问题.一种解题办法，是把已判出的国籍和名次捆绑在一个顶点内，如（中2）、（韩1）、（日3），再和A、B、C构造一个新的二分图：
图论模型简介 一、图及其矩阵表示 1、起源：哥尼斯堡七桥问题： 欧拉为了解决这个问题，建立数学模型：陆地——点，桥——边，得到一个有四个“点”，七条“边”的“图”。问题转化为能否从任一点出发一笔画出七条边再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画判定法则：图是连通的，且每个顶点都与偶数条边相关联（这种图称为欧拉图）。由此可以得出结论：七桥问题无解。
2、基本概念： 图（graph）：由顶点和边（又称线，边的两端必须是顶点）组成的一个结构。 邻接：一条边的两个端点称是邻接的；关联：边与其两端的顶点称是关联的。 无向图（graph）：边无方向的图；有向图（digraph）：边有方向的图。 路(path)：由相邻边组成的序列，其中中间顶点互不相同。 圈(cycle)：首、尾顶点相同的路，即闭路。 连通图（connected graph）：图中任意两顶点间都存在路的图。 树（tree）：无圈连通图 完全图（complete graph）：任意两个顶点之间都有边相连的无向图，记为K n。 竞赛图（tournament）：由完全图给每条边定向而得到的有向图。 二部图（bipartite graph）：图的顶点分成两部分，只有不同部分顶点之间才有边相连。图G的子图H（subgraph）：H是一个图，H的顶点（边）是图G的顶点（边）。 网络（Network）：边上赋了权的有向图。
3、图的矩阵表示 无向图 有向图 0100010 11001011 011000 1 00???????????????? ???? ? ? ? ? ????????0110010100000100100000110
数学建模中的图论方法 一、引言 我们知道，数学建模竞赛中有问题A和问题B。一般而言，问题A是连续系统中的问题，问题B是离散系统中的问题。由于我们在大学数学教育内容中，连续系统方面的知识的比例较大，而离散数学比例较小。因此很多人有这样的感觉，A题入手快，而B题不好下手。 另外，在有限元素的离散系统中，相应的数学模型又可以划分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。但是这类问题在MCM中非常少见，事实上，由于竞赛是开卷的，参考相关文献，使用现成的算法解决一个P类问题，不能显示参赛者的建模及解决实际问题能力之大小；还有一类所谓的NP问题，这种问题每一个都尚未建立有效的算法，也许真的就不可能有有效算法来解决。命题往往以这种NPC问题为数学背景，找一个具体的实际模型来考验参赛者。这样增加了建立数学模型的难度。但是这也并不是说无法求解。一般来说，由于问题是具体的实例，我们可以找到特殊的解法，或者可以给出一个近似解。 图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问题被巧妙地解决。而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如： AMCM90B－扫雪问题； AMCM91B－寻找最优Steiner树； AMCM92B－紧急修复系统的研制(最小生成树) AMCM94B－计算机传输数据的最小时间(边染色问题) CMCM93B－足球队排名(特征向量法) CMCM94B－锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性) CMCM98B－灾情巡视路线(最优回路) 等等。这里面都直接或是间接用到图论方面的知识。要说明的是，这里图论只是解决问题的一种方法，而不是唯一的方法。 本文将从图论的角度来说明如何将一个工程问题转化为合理而且可求解的数学模型，着重介绍图论中的典型算法。这里只是一些基础、简单的介绍，目的在于了解这方面的知识和应用，拓宽大家的思路，希望起到抛砖引玉的作用，要掌握更多还需要我们进一步的学习和实践。
习题十 1. 设G 是一个(n ，m)简单图。证明：，等号成立当且仅当G 是完全图。 证明：（1）先证结论： 因为G 是简单图，所以G 的结点度上限 max(d(v)) ≤ n-1, G 图的总点度上限为 max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G 图边的上限为 max(m) ≤ n(n-1)/2,所以。 （2） =〉G 是完全图 因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G 的每个结点的点度都为n-1，G 为完全图。 G 是完全图 =〉 因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数 。■ 2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。 证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。与题设m = n+1，矛盾。因此，G 中存在顶点u ，d （u ）≥3。■ 3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5） 解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。 可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明： (6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5} 每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)
251 图论模型 图论是运筹学的一个经典和重要分支，专门研究图与网络模型的特点、性质以及求解方法。许多优化问题，可以利用图与网络的固有特性而形成的特定方法来解决，比用数学规划等其他模型来求解往往要简单且有效得多。 图论起源于1736年欧拉对柯尼斯堡七桥问题的抽象和论证。1936年，匈牙利数学家柯尼希（D. K?nig ）出版的第一部图论专著《有限图与无限图理论》，树立了图论发展的第一座里程碑。近几十年来，计算机科学和技术的飞速发展，大大地促进了图论研究和应用，其理论和方法已经渗透到物理、化学、计算机科学、通信科学、建筑学、生物遗传学、心理学、经济学、社会学各个学科中。 9.1 图的基础理论 9.1.1 图的基本概念 所谓图，概括地讲就是由一些点和这些点之间的连线组成的。定义为(,)G V E =，V 是顶点的非空有限集合，称为顶点集。E 是边的集合，称为边集。边一般用(,)i j v v 表示，其中 ,i j v v 属于顶点集V 。 以下用V 表示图(,)G V E =中顶点的个数，E 表示边的条数。 如图9.1是几个图的示例，其中图9.1 (a)共有3个顶点、2条边，将其表示为 (,)G V E =，123{,,}V v v v =，1213{(,),(,)}E v v v v =. 2 3 v 45 v 3 4 (a) (c) 图9.1 图的示意图 1.无向图和有向图 如果图的边是没有方向的，则称此图为无向图（简称为图），无向图的边称为无向边（简称边）。如图9.1 (a)和(b)都是无向图。连接两顶点i v 和j v 的无向边记为(,)i j v v 或(,)j i v v 。 如果图的边是有方向（带箭头）的，则称此图为有向图，有向图的边称为弧（或有向边），如图9.1 (c)是一个有向图。连接两顶点i v 和j v 的弧记为,i j v v ??，其中i v 称为起点，j v 称为终点。显然此时弧,i j v v ??与弧,j i v v ??是不同的两条有向边。有向图的弧的起点称为弧头，弧的终点称为弧尾。有向图一般记为(,)D V A =，其中V 为顶点集，A 为弧集。 例如图9.1 (C)可以表示为(,)D V A =，顶点集1234{,,,}V v v v v =，弧集为1223{,,,, A v v v v =????243441,,,,,}v v v v v v ??????。 对于图除非指明是有向图，一般地，所谓的图都是指无向图。有向图也可以用G 表示。 例9.1 设12345{,,,,}V v v v v v =，12345{,,,,}E e e e e e =，其中
二、应用题 题0：（1996年全国数学联赛） 有n （n ≥6）个人聚会，已知每个人至少认识其中的[n /2]个人，而对任意的[n /2]个人，或者其中有两个人相互认识，或者余下的n -[n /2]个人中有两个人相互认识。证明这n 个人中必有3个人互相认识。 注：[n /2]表示不超过n /2的最大整数。 证明 将n 个人用n 个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G 。由条件可知，G 是具有n 个顶点的简单图，并且有 （1）对每个顶点x ， )(x N G ≥[n /2]； （2）对V 的任一个子集S ，只要S ＝[n /2]，S 中有两个顶点相邻或V-S 中有 两个顶点相邻。 需要证明G 中有三个顶点两两相邻。 反证，若G 中不存在三个两两相邻的顶点。在G 中取两个相邻的顶点x 1和y 1,记N G (x 1)＝{y 1,y 2,……,y t }和N G (y 1)={x 1,x 2,……,x k },则N G (x 1)和N G (y 1)不相交，并且N G (x 1)（N G (y 1)）中没有相邻的顶点对。 情况一；n=2r ：此时[n /2]＝r ，由（1）和上述假设，t=k=r 且N G (y 1)＝V-N G (x 1)，但N G (x 1)中没有相邻的顶点对，由（2），N G (y 1)中有相邻的顶点对，矛盾。 情况二；n=2r+1: 此时[n /2]＝r ，由于N G (x 1)和N G (y 1)不相交，t ≥r,k ≥r,所以r+1≥t,r+1≥k 。若t=r+1,则k=r ，即N G (y 1)=r ，N G (x 1)＝V-N G (y 1)，由（2），N G (x 1)或N G (y 1)中有相邻的顶点对，矛盾。故k ≠r+1，同理t ≠r+1。所以t=r,k=r 。记w ∈V- N G (x 1) ∪N G (y 1),由（2），w 分别与N G (x 1)和N G (y 1)中一个顶点相邻，设wx i0∈E, wy j0∈E 。若x i0y j0∈E ，则w ，x i0, y j0两两相邻，矛盾。若x i0y j0?E ，则与x i0相邻的顶点只能是(N G (x 1)-{y j0})∪{w},与y j0相邻的顶点只能是(N G (y 1)-{x j0})∪{w}。但与w 相邻的点至少是3，故N G (x 1)∪N G (y 1)中存在一个不同于x i0和y j0顶点z 与w 相邻，不妨设z ∈N G (x 1)，则z ，w ，x i0两两相邻，矛盾。 题1：已知图的结点集V ={a ,b ,c ,d }以及图G 和图D 的边集合分别为： E (G )={(a ,a ), (a ,b ), (b ,c ), (a ,c )} E (D)={, ,
数学建模中常见的十 大模型
精品文档 数学建模常用的十大算法==转 (2011-07-24 16:13:14) 转载▼ 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MA TLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的 收集于网络，如有侵权请联系管理员删除
第4章图论 综合练习 一、单项选择题 1．设L是n阶无向图G上的一条通路，则下面命题为假的是( )． (A) L可以不是简单路径，而是基本路径 (B) L可以既是简单路径,又是基本路径 (C) L可以既不是简单路径，又不是基本路径 (D) L可以是简单路径，而不是基本路径 答案：A 2．下列定义正确的是( )． (A) 含平行边或环的图称为多重图 (B) 不含平行边或环的图称为简单图 (C) 含平行边和环的图称为多重图 (D) 不含平行边和环的图称为简单图 答案：D 3．以下结论正确是 ( )． (A) 仅有一个孤立结点构成的图是零图 (B) 无向完全图K n每个结点的度数是n (C) 有n(n>1)个孤立结点构成的图是平凡图 (D) 图中的基本回路都是简单回路 答案：D 4．下列数组中，不能构成无向图的度数列的数组是( )． (A) (1,1,1,2,3) (B) (1,2,3,4,5) (C) (2,2,2,2,2) (D) (1,3,3,3)答案：B 5．下列数组能构成简单图的是( )． (A) (0,1,2,3) (B) (2,3,3,3) (C) (3,3,3,3) (D) (4,2,3,3) 答案：C 6．无向完全图K3的不同构的生成子图的个数为（）． (A) 6 (B) 5 (C) 4 (D) 3 答案：C 7．n阶无向完全图K n中的边数为（）． (A) 2)1 (+ n n (B) 2)1 (- n n (C) n (D)n(n+1) 答案：B 8．以下命题正确的是( )． (A) n (n1)阶完全图K n都是欧拉图 (B) n(n 1)阶完全图K n都是哈密顿图 (C) 连通且满足m=n－1的图
数学建模中常见的十大 模型 Document serial number【KKGB-LBS98YT-BS8CB-BSUT-BST108】
数学建模常用的十大算法==转 (2011-07-24 16:13:14) 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MATLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。
8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。
第二章 图的连通性 连通图：任二顶点间有路相连。 例 可见在连通图中，连通的程度也是有高有低。 本章的目的就是定义一种参数来度量连通图连通程度的高低。 §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 ===?=?，
按模型的数学方法分： 几何模型、图论模型、微分方程模型、概率模型、最优控制模型、规划论模型、马氏链模型等 按模型的特征分： 静态模型和动态模型，确定性模型和随机模型，离散模型和连续性模型，线性模型和非线性模型等 按模型的应用领域分： 人口模型、交通模型、经济模型、生态模型、资源模型、环境模型等。 按建模的目的分： 预测模型、优化模型、决策模型、控制模型等 一般研究数学建模论文的时候，是按照建模的目的去分类的，并且是算法往往也和建模的目的对应 按对模型结构的了解程度分： 有白箱模型、灰箱模型、黑箱模型等 比赛尽量避免使用，黑箱模型、灰箱模型，以及一些主观性模型。 按比赛命题方向分： 国赛一般是离散模型和连续模型各一个，2016美赛六个题目（离散、连续、运筹学/复杂网络、大数据、环境科学、政策） 数学建模十大算法 1、蒙特卡罗算法 （该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，比较好用的算法） 2、数据拟合、参数估计、插值等数据处理算法 （比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具）
3、线性规划、整数规划、多元规划、二次规划等规划类问题 （建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法 （这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法 （这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法 （这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法 （当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法 （很多问题都是从实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法 （如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）10、图象处理算法 （赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的这些图形如何展示，以及如何处理就是需要解决的问题，通常使用Matlab进行处理） 算法简介 1、灰色预测模型（必掌握）
各种图论模型及其解答 摘要： 本文用另一种思路重新组织《图论及其应用》相关知识。首先，用通俗化语言阐述了如何对事物间联系的问题进行图论建模；接着从现实例子出发，给出各种典型图论模型，每种图论模型对应于图论一个重要内容；再者，介绍相关知识对上述提到的图论模型涉及的问题进行解答；最后，补充一些图论其他知识，包括图论分支、易混概念。 符号约定： Q(Question)表示对问题描述，M(Modeling)表示数学建模过程，A(Answer)表示原问题转化为何种图论问题。 一、引言 图论是研究点、线间关系的一门学科，属于应用数学的一部分。现实生活中，凡是涉及到事物间的关系，都可以抽象为图论模型。点表示事物，连线表示事物间的联系。整个求解过程如下： 原问题——>图论建模——>运用图论相关理论求解——>转化为原问题的解 整个过程关键在于图论建模，所谓图论建模，就是明确点表示什么，连线表示什么，原问题转化为图论中的什么问题。存在以下两种情况： ①若事物间联系是可逆的(比如双行道，朋友)，则抽象成无向图 ②若事物间联系是不可逆的(比如单行道，状态转化不可逆)，则抽象成有向图 如果需要进一步刻画事物间的联系（比如城市间的距离），就给连线赋一个权值，从而抽象成赋值图。 综上，根据实际问题，可建模成下列图论模型的一种：无向赋权图、有向赋权图、无向非赋权图、有向非赋权图。 例1.宴会定理：任何一宴会中，一定存在两个人有相同的数量朋友M：点表示人，连线表示当且仅当该两个人是朋友 A：问题转化为任何一个图一定存在两个顶点的度相等 二、图论模型 接下来介绍若干典型的图论模型，每种模型几乎对应于图论的一个重要内容，这些内容将在第三章进行讨论，也就给出了这些模型的解答思路。 2.1 偶图模型 凡涉及两类事物间的联系（即只考虑两类事物间的联系，而不考虑同类事物间的联系），均可抽象成偶图模型。作图时，将两类事物分成两行或者两列。这
第七章 平面图 §7.1 平面图的概念 定义7.1.1 如果图G 能画在曲面S 上，使得任意两边互不交叉，则称G 可嵌入曲面S 。若图G 可嵌入平面，则称G 是可平面图或平面图，画出的无交叉边的图形称为图G 的平面嵌入。 例如，下面是三个平面图及其平面嵌入。 根据定义，下列定理是显然的。 定理7.1.1 若图G 是平面图，则G 的任何子图都是平面图。 定理7.1.2 若图G 是非平面图，则G 的任何母图都是非平面图。 定理7.1.3 若图G 是平面图, 则在G 中添加重边或环边后所得之图仍是平面图。 注：由以上定理知 (1) K n ( n ≤4 ) 和 K 1,n (n ≥ 1)及其所有子图都是平面图。 (2) 环边和重边不影响图的平面性。故以下讨论平面性时总假定图G 是简单图。 定义7.1.2 设图G 是平面图 (已平面嵌入)，G 的边将平面划分出的若干区域都称为图G 的面。其中面积无限的面称为无限面或外部面，面积有限的面称为有限面或内部面。包围一个面的所有边称为该面的边界。一个面边界上的边数称为该面的次数 (割边按两次计)，面R 的次数记为deg (R )。 定理7.1.4 平面图G 中所有面的次数之和等于G 的边数的两倍，即 其中R 1, R 2, … , R r 是G 的所有面。 证明： 对G 的任何一条边e ，若e 是两个面 R i 和 R j 的公共边界，则在计算R i 和 R j 的次数时，e 各提供了1；若e 只是某一个面的边界，则在计算该面的次数时，e 提供了2。可见每条边在计算总次数时，都提供2。因而结论成立。 1 deg()2().r i i R G ε==∑