第六章图论方法
【引例1】K?nigsberg七桥问题
在K?nigsberg城郊的Pregerl河上有两个小岛，小岛和河两岸
的陆地由7座桥相连（如图a），问题是如何从河岸或岛上的某
一个位置出发，能否经过7座桥正好各一次，最后回到出发地。
将图抽象，用4个点代表4个被河隔开的陆地（两岸和岛屿），把桥表示为连接两个陆地之间的边，则得到图b所示的图，从而问题变为如何从图中的某个点出发，经过所有的边正好一次，最后回到这个点。
【引例2】
某河流中有几个岛屿，从两岸至各岛屿及岛屿之间的桥梁如图。在一次军事行动中，问至少炸断几座桥，才能完全切断A 与F 的交通联系？
A
D
B
C
D
E F
A
F
D
E
C
B 213
1
2
1
2
11
§6.1图的基本概念与模型
图是反映研究对象之间相互关系的一种工具。是在纸上用点和线画出的各种各样的示意图。
太原
石家庄
保定
灵丘
原平
天津
塘沽
通县
秦皇岛
密云
承德
北京
张家口
怀柔
甲
乙
丙
丁
戊
图的最基本的要素是点以及点与点之间的一些连线，点表示我们要研究的对象，线表示对象之间的某种特定关系。
如图中点和线赋与具体的含义和权重，称为网络图。
边：若点与点之间的连线没有方向，称为边。如e 1=[v 1, v 2], v 1, v 2称为e 1的
端点，e 1称为v 1,v 2的关联边，v 1,v 2称为点相邻，e 1,e 2称为边相邻
v 1e 1v 2
v 3
v 4
v 5
v 6
e 2e 3
e 4e 5
e 6
e 7
e 8
e 9e 10
环：如果边的两个端点相重，称该边为环，如e 10；如果两个端点之间的边多于一条, 称为具有多重边，如[v 2, v 4] ,无环，无多重边的图为简单图。
甲
乙
丙
丁
戊
弧：若点与点之间的连线有方向，称为弧，由此构成的图为有向图。
圈：若起始点和终点是同一个点的链称为圈。例如(v1 ,e1 ,v2 ,
e2 ,v4 ,e3 ,v3 ,e4 ,v1 )。
v 1e 1v 2
v 3
v 4
v 5v 6e 2
e 3
e 4e 5
e 6
e 7
e 8
e 9e 10
链：是一个点、边交错序列, 如（v 1 ,e 1 ,v 2 ,e 2 ,v 4 )
路：如果链中每个项点都不相同, 则称为路，如（v 1 ,e 1 ,v 2 ,e 2 ,v 4 )
回路：若起始点和终点是同一个点的路称为回路。
连通图：一个图中，任意两个顶点至少存在一条链，则称这样的图为连通图。否则称为不连通的。
v 1v 2
v 3v 4v 5
v 6
e 2e 4e 5
e 6
e 7
e 8
e 1e 3
v 7v 8
e 9
e 10
v 1v 2
v 3
v 4
v 5
v 6
e 2e 4
e 5e 6e 7e 1e 3悬挂节点:次为1的点称为悬挂节点:
次：与一个点相关联的边的数目称为次, 如v 1 的次为2，v 5的次为3，次为奇数的点称为奇点，次为偶数的点称为偶点，次为0的点称为孤立点，如v 6
利用图可以对象之间的关系
例：有甲、乙、丙、丁、戊、己六名运动员参加A、B、C、D、E、F六个项目的比赛。打对号的是各运动员参加比赛的项目，问六个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。
A
B
C D
E
F
A B C D E F
甲√√√
乙√√√
丙√√
丁√√
戊√√√
己 √√√
A C
B F E D
§6.2 树图和图的最小部分树
一、树的性质
树：一个无圈的连通图称为树。
例如
性质1：任何树至少有一个悬挂节点
性质2：具有n个顶点的树的边恰好为(n-1)条
性质3：任何具有n个顶点、(n-1)条边的连通图是树图。
树图的任意两个点之间有一条且仅有一条唯一的通路，是最脆弱的连通图
例：树的形成
已知在五个城市间架设电话线，要求任何两个城市都可以通话（允许通过其它城市），并且电话线的条数最少。
方案一不连通方案三方案二有圈
树
问题：如何构建才能是最短路径的树—最小枝权树问题
v 1
v 2
v 3
v 4
v 5
v 1
v 2
v 3
v 4
v 5v 1
v 2
v 3
v 4
v 5
v 1
v 2v 3
v 4
v 5
接上节、求最小树杈问题
最小树杈问题是关于在一个网络中，从一个起点出发到所有点，找出一条或几条路线，以使在这样一些路线中所采用的全部支线的总长度是最小的，或铺设费用最少。求图的最小树杈问题的方法有“破圈法”和“避圈法”。破圈法v 1v 2
v 3
v 5e 2
e 3e 5e 1
e 6e 7e 8
e 4v 4v 1v 2e 1
v 3
e
2
e 4v 4v 5
e 6避圈法
破圈法(克鲁斯喀尔法)
例：已知连接五个城市的公交线路图，在要在五个城市间架设电话线，为了便于维修要求电话线必须沿公路架设，并且电话线总长度最小。
此为最小树杈
v1
v2
v3v4 v5
25 20
10
9
1512
30
破圈法：任选一个圈，从圈中去掉杈最大的一条边。在余下的图中重复这个步骤，直到得到一连通的不含圈的图为止。
最小线路长度为：
20+15+10+9=54
避圈法(普赖姆法)
避圈法：从任意一个节点开始，选一条杈较小的边连接，以后每一步中，总从未被选取的边中选一条杈尽可能小，且与已选边不构成圈的边。
此为最小树杈，最小线路长度为54
v 1
v 2
v 3
v 4
v 5
25
20
10
9
15
12
30
又例
在住宅小区安装供水管道。求最小线路。
1.供水管道的阀门
2
7
3
5
4
6
300
700
10002001100
900
600
100500400
600
破圈法(克鲁斯喀尔法)
1.供水管道的阀门
2
7
3
5
46
300
2001100
900
100500
400
11001000700
600
600
此为最小树杈，最小线路长度为2400
避圈法(普赖姆法)
1.供水管道的阀门
300
700
1000
200
1100
900
600
100
500
400
600
3
4
5
6
7
2
此为最小树杈，最小线路长度为2400
练习：求最小树杈
65
51
7
2
3
4
4v 1
v 2
v 3v 4
v 5
v 6
6
55172
3
4
4v 1
v 2
v 3v 4
v 5
v 6
此为最小树杈，最小线路长度为15
v 3
v 2
1v 4
2
v 5
3v 6
4v 1
5
655
1
7
2
3
4
4
v 1
v 2
v 3v 4
v 5
v 6
此为最小树杈，最小线路长度为15
练习：求最小树杈
2
5
3
12
2
3
4
533
2
32
2
2
§6.3 最短线路问题
当通过网络的各边所需时间、距离或费用为已知时，找出从入口到出口所需的最少时间、最短距离或最少费用的路径问题，称做网络的路线问题。
100
300
9-106-9-10500
4-6-9-10650
1-4-6-9-10150
8-10375
7-8-10400
5-8-10600
2-6-9-10
600
3-5-8-102
8
5
6
100400350
275
175
250
1
150175
225
150
100
200
300
200
275
200
4
9
10
最短路线为650
一、起点到终点的最短距离
本节主要介绍从起点到终点的最短路线问题。方法以是从终点
开始逐步逆向推算
070105运筹学与控制论 一、专业介绍 1、学科简介 运筹学与控制论是研究各种系统的结构、运作、设计和调控的现代数学学科，是应用数学与系统科学、信息科学的结合点。运筹学与控制论是数学的二级学科，本学科所研究的问题是从众多的可行方案中优选某些目标最优的方案，在社会与经济生活的合理规划、最优设计、最优控制和科学管理中起着十分重要的作用。在自然科学、社会经济中有广泛的应用。 2、培养目标 在政治上培养学生有坚定的政治方向，热爱祖国，坚持四项基本原则，具有全心全意为人民服务的思想。在业务上系统掌握本专业的基本理论，在所研究方向上了解国内外学术动态，具有一定的独立开展科研的能力，并能熟练地运用一门外语阅读专业书刊和撰写论文，成为德、智、体全面发展的运筹学与控制论专业的高级人才。 3、专业方向 01 最优控制理论及其应用 02 随机控制理论与数学金融 4、考试科目 ①101思想政治理论②201英语一③719分析④835代数与几何 (注：各个学校专业方向、考试科目有所不同，以上以复旦大学数学科学学院大学为例) 二、就业前景 1.运筹学 该学科已被广泛应用于工商企业、军事部门、民政事业等研究组织内的统筹协调问题，故其应用不受行业、部门之限制; 运筹学既对各种经营进行创造性的科学研究，又涉及到组织的实际管理问题，它具有很强的实践性，最终应能向决策者提供建设性意见，并应收到实效; 它以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突。对所研究的问题求出最优解，寻求最佳的行动方案，所以它也可看成是一门优化技术，提供的是解决各类问题的优化方法。运筹学已被应用到各种管理工程中，在现代化建设中发挥着重要作用。因此运筹学是很有前景的，今后也可以转管理方向。 2. 控制论 随着自动化水平的不断提高，控制系统本身也日渐复杂，系统中的控制变量数也随之增多，对控制性能的要求也逐步提高，很多情况都要求系统的性能是最优的，如时间最短，误差最小、燃料最省、产量最高、成本最低、效益最大等，而且要求对环境的变化有较强的适应能力，但现在所依据的稳定性、快速性和准确性等设计指标难以满足新的控制要求。所以现在社会对控制人才的要求也越来越高，该专业的毕业生就业前景也是很好的。 三、就业方向 学生毕业后能在科研、教育等部门从事学术研究、技术管理、教学工作，以及在生产、设计、开发等企事业单位从事应用技术研究和管理决策等工作。 四、推荐院校 山东大学、复旦大学、上海大学、浙江大学、大连理工大学、南开大学、重庆大学、四川大学、北京交通大学、清华大学、西安交通大学、哈尔滨工业大学、东北大学、华东师范大学、中国科学技术大学 五、相近专业 相同一级学科下的其他专业有：基础数学、计算数学、概率论与数理统计、应用数学。 六、课程设置(以华东师范大学为例) (一)必修课程 1. 学位公共课 政治理论、外国语、计算机应用、专业外语、教育实习或专业实习; 2. 学位基础课
1、略 2、计算有向无圈图的根 输入一个有向无圈图DAG，计算和输出DAG的根r（即r到其他任何顶点都有一条路。若图中没有根，则输出“not found”）。 输入：顶点数n和边数e;以下为e行，每行为一条有向边的两个端点 输出：根r或者“not found” 算法分析 设 const mx=100;{顶点数的上限} var n,e,i,j,k,a,b:integer;{ 顶点数n、边数e} g:array[1..mx,1..mx]of boolean;{传递闭包} bn:boolean;{根存在标志} 1、输入信息，计算传递闭包 readln(n,e);{输入顶点数和边数} fillchar(g,sizeof(g),0);{ 有向无圈图初始化} for i:=1 to e do{输入信息，构造传递闭包的初始值} begin readln(a,b);g[a,b]:=true end; for k:=1 to n do{计算传递闭包} for i:=1 to n do for j:=1 to n do if g[i,j] or g[i,k] and g[k,j]then g[i,j]:=true; 2、计算DAG的根 然后枚举每一个顶点。根据传递闭包的信息，若当前顶点至其它所有顶点有路，则判定该顶点即为根。若没有一个顶点可作为DAG的根，则输出失败信息 for i:=1 to n do{枚举每一个可能的根} begin bn:=true;{设定I至其他所有顶点有路的标志} for j:=1 to n do{若I至任一个顶点无路，则返回bn为false} if (i<>j) and not g[i,j] then begin bn:=false; break end; if bn then break{若I至其他所有顶点有路，则输出根i} end; if bn then writeln(i) else writeln('not found'){若不存在根，则输出失败信息}
运筹学（yùnchóuxué）简介 英语全称为：Operational?Research(英国)或者是Operations?Research(美国) 在中国战国时期，曾经有过一次流传后世的赛马比赛，相信大家都知道，这就是田忌赛马。田忌赛马的故事说明在已有的条件下，经过筹划、安排，选择一个最好的方案，就会取得最好的效果。可见，筹划安排是十分重要的。 现在普遍认为，运筹学是近代应用数学的一个分支，主要是将生产、管理等事件中出现的一些带有普遍性的运筹问题加以提炼，然后利用数学方法进行解决。前者提供模型，后者提供理论和方法。 运筹学的思想在古代就已经产生了。敌我双方交战，要克敌制胜就要在了解双方情况的基础上，做出最优的对付敌人的方法，这就是“运筹帷幄之中，决胜千里之外”的说法。 但是作为一门数学学科，用纯数学的方法来解决最优方法的选择安排，却是晚多了。也可以说，运筹学是在二十世纪四十年代才开始兴起的一门分支。 运筹学主要研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。当然，随着客观实际的发展，运筹学的许多内容不但研究经济和军事活动，有些已经深入到日常生活当中去了。运筹学可以根据问题的要求，通过数学上的分析、运算，得出各种各样的结果，最后提出综合性的合理安排，已达到最好的效果。 运筹学作为一门用来解决实际问题的学科，在处理千差万别的各种问题时，一般有以下几个步骤：确定目标、制定方案、建立模型、制定解法。 虽然不大可能存在能处理及其广泛对象的运筹学，但是在运筹学的发展过程中还是形成了某些抽象模型，并能应用解决较广泛的实际问题。 随着科学技术和生产的发展，运筹学已渗入很多领域里，发挥了越来越重要的作用。运筹学本身也在不断发展，现在已经是一个包括好几个分支的数学部门了。比如：数学规划（又包含线性规划；非线性规划；整数规划；组合规划等）、图论、网络流、决策分析、排队论、可靠性数学理论、库存论、对策论、搜索论、模拟等等。 运筹学有广阔的应用领域，它已渗透到诸如服务、库存、搜索、人口、对抗、控制、时间表、资源分配、厂址定位、能源、设计、生产、可靠性、等各个方面。 运筹学是软科学中“硬度”较大的一门学科，兼有逻辑的数学和数学的逻辑的性质，是系统工程学和现代管理科学中的一种基础理论和不可缺少的方法、手段和工具。运筹学已被应用到各种管理工程中，在现代化建设中发挥着重要作用。 [编辑本段]运筹学的历史 运筹学作为一门现代科学，是在第二次世界大战期间首先在英美两国发展起来的，有的学者把运筹学描述为就组织系统的各种经营作出决策的科学手段。?P.M.Morse与G.E.Kimball在他们的奠基作中给运筹学下的定义是：“运筹学是在实行管理的领域，运用数学方法，对需要进行管理的问题统筹规划，作出决策的一门应用科学。”运筹学的另一位创始人定义运筹学是：“管理系统的人为了获得关于系统运行的最优解而必须使用的一种科学方法。”它使用许多数学工具（包括概率统计、数理分析、线性代数等）和逻辑判断方法，来研究系统中人、财、物的组织管理、筹划调度等问题，以期发挥最大效益。 现代运筹学的起源可以追溯到几十年前，在某些组织的管理中最先试用科学手段的时候。可是，现在普遍认为，运筹学的活动是从二次世界大战初期的军事任务开始的。当时迫切需要把各项稀少的资源以有效的方式分配给各种不同的军事经营及在每一经营内的各项活动，所以美国及随后美国的军事管理当局都号召大批科学家运用科学手段来处理战略与战术问题，实际上这便是要求他们对种种（军事）经营进行研究，这些科学家小组正是最早的运筹小组。 第二次世界大战期间，“OR”成功地解决了许多重要作战问题，显示了科学的巨大物质威力，为“OR”后来的发展铺平了道路。
第5章 运筹学模型 5.2 图论模型 图论是运筹学的一个重要分支，它是建立和处理离散类数学模型的一个重要工具。用图论的方法往往能帮助人们解决一些用其它方法难于解决的问题。图论的发展可以追溯到1736年欧拉所发表的一篇关于解决著名的“哥尼斯堡七桥问题”的论文。由于这种数学模型和方法直观形象，富有启发性和趣味性，深受人们的青睐。到目前为止，已被广泛地应用于系统工程、通讯工程、计算机科学及经济领域。传统的物理、化学、生命科学也越来越广泛地使用了图论模型方法。本章将在介绍图的一些基本概念的基础上，着重介绍最小生成树、最短路、最大流及最小费用最大流问题。 5.2.1 图的基本概念 城市之间的交通关系，家族成员之间的关系，工厂、企业、事业单位内部，部门之间的上下关系，工程中各个工序之间的先后关系等等，用图形来描述往往是很有益的。图论是研究某种特定关系的一门学问。 1.图 图 (graph) 由若干个点 (称作顶点，vertex) 和若干条连接两两顶点的线段（称edge ）组成。通常，顶点可用来表示某一事物，边用来表示这些事之间的某种关系。如图5-1中的五个顶点可以代表五个城市。如果两个顶点之间有一条边连接，就表示这两个城市之间有一条铁路。同样，它也可以代表五个人。如果两个人认识，则用一条边把这两个顶点连接 起来。 图5-1 由于图是用来表示某些事物之间的联系，因而在画图时，顶点位置，边的长短、曲直是无关紧要的。只要两个图的顶点可以一一对应，并且 使得对应的顶点之间是否有边相连完全相同，就可以认为是同一个图。例如：图5-1也可以画成图5-2的形式。 图 5-2 设图的顶点集合V ={n v v v ,...,, 21}, 边的集合 E ={m e e e , ... ,,21} 把图记作 ) , (E V G =。这里大括号 { } 内的元素是没有顺序的，而小括号（ ）内的元素是有顺序 的。如果边e 连接顶点u 和v ，则记作e = {v u ,}。u 和v 称作e 的端点，e 称作u 和v 的关联边。如果u 和v 之间有一条边，即{v u ,}∈E ，则称u 和v 相邻。如果两条边有一个共同的端点，则称这两条边相邻。没有关联边的顶点称作孤立点。两个顶点之间可以有不止一条
图论基本知识 对于网络的研究，最早是从数学家开始的，其基本的理论就是图 论，它也是目前组合数学领域最活跃的分支。我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的……这些都可以用图论的语言和符号精确简洁地描述。图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。考虑到物理学家对于图论这一领域比较陌生，我在此专辟一章介绍图论的基本知识，同时将在后面的章节中不加说明地使用本章定义过的符号。进一步研究所需要的更深入的图论知识，请参考相关文献[1-5]。 本章只给出非平凡的定理的证明，过于简单直观的定理的证明将 留给读者。个别定理涉及到非常深入的数学知识和繁复的证明，我们将列出相关参考文献并略去证明过程。对于图论知识比较熟悉的读者可以直接跳过此章，不影响整体阅读。 图的基本概念 图G 是指两个集合(V ，E)，其中集合E 是集合V×V 的一个子集。 集合V 称为图的顶点集，往往被用来代表实际系统中的个体，集合E 被称为图的边集，多用于表示实际系统中个体之间的关系或相互作用。若{,}x y E ，就称图G 中有一条从x 到y 的弧（有向边），记为x→
y ，其中顶点x 叫做弧的起点，顶点y 叫做弧的终点。根据定义，从任意顶点x 到y 至多只有一条弧，这是因为如果两个顶点有多种需要区分的关系或相互作用，我们总是乐意在多个图中分别表示，从而不至于因为这种复杂的关系而给解析分析带来困难。如果再假设图G 中不含自己到自己的弧，我们就称图G 为简单图，或者更精确地叫做有向简单图。以后如果没有特殊的说明，所有出现的图都是简单图。记G 中顶点数为()||G V ν=，边数为()||G E ε=，分别叫做图G 的阶和规模，显然有()()(()1)G G G ενν≤-。图2.1a 给出了一个计算机分级网络的示意图，及其表示为顶点集和边集的形式。 图2.1：网络拓扑结构示意图。图a 是10阶有向图，顶点集为 {1,2,3,4,5,6,7,8,9,10}，边集为{1→2,1→3,1→4,2→5,2→6,2→7,3→6,4→7,4→8,6→9,7→9,8→10}；图b 是6阶无向图，顶点集为{1,2,3,4,5,6}，边集为{13,14,15,23,24,26,36,56}。 从定义中可以看到，从任意顶点x 到y 不能连接两条或以上 边，本文所讨论的图，均符合上述要求，既均为不含多重边的图。如
【图论基础】求连通子图的个数 Time Limit:10000MS Memory Limit:65536K Total Submit:42 Accepted:30 Description 求一个无向图中连通子图的个数。 Input 第一行一个数n，表示无向图的顶点的数量（n<=5000），接下来从第2行到第n+1行，每行有n个数（1表示相应点有直接通路，0表示无直接通路），形成一个n*n的矩阵，用以表示这个无向图。示例： Output 输出一个数，表示这个图含有连通子图的个数。 Sample Input 5 1 0 1 0 0 0 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 1 Sample Output 自己算吧！ Source
?var ? i,j,n,ans,x:longint; ? a:array[1..5000,0..5000] of longint; ? b:array[1..5000] of boolean; ?procedure dfs(x:longint); ?var i:longint; ?begin ? b[x]:=false; ? for i:=1 to a[x,0] do if b[a[x,i]] then ? dfs(a[x,i]); ?end; ? ?begin ? readln(n); ? for i:=1 to n do ? for j:=1 to n do begin ? read(x); ? if x=1 then begin ? inc(a[i,0]); a[i,a[i,0]]:=j; ? end; ? end; ? fillchar(b,sizeof(b),true); ? for i:=1 to n do if b[i] then begin ? inc(ans); ? dfs(i); ? end; ? writeln(ans); ?end.
工商管理中的运筹学问题—建模及求解 项目报告 姓名： 课题组的分工或贡献： 课程名称：运筹学 指导教师： 2019年6月
前言 工商管理中的运筹学问题—建模及求解项目报告主要内容为（1）运输问题建模与管理运筹学软件求解及分析；（2）目标规划问题建模与管理运筹学软件求解及分析；（3）整数规划问题建模与管理运筹学软件求解及分析；（4）图论问题与管理运筹学软件求解及分析。范围为运筹学第五版教程中的线性规划、运输问题、目标规划、整数规划和图论等章节。本次项目的实施旨在更好的了解运筹学的理论，学会将运筹学的各种方法应用到实际问题中去，做到学以致用。
4.1研究内容 图论最吸引人的特色是它蕴含着大量有趣的思想、漂亮的图形和巧妙的方法，使非常困难的问题也易于表达。最短路问题是图与网络知识中的经典问题之一，生活中如选址、石油运输管道铺设时的选线、设备更新等问题，都可以归结为最短路问题。此外，图论问题中还包括最大流问题和网络计划问题等。 4.2问题描述 石油管道铺设最优方案的选择问题: 如下图所示，其中v1为出发点，v10为目的地，v2、v3、v4、v5、v6、v7、v8、v9分别为可供选择的各站站点，图中的线段表示管道可铺设的位置，线段旁的数字为铺设管线所需要的费用，问如何铺设管道线路才使总费用最小? 图中各点之间的距离如下: ( 1) V1—V2：3、V1—V3∶5、V1—V4∶4; ( 2) V2—V5∶6、V2—V6∶3、V2—V7∶5、V3—V5∶3、V3-V6∶2、V3-V7∶4、V4-V5∶4、V4— V6∶1、V4—V7∶5； ( 3) V5—V8∶2、V5—V9∶5、V6—V8∶7、V6— V9∶4、V7—V8∶5、V7—V9∶4； ( 4) V8—V10∶3、V9—V10∶4. 4.3求解步骤（Dijkstra 算法） 4.3.1.给v s以P标号，P(v s)=0，其余各点均给T标号，T（v s）=+∞。 4.3.2.若v i点为刚得到P标号的点，考虑这样的点v j:(v i，v j)属于E，且v j为T标号点。 对v j的T标号点进行以下的修改：T（v j）=min[T（v j）,P（v j）+l ij]. 4.3.3.比较所有具有T标号的点，把最小的改为P标号，即P（v i'）=min[T（v i）]， 当存在两个以上最小者时，可同时改为P标号。若全部点均为P标号则停止。否则 用v i'代替v i转回4.3.2。
基本知识点： 一、图的基本定义： 平凡图：只有一个顶点无边的图。 非平凡图：其他所有图。 空图：边集合为空的图。 简单图：既没有环也没有重边的图。 复合图：其他所有的图。 同构图：顶点集合之间存在双射（一一对应关系），对应边重数和端点对应相等。 标定图：给图的点和边标上符号。非标定图：不标号。非标定图代表一类相互 同构的图。 完全图：每两个不同顶点之间都有一条边相连的简单图。N 个顶点的完全图只有一个，记为n K 。 偶图（二部图）：具有二分类(,)X Y 的图，他的点集可以分解为两个（非空）子集X 和Y ，使得每条边的一个端点在X 中，另一个端点在Y 中。 完全偶图 ：指具有二分类(,)X Y 的简单偶图，其中X 的每个顶点与Y 的每个顶点相连。若,X m Y n ==，则这样额完全偶图记为：,m n K 。 k —正则图：设(,)G V E =为简单图，如果对所有的结点v V ∈，有()d v k =，称G 为k —正则图。 完全图和完全偶图,n n K 均是正则图。 图划分：若一个n 阶简单图G 各点的度为i d ，则分正整数k 为n 个部分的划分i d ∑称为是图划分。 子图：边集合和点集合均是原图的子集，且待判定图中的边的重数不超过原图中对应的边的重数。 生成子图：点集合相等，边集合为原图子集的图。 导出子图：由顶点集为原图G 真子集的所有点，及两端点均在该集合中的边的全体组成的 子图V ‘。 '[]G V 和G v -。 边导出子图：由原图G 边的真子集，该图中边的断点全体为顶点组成的子图E ‘。 ' []G E 和{}G e -。 图的运算： 并，交，差，对称差，联图，积图，合成图，极图 路与图的联通性： 途径： 迹：边互不相同的途径。 路：边和点都互不相同的途径。 连通的：两个顶点之间存在路。 连通图：每一对顶点之间都有一条路。
第六章习题图论基础 6.1下列各组数中，那些能构成无向图的度数列？那些能构成无向简单图的度数列？ （1）1，1，1，2.3 (2)2, 2, 2, 2 , 2 (3)1,2,3,4,5 (4)1,3,3,3 6.2设有向简单图D的度数为2，2，3，3，入度列0，0，2，3，试求D的除度列。 6.3设是4阶有向简单图，度数列为3，3，3，3.它的入度列9或出度列）能为1，1，1，1 吗？ 6.4设( )为一正整数序列，互不相同，问此序列能构成n阶无向图的度数列吗？为什么？ 6.5下面无向图中有几个顶点？ （1）16条边，每个顶点都是2度顶点. （2）21条边，3个4度顶点，其余的都是3度顶点. （3）24条边，各顶点的度数是相同的. 6.6 35条边，每个顶点的度数至少为3的图最多有几个顶点? 6.7设n阶无向简单图中，（G）=n-1，问（G）应为多少？ 6.8一个n（n２）阶无向简单图Ｇ中，ｎ为奇数，已知Ｇ中有ｒ各奇度顶点，问Ｇ的补图中有几个奇度顶点？ 6.9设Ｄ是ｎ阶有向简单图，是Ｄ的子图，已知的边数＝ｎ（ｎ－１），问Ｄ的边数ｍ为多少？ 6.10画出－－－的所有非同构的子图，其中有几个是子图？生成子图中有几个是连通图？ 6.11设Ｇ为ｎ阶简单图（无向图或有向图），－－为Ｇ的补图，若Ｇ－－－－，则称Ｇ为自补图，――的生成子图中有几个非同构的自补图？ 6.12．设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G 中至少有几个顶点？在最少顶点的情况下，写出G的度数列、Δ(G)、δ(G). 6.13．设n阶图G中有m条边，证明：δ(G)≤2m/n≤Δ(G). 6.14．设无向图中有6条边，3度与5度顶点各一个，其余的都是2度顶点，问该图有 几个顶点？ 6.15．证明空间中不可能存在有奇数个面且每个面都有奇数条棱的多面体。 6.16．阶2-正则图有几种非同构的情况？ 6.17．设n阶无向图为3-正则图，且边数m与n满足2n-3=m，问这样的无向图有几种非同构的情况？ 6.18画出３阶有完全图所有非同构的子图，问其中有几个是生成子图？生成子图中有几个是自补图？ 6.19设－－－－均为４阶无向简单图，他们均由两条边，他们能彼此均非同构吗？为什莫？ 6.20已知ｎ阶无向图Ｇ中有ｍ条边，各顶点的度数均为３，又已知２ｎ－３＝ｍ，问在同构的意义下，Ｇ是唯一的吗？又若Ｇ为简单时，是否唯一？ 6.22在－－的边上涂上红色或蓝色，证明对于任意一种随意的涂法，总存在红色――或蓝色――？
图与网络模型及方法 §1 概论 图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷22 n n H C 的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈，近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。 图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点。当 然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决 这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。 图与网络是运筹学（Operations Research ）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。 我们首先通过一些例子来了解网络优化问题。 例1 最短路问题（SPP －shortest path problem ） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 例2 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两