5经典图论问题
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
5.3旅行推销员问题（TSP，货郎担问题）（NPC问题）
定义：包含图G的所有定点的路（圈）称为哈密顿路（圈），含有哈密顿圈得图称为哈密顿图。
分析：从一个哈密顿圈出发，
算法一：（哈密顿圈的充要条件：一包含所有顶点的连通子图，二每个顶点度数为2）
象求最小生成树一样，从最小权边加边，顶点度数大于3以及形成小回路的边去掉。
算法二：
算法三：
示例：设旅行推销员的矩阵为????
??
? ??01086100111281101565150
规划模型：
先将一般加权连通图转化成一个等价的加权完全图，设当从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,
不含子巡回的约束也可以用如下条件表示：
0,,,2,1;1≥≠==-≤++j i ij j i u u j i n j n i n nx u u
5.4 排课表问题 问题一
Step1：取权数最小的四条边，权和29，不合理（v 4度数为3）但为下界，分两枝保留或去掉（v1，v4）
Step2：去掉（v1，v4）后取权最小的四条边
边色数:给图的边着色，相邻边着不同的颜色，则每条边都着上颜色而且最少的颜色数称为边色数，对于排课表问题来说，一种颜色表示可以在同一时间段同时上课的情况。 定理：最小边色数()G χ'等于最大顶点度数()G ?。
以下加边循环算法为多项式时间算法：就是加边让每个顶点的度数一样（为最大度数），然后求一组完美匹配M ，着同样颜色，然后从图中去掉M 中的边,再求第二组完美匹配。。。。。。。。
问题二：
基本思想是：由给定的教室数与总课时数确定教学时间长度（即匹配数--色数），在没有考虑教室数限制所计算的匹配数基础上，增加空匹配至时间长度个，然后调节匹配边差大于1的匹配，直到满足要求。
5.5 几个小问题
会议安排问题
例如: 举行一个国际会议,有A, B, C, D, E,F,G 7个人。已知下列事实:
A 会讲英语;
B 会讲英语和汉语;
C 会讲英语、意大利语和俄语;
D 会讲日语和汉语;
E 会讲德语和意大利语;
F 会讲法语、日语和俄语;
G 会讲法语和德语。
试问这7个人应如何排座位, 才能使每个人都能和他身边的人交谈?
解答：那么我们用结点来代表人,于是结点集合V={A,B,C,D,E,F,G}对于任意的两点,若有共同语
言,就在它们之间连一条无向边,可得边集E,图G=(V,E), 如下图:
问题转化为在图中找到一条哈密顿回路的问题(哈密顿回路即是通过每个结点一次且仅一次的回路)。而A-B-D-F-G-E-C-A 即是图中的一条哈密顿回路。照这个顺序排座位就可以解决问题了。
过河问题
一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到河东.由于船小,一次只能带一物过
河，并且狼与羊,羊与菜不能独处.给出渡河方法.
解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0),共有
24 =16 种状态.在河东岸的状态类似记作.由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的,从而对应状态(1,0,0,1), (1,1,0,0), (1,0,0,0)也是不允许的.以可允许的10个状态向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图.根据此图便可找到渡河方法.
问题转化为求一点到另一点的路。
放置机器人
有一个N*M(N,M<=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。
模型一
以空地为顶点，有冲突的空地间连边，问题转化为最大独立点集。
模型二
我们将每一行，每一列被墙隔开，且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。我们把这些块编上号。同样，把竖直方向的块也编上号。
把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。于是，问题转化为二部图的最大匹配问题。
比较前面的两个模型：模型一过于简单，没有给问题的求解带来任何便利；模型二则充分抓住了问题的内
在联系，巧妙地建立了二部图模型。为什么会产生这种截然不同的结果呢？其一是由于对问题分析的角度不同：模型一以空地为点，模型二以空地为边；其二是由于对原型中要素的选取有差异：模型一对要素的选取不充分，模型二则保留了原型中“棋盘”这个重要的性质。由此可见，对要素的选取，是图论建模中至关重要的一步。
打猎
猎人要在n*n的格子里打鸟，他可以在某一行中打一枪，这样此行中的所有鸟都被打掉，也可以在某一列中打，这样此列中的所有鸟都打掉。问至少打几枪，才能打光所有的鸟？建图：二分图的X部为每一行，Y部为每一列，如果(i,j)有一只鸟，那么连接X部的i与
Y部的j。该二分图的最大匹配数则是最少要打的枪数。
设备更新问题
某企业使用一台设备,每年年初,企业都要作出决定,如果继续使用旧的,要付维修费；若购买一台新设备,要付购买费. 试制定一个5年更新计划,使总支出最少.
已知设备在每年年初的购买费分别为11,11, 12,12,13. 使用不同时间设备所需的维修费分别为5,6,8,11,18.
组合数学与图论复习题与参考答案
组合数学与图论复习题及答案 1．Show that if n+1 integers are chosen form the set {1,2, …,2n},then there are always two which differ by at most 2. 从{1,2, …,2n}中选出n+1个数，在这n+1个数中，一定存在两个数，其中一个整数能整除另外一个整数。 任何一个数都可以写成2k*L，其中k是非负数，L是正奇数。现在从1到2n 之间只有n个奇数。由于有n+1个数都能表示成2k*L，而L的取值只有n中，所以有鸽子洞原理知道，至少有两个数的L是一样的，于是对应k小的那个就可以整除k大的另一个数。 2．Show that for any given 52 integers there are exist two of them whose sum, or else difference, is divisible 100. 设52个整数a 1，a 2 ，…，a 52 被100除的余数分别是r 1 ,r 2 ,…,r 52 ，而任意一 个数被100除余数为0，1，2，…，99，一共100个。他们可以分为51个类{0},{1,99},{2,98},…,{49,51},{50}。将这51个集合视为鸽笼，则将 r 1,r 2 ,…,r 52 放入51个笼子中，至少有两个属于同一个笼子，所以要么有ri＝rj， 要么有ri＋rj＝100，也就是说ai－aj|100或者ai＋aj|100。 3．从1，2，3，…，2n中任选n+1个数，证明在这n+1个数中至少有一对数互质。 鸽子洞原理，必有两个数相邻，相邻的两个数互质 4．Prove that Ramsey number R(p,q)≤R(p,q-1)+R(p-1,q). 令N＝R(p,q-1)+R(p-1,q)，从N个人中中随意选取一个a，F表示与a相识的人，S表示与a不相识的人。 在剩下的R(p,q-1)+R(p-1,q)－2＋1个人中，由鸽子洞原理有，或者F中有R(p,q-1)人，或者S中有R(p-1,q)人。如果F中有R(p,q-1)人，则与a相识的人为p个；如果S中有R(p-1,q)人，则与a不相识的人有p个。所以有R(p,q)≤R(p,q-1)+R(p-1,q) 5．There are 10 people, either there are 3 each pair of whom are acquainted, or there are 4 each pair of whom are unacquainted。 从10人中随意选一个人p，F表示与p相识的人，S表示与p不相识的人若F中至少有4人，如果至少有4人不相识，则满足题设；如果有2人相识，则加上p有3人相识，也满足题设。 若F中至多有3人，则S中至少有6人，6人中至少有3人相识，或者不相识。如果相识则满足题设，如果不相识加上p不相识的人就有4个，也满足题设。6．In how many ways can six men and six ladies be seated at round table if the men and ladies to sit in alternate seats? 6个男的先进行圆排列，然后6个女的插入空位。 7．In how many ways can 15 people be seated at round table if B refuses to sit next to A? What if B only refuses to sit on A right?
经典图论问题
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以及形成小回路的边去掉。 算法二： 算法三：
图论与组合数学期末复习题含答案
组合数学部分 第1章 排列与组合 例1： 1)、求小于10000的含1的正整数的个数； 2、)求小于10000的含0的正整数的个数； 解：1)、小于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个 2)、“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含的规定，要特别留神。不含0的1位数有19个，2位数有29个，3位数有39个，4位数有49个 不含0小于10000的正整数有() ()73801919999954321=--=+++个含0小于10000的正整数9999－7380=2619个。 例2： 从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？ 解：将[1,300]分成3类： A={i|i ≡1(mod 3)}={1,4,7,…,298}, B={i|i ≡2(mod 3)}={2,5,8,…,299}, C={i|i ≡0(mod 3)}={3,6,9,…,300}. 要满足条件，有四种解法： 1)、3个数同属于A; 2)、3个数同属于B ； 3)、3个数同属于C; 4)、A,B,C 各取一数；故共有3C(100,3)+1003=485100+1000000=1485100。 例3：（Cayley 定理：过n 个有标志顶点的数的数目等于2-n n ） 1）、写出右图所对应的序列； 2）、写出序列22314所对应的序列； 解： 1）、按照叶子节点从小到大的顺序依次去掉节点（包含与此叶子 节点相连接的线），而与这个去掉的叶子节点相邻的另外一个点值则记入序列。如上图所示，先去掉最小的叶子节点②，与其相邻的点为⑤，然后去掉叶子节点③，与其相邻的点为①，直到只剩下两个节点相邻为止，则最终序列为51155.。 2）、首先依据给定序列写出（序列长度+2）个递增序列，即1234567，再将给出序列按从小到大顺序依次排列并插入递增序列得到：7。我们再将给出序列22314写在第一行，插入后的递增序列写在第二行。如下图第一行所示： ??→????? ??--②⑤67112223344522314??→???? ? ??--②⑥11223344672314 ??→????? ??--③②11233447314??→???? ? ??--①③11344714
组合数学及其图论试题库
组合数学及其图论 1、一个图G 是指一个有序三元组（V （G ），E （G ），G ?），其中G ?是：________________. 关联函数 2、 是有40个点的简单图且 中任两个点之间有且只有1条路，则 。 39 3、只有一个顶点所构成的图称为：________________ 平凡图 4、如果H 是G 的子图，其中V （H ）=V （G ）和E （G ）=E （H ）至少有一个不成立，就称H 是G 的：_____________. 真子图 5、设G 是p 阶简单图，则__________________等号成立当且仅当G 是完全图。 q(G)≤p(p-1)/2 6、如果一条途径的_________与___________相同，就称这条途径为闭途径。 起点 终点 7、如果对图G=（V ，E ）的任何两个顶点u 与v ，G 中存在一条（u-v ）路，则称G 是___________否则称为是______________ 连通图、 非连通图 8、设G 是P 阶连通图，则__________________. q(G)≥p-1 9、若二分图 有Hamilton 回路，则 与 满足 。 10、若G 是2-边连通图，则G 有强连通的________________. 定向图 11、边数最少的连通图是 。
树 12、没有回路的连通图称为_______________. 树 13、的图是图或图。 平凡图，不连通图 14、树T的每一个非悬挂点都是T的 __________. 割点 15、二分图中若与满足，则必有完美对集。 16、给定一个图G，如果图G的一个生成子图T是一棵树，则称T是G的一个_______________. 生成树 17、设G是无环图，e是G的一条边，则 τ(G)=___________________________. τ （G－e）+τ (G·e) 18、是阶简单图，则，等号成立当且仅当是图。 ，完全图 2、 19、___________________________的生成树称为最优生成树。 连通赋权图中具有最小权 20、的一个对集是最大对集的充要条件是。 中无可扩路 21、一个有向图D，如果略去每条弧的方向时所得无向图是一棵树，就称D为_____________________. 有向树 22、经过G的每条边的迹称为G的Euler迹，如果这条迹是闭的，则称这条闭迹为G的 ________________. Euler环游 23、是简单图且，则。
离散数学图论部分经典试题及答案
离散数学图论部分综合练习 一、单项选择题 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
图论与组合数学 教学大纲 2016 修改版
《图论与组合数学》教学大纲 一、课程名称：图论与组合数学 二、课程代码：021********* 三、课程英文名称：Graph Theory and Combinatorics 四、课程负责人：刘任任，肖芬，曹春红 五、学时与学分：48学时（理论40学时，实验8学时），3.0学分 六、课程性质：必修 七、适用专业：工科本科计算机科学与技术专业 八、选课对象：计算机科学与技术专业 九、预修课程：集合论与数理逻辑、C语言程序设计I、数据结构 十、课程教材与参考书目： 课程教材： 1.刘任任编著，《离散数学》，中国铁道出版社，2009年12月； 2.刘任任主编，《离散数学题解与分析》，中国铁道出版社，2010年10月。 参考书目： 1.Kneneth H. Rosen, Discete Mathematics and Its Applications, Fifth Edition,2003年； 2.Richard Johnsonbaugh, Discrete Mathematics, Prentice Hall Inc., 2000年； 3.Kolman B., etc., Discrete Mathematical Structures，Prentice Hall Inc., 2001； 4.Brualdi, R.A. (美)，组合数学(第四版)，北京机械工业出版社，2005年2月； 5.卢开澄，组合数学，清华大学出版社， 6.孙吉贵等编著，《离散数学》，高等教育出版社，2002年； 7.陈莉等编著，《离散数学》，高等教育出版社，2002年。 十一、开课单位：信息工程学院 十二、课程与能力培养中的对应关系 1、能力1.2: 掌握计算机科学与技术专业所要求的数学和自然科学基本知识，能将其用于计算机复杂工程问题的分析与建模； 2、能力2.1：掌握文献检索、资料查询的基本方法，能够运用现代技术获取相关文献，具有资料阅读和文献研究能力，并用于计算机科学与技术相关的复杂工程问题的分析和推理； 3、能力2.2：通过理论与实践相结合的系统学习，能够识别复杂工程问题中所涉及的数学、自然科学及计算机科学与技术专业的相关理论知识。 十三、课程的目标 图论和组合数学是现代数学的重要分支，是研究离散结构的存在、计数、分析和优化等问题的一门科学，是计算机科学与技术专业的基础理论课程。通过本课程的学习，使学生掌握图论与组合数学的基本原理和方法，了解和掌握无向图、有向图、连通图、排列与组合、容斥原理、递推关系和生成函数等基本知识，灵活运用所学知识对一些简单问题进行建模并编程求解。
图论基础知识
图论基本知识 对于网络的研究，最早是从数学家开始的，其基本的理论就是图 论，它也是目前组合数学领域最活跃的分支。我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的……这些都可以用图论的语言和符号精确简洁地描述。图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。考虑到物理学家对于图论这一领域比较陌生，我在此专辟一章介绍图论的基本知识，同时将在后面的章节中不加说明地使用本章定义过的符号。进一步研究所需要的更深入的图论知识，请参考相关文献[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 不能连接两条或以上 边，本文所讨论的图，均符合上述要求，既均为不含多重边的图。如
图论经典问题
常见问题： 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)将树
中国运筹学会图论组合分会青年论文奖奖励办法-GTCA2015
中国运筹学会图论组合分会《青年论文奖》奖励办法 （常务理事会2011年5月5日讨论通过） 第一章总则 为鼓励青年图论与组合工作者的学术进步，提倡青年学生和科研教学第一线的青年科技人员发扬勇于探索、创新进取的精神，表彰优秀的年轻学者的学术研究成果，中国运筹学会图论组合设立青年论文奖（下称《青年论文奖》），设一等奖一名，二等奖二名，另外设提名奖二名。 为了保证《青年论文奖》奖励工作的科学性、公正性和持久性，使《青年论文奖》的表彰奖励工作有利于促进青年学者对图论与组合的发展、普及做出突出贡献，特制定本奖励办法。 第二章组织机构 评选《青年论文奖》的领导机构是运筹学会图论组合分会常务理事会“青年论文奖奖励委员会”（以下简称奖励委员会）。奖励委员会受常务理事会领导，设主任委员一名，由中国运筹学会图论组合分会理事长担任；委员若干人，由部分中国运筹学会图论组合分会常务理事及有关专家担任。奖励委员会成员由常务理事会批准。其主要职责是：审查申请者材料、对合格申请者按照科学、公正的原则，组织评审、公布结果和异议处理等。 奖励委员会的办事机构是学会图论组合分会秘书处，在奖励委员会的领导下，承担日常工作。 奖励工作办事机构和评审委员会委员应坚持廉洁公正、不徇私情、遵守程序的工作原则，认真做好各项工作。 第三章奖励范围 《青年论文奖》的奖励范围是：中国运筹学会会员（包括学生会员），申请者年龄不超过40周岁（申请者需注明身份证号码）。 第四章申报与推荐 《青年论文奖》的申请采取专业委员会推荐和自由申请两种形式。申报青年运筹学奖应提交下列材料： 1.申请者应填写《中国运筹学会图论组合分会青年论文奖申报表》，在申请书 中应清楚地阐述所研究问题的重要性、建立的模型、方法和解决问题技术的科学性和创新性，并提出相应的证据。 2.参评论文必须是国内外学术刊物上近三年公开发表的研究论文。 3.提供两名具有正高级职称专家推荐信，其中至少一名推荐专家与申请人非同 一工作单位。 4.填写单位推荐意见，并由单位负责人签字和单位盖章。 申请人按照要求准备齐全的申报资料按规定的时间报送到学会图论组合分
图论
3 图论 图论在计算机科学、信息科学、人工智能、网络理论、系统工程、控制论、运筹学和经济管理等领域有着广泛的应用。但很多图论问题虽易表达，却难以求解，其中有相当多的图论问题均属NP完全问题。本章主要介绍工程实用简单图论问题的并行算法及其MPI编程实现，包括传递闭包、连通分量、最短路径和最小生成树等。 1.1 传递闭包 设A是一个含N个顶点的有向图G的布尔邻接矩阵(Boolean Adjacent Matrix)，即元素a ij=1当且仅当从顶点i到j有一条有向边。所谓A的传递闭包（Transitive Closure），记为A+，是一个N×N的布尔矩阵，其元素b ij=1当且仅当：①i=j；或②从i出发存在有向路径到j，又称为顶点i到j可达。从G的布尔邻接矩阵A求出G的传递闭包，就称为传递闭包问题。 传递闭包问题有很强的应用背景，在科学计算中广泛存在。传递闭包问题的经典解法之一就是利用布尔矩阵的乘法来求解。本节将把这一算法分别在串行和并行机上实现。 1.1.1 传递闭包串行算法 利用布尔矩阵相乘求解传递闭包问题的原理为：对于布尔矩阵(A+I)k中的任一元素b ij，b ij=1表示从i到j存在长度小于等于k的可达路径，否则，b ij=0。显然对于k=1，(A+I)1中b ij=1当且仅当从i到j路径长度为0（i=j）或为1（从i到j存在有向边）；(A+I)2中，b ij=1当且仅当从i到j路径长度小于等于2；((A+I)2) 2中，b ij=1当且仅当从i到j路径长度小于等于4，等等。因为任意两点间如果存在可达路径，长度最多为N-1，所以k≥N-1时，(A+I)k 就是所求的传递闭包A+。于是(A+I)矩阵的㏒N次自乘之后所得的矩阵就是所求的传递闭包。 根据前面的叙述，很自然的有下面的传递闭包串行算法15.1，其时间复杂度为O(N3㏒N)。 算法15.1传递闭包串行算法 输入：图G的布尔邻接矩阵A 输出：A的传递闭包M procedure closure Begin (1)读入矩阵A /* 以下作A = A+I的运算*/ (2)for i=0 to N-1 do a(i, i) = 1 endfor /* 以下是A矩阵的㏒N次自乘，结果放入M矩阵；每次乘后，结果写回A矩阵*/ (3)for k=1 to㏒N do (3.1)for i=0 to N-1 do for j=0 to N-1 do s=0
电子科技大学图论及其应用5班第4-5章作业
习题4 3： 1）、画一个有Euler闭迹和Hamilton圈的图。 2）、画一个有Euler闭迹但没有Hamilton圈的图。 3）、画一个有Hamilton圈但没有Euler闭迹的图 4）、画一个既没有Hamilton圈也没有Euler闭迹的图 7、证明： 将G中的孤立点去掉后的图为G1，则G1也是没有奇度点的，且G1的最小度大于等于2.则G1存在一个圈S1，在G1 –S1中去除孤立的点，得到一个新的图G2，显然G2也没有奇度的点，且G2的最小度大于等于2.这样G2中也存在一个圈S2，这样一直下去，指导Gm中有圈Sm，且Gm-Sm都是孤立的点。这样E(G) = E(G1)并E(G2)…..
并E(Gm).命题得证。 10、证明： 1）、如果G不是而连通的图，那么G存在割点v或则G是不连通的，G-v的连通分支数大于等于2.由定理：若G是H图，则对于V的每个飞空真子集S，均有G-S的连通分支数小于等于S的顶点数，知，G是非H图。 2）、G 是2部图，且|X|<|Y|,则有G-X的连通分支数等于|Y|>|X|由上边的定理知，G是非H图。 12、证明： 假设G中新加入的一点，为V,它和G中的每一个顶点均相连，这样得到新的图G^,这样G^的度序列为(d1+1,d2+1……,dv+1,V)。因为不存在正整数m<(v+1)/2,使其满足dm
图论总结(超强大)78408
1.图论Graph Theory 1.1.定义与术语Definition and Glossary 1.1.1.图与网络Graph and Network 1.1. 2.图的术语Glossary of Graph 1.1.3.路径与回路Path and Cycle 1.1.4.连通性Connectivity 1.1.5.图论中特殊的集合Sets in graph 1.1.6.匹配Matching 1.1.7.树Tree 1.1.8.组合优化Combinatorial optimization 1.2.图的表示Expressions of graph 1.2.1.邻接矩阵Adjacency matrix 1.2.2.关联矩阵Incidence matrix 1.2.3.邻接表Adjacency list 1.2.4.弧表Arc list 1.2.5.星形表示Star 1.3.图的遍历Traveling in graph 1.3.1.深度优先搜索Depth first search (DFS) 1.3.1.1.概念 1.3.1. 2.求无向连通图中的桥Finding bridges in undirected graph 1.3. 2.广度优先搜索Breadth first search (BFS) 1.4.拓扑排序Topological sort 1.5.路径与回路Paths and circuits 1.5.1.欧拉路径或回路Eulerian path 1.5.1.1.无向图 1.5.1. 2.有向图 1.5.1.3.混合图
1.5.1.4.无权图Unweighted 1.5.1.5.有权图Weighed —中国邮路问题The Chinese post problem 1.5. 2.Hamiltonian Cycle 哈氏路径与回路 1.5. 2.1.无权图Unweighted 1.5. 2.2.有权图Weighed —旅行商问题The travelling salesman problem 1.6.网络优化Network optimization 1.6.1.最小生成树Minimum spanning trees 1.6.1.1.基本算法Basic algorithms 1.6.1.1.1.Prim 1.6.1.1. 2.Kruskal 1.6.1.1.3.Sollin（Boruvka） 1.6.1. 2.扩展模型Extended models 1.6.1. 2.1.度限制生成树Minimum degree-bounded spanning trees 1.6.1. 2.2.k小生成树The k minimum spanning tree problem(k-MST) 1.6. 2.最短路Shortest paths 1.6. 2.1.单源最短路Single-source shortest paths 1.6. 2.1.1.基本算法Basic algorithms 1.6. 2.1.1.1.Dijkstra 1.6. 2.1.1.2.Bellman-Ford 1.6. 2.1.1.2.1.Shortest path faster algorithm(SPFA) 1.6. 2.1.2.应用Applications 1.6. 2.1.2.1.差分约束系统System of difference constraints 1.6. 2.1.2.2.有向无环图上的最短路Shortest paths in DAG 1.6. 2.2.所有顶点对间最短路All-pairs shortest paths 1.6. 2.2.1.基本算法Basic algorithms 1.6. 2.2.1.1.Floyd-Warshall 1.6. 2.2.1.2.Johnson
图论的起源和发展
大 众 文 艺大34 摘要：图论是数学领域中发展最快的分支之一，数学史上著名的七桥问题欧拉只用了一步就证明了不重复地通过7座桥的路线是根本不存在的！这是拓扑学研究的先声。图的染色问题一直是图论研究的焦点问题。数学家赫伍德（Hedwood）成功地运用肯普的方法证明了五色定理，即一张地图能够用五种或者更少的颜色染色。美国伊利诺斯大学的黑肯（W.Haken）和阿佩尔（Appel），经过四年的艰苦工作，终于完成了四色猜想的证明。正是上述那些似乎没有多大意义的游戏的抽象与论证的方法，开创了图论科学的研究。 关键词：团论；染色体；四色猜想 图论是组合数学的—个分支，与其他的数学分支，如群论、矩阵论、概率论、拓扑学、数值分析等有着密切的联系（参见文献[1]）。图论中以图为研究对象，图形中我们用点表示对象，两点之间的连线表示对象之间的某种特定的关系。事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟，而且它具有形象直观的特点。由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点间连接与否尤为重要，而图形的位置、大小、形状及连接线的曲直长短则无关紧要。 20世纪后，图论的应用渗透到许多其他学科领域。从20世纪50年代以后，由于计算机的迅速发展，有力地推动了图论的发展，使图论成为数学领域中发展最快的分支之一。 一、图论的起源 图论是一个古老的但又十分活跃的数学学科，也是一门很有实用价值的学科，它在自然科学、社会科学等各领域均有很多应用。近年来它受计算机科学蓬勃发展的刺激，发展极其迅速。应用范围不断拓广，已渗透到诸如语言学、逻辑学、物理学、化学、电讯工程、计算机科学以及数学的其它分支中。 1736年是图论的历史元年。这一年，欧拉（L?Euler）研究了哥尼斯堡城（K?nigsberg）的七桥问题，发表了图论的首篇论文。欧拉也因此被称为图论之父。 古老而美丽的哥尼斯堡城濒临蓝色的波罗的海，是著名的哲学家康德（Immanuel Kant）的出生地，城中有一条普莱格尔（Pregel）河，河的两条支流在这里汇合，然后横穿全城，流入大海。河水把城市分成4块，于是，人们建造了7座各具特色的桥，把哥尼斯堡城连成一体，如图1．1(a)所示。 早在18世纪，这些形态各异的小桥吸引了众多的游客，游人在陶醉于美丽风光的同时，不知不觉间，脚下的桥触发了人们的灵感，一个有趣的问题在居民中传开。 谁能够从两岸A，B或两个小岛C，D中任一个地方出发一次走遍所有的7座桥，而且每座桥都只通过一次？这个问题似乎不难，谁都乐意用这个问题来测试一下自己的智力。可是，谁也没有找到一条这样的路线。这个问题极大的刺激了德意志人的好奇心，许多人热衷于解决这个问题，然而始终未能成功。“七桥问题” 难住了哥尼斯堡城的所有居民。哥尼斯堡城也因“七桥问题” 而出了名。这就是数学史上著名的七桥问题。 问题看来不复杂，但谁也解决不了，也说不出其所以然来。1736年，当时著名的数学家欧拉仔细研究了这个问题，他将上述四块陆地与七座桥间的关系用一个抽象图形来描述(见图1．1(b))，其中A、B、C、D分别用四个点来表示，而陆地之间有桥相连者则用连接两个点的连线来表示，这样，上述的哥尼斯堡七桥问题就变成了由点和边所组成的如下问题： 试求从图中的任一点出发，通过每条边一次，最后返回到该点，这样的路径是否存在？于是问题就变得简洁明了多了，同时也更一般、更深刻。这样一来，七桥问题就转变为图论中的一个一笔画问题。即能不能一笔不重复的画出图1．1(b)中的这个图形。 原先人们是要求找出一条不重复的路线，欧拉想，成千上万的人都失败了，这样的路线也许根本不存在。于是，欧拉接下来着手判断：这样不重复的路线究竟存不存在？由于这么改变了一下提问的角度，欧拉抓住了问题的实质。最后，欧拉认真考虑了一笔画图形的结构特征。 欧拉发现，凡是能用一笔画成的图形，都有这样一个特点：每当用笔画一条线进入中间的一个点时，还必须画一条线离开这个点。否则，整个图形就不可能用一笔画出。也就是说，单独考察图中的任何一点（起点和终点除外），这个点都应该与偶数条线相连；如果起点与终点重合，那么，连这个点也应该与偶数条线相连。 在七桥问题的几何图中，A、B、D三点分别与3条线相连，C 点与5条线相连。连线都是奇数条。因此，欧拉断定：一笔画出这个图形是不可能的。也就是说，不重复地通过7座桥的路线是根本不存在的！天才的欧拉只用了一步就证明了这个难题，从这里我们也可以看到图论的威力有多么的强大！ 欧拉对七桥问题的研究，是拓扑学研究的先声。 1750年，欧拉又发现了一个有趣的的现象。欧拉得到了后人以他的名字命名的“多面体欧拉公式”。正4面体有4个顶点、6 条棱，它的面数加顶点数减去棱数等于2；正6面体有8个顶点、12条棱，它的面数加顶点数减去棱数也等于2。接着，欧拉又考察了正12面体、正24面体，发现都有相同的结论。于是继续深入研究这个问题，终于发现了一个著名的定理： 这个公式证明了多面体只有正四面体、正六面体、正八面体、正十二面体、正二十面体五种。这个定理成为拓扑学的第一个定理，这个公式被认为开启了数学史上新的一页，促成了拓扑学的发展。 二、图论的发展 从19世纪中叶开始，图论进入第二个发展阶段。这一时期图论问题大量出现，诸如关于地图染色的四色问题、由“周游世界”游戏发展起来的哈密顿(W.Hamilton)问题等。 图的染色问题一直是图论研究的焦点问题。最早记载染色问题的是英国伦敦大学（University of London）的数学教授德?摩根（D.Morgan）。 1852年，一位刚从伦敦大学毕业的学生费南西斯?古色利（F.Guthrie）在研究英国地图时想到了一个奇怪的问题。这个问题被称为世界近代三大数学难题之一，这就是著名的“四色猜想”。问题的起源是这样的： 古色利望着挂在墙上的英国地图发呆，他边数着英国的行政区域，边查找它们的位置，同时还注意各区域的地图着色，看着看着他突然发现，该地图仅用四种不同的颜色便可以将地图中相邻的区域分开。古色利无法解释这一现象，于是他写信给仍在大学读书的弟弟，让他向该校有名的数学家德?摩根请教。摩根首先注意到：区分地图上的不同区域少于四种颜色不行。但遗憾的是摩根本人也未能解决这个问题。于是向自己的好友、著名数学家哈密顿爵士请教。哈密顿接到摩根的信后，对四色问题进行论证。但直到1865年哈密顿逝世，问题也没有能够解决。 1878年，英国数学家凯莱（Cayley）在伦敦数学年会上正式提出该问题——平面或球面上的地图仅需四种颜色可以将任何相邻的两区域分开——且征求解答，人称“四色猜想” 的问题便引起了世界数学界的重视。许多一流的数学家纷纷参加了四色猜想的大会战。1878—1880年，著名的律师兼数学家肯普（Kempe）和泰勒（Taylor）两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。但是数学家赫伍德（Hedwood）仍然花费毕生精力致力于四 图论的起源和发展 李 冰 （河北省唐山第五中学 063000） 图1．1(a) A D C 图1．1(b) 理论研究
组合数学与图论试卷A.
---○---○--- ---○---○--- … …… … 评卷 密封 线 … …… … …… 密 封线 内不 要 答题 ，密 封线外 不准 填写 考 生 信 息， 违者 考试 成绩 按0 分 处理 … … … …… … 评卷 密 封 线 … … … … 中南大学考试试卷A 2008~2009 学年 上 学期 组合数学课程 一、填空题(本题42分，每小题3分) 1．求从100到500的整数中能被3和5整除，但不能被7整除的数的个数 。 2．现有5双不同颜色的鞋子，重新搭配，使得两两成双（左、右鞋为一双），试求有 种搭配方法。 3．()4231322x x x +++的展开式中5x 的系数是 。 4．将a,b,c,d,e 排成一行，要求a 在c 的左侧(可以不邻)，b 也在c 的左侧(可以不邻)的排列有 种排法。 5．求多重集合{}4,2,1,2S a b c d =????中的8-可重组合数为 个。 6．求右边棋盘的车多项式 。 7．求由0，1，2作成的含有偶数个0且能被3整除的6位数（数要求第一位不为0）的个数 。 8．求()416p ＝ 。 9．求26的部分数最少的完备分拆的个数为 ，并写出一个为 。 10．求25的自共轭分拆的个数为 。 11. 求()303n k k k =+∑＝ 。 ******
12．从()12，到()55，的T 路的条数为 。 13． Ramsey 数(3,32)R ；= 。 14.2 39x y +≤的整数解的个数为 。 二、求由3个相同的绿球、2个相同的红球、2个相同的白球和 3个相同的黄球作成的恰有两个黄球相邻的全排列的个数． (本 题10分)
科大组合与图论专业三十五年
科大组合与图论专业三十五年 ------为科大校庆五十周年而写 李乔、李炯生、徐俊明 中国科学技术大学组合与图论专业从李乔发表的第一篇论文算起，经历了整整35年。在这35年里，逐渐形成了自己的研究特色：组合矩阵论和组合网络理论。发表学术论文300余篇，专著和教材16部。获得1993年国家教委科技进步一等奖（合作）和2003年安徽省自然科学二等奖。培养硕士研究生57名，博士研究生26名，进站博士后5名，接收国内高校青年进修和访问学者9名。 回忆这段历史，科大组合学与图论专业的创立和发展大体上分为三个阶段。 一、创立阶段（1973-1985） 中国科学技术大学数学系的组合学与图论研究始于上世纪七十年代初。北京大学段学复教授向曾肯成建议：国内可由科大牵头研究组合与图论。 李乔和冯克勤凭借代数方面的深厚功底开始涉及组合与图论，在国内率先开展代数图论研究。1973年，李乔在《中国科学技术大学学报》上发表的“关于偶图的极大对口”是本专业第一篇学术论文。随后，李乔和冯克勤合作完成了 “关于树和其他图的联系矩阵”、“图的谱性质的若干结果”和“论图的最大特征根” 3篇论文，分别发表在《中国科学技术大学学报》（1976，1979）和《应用数学学报》（1979）上。这些论文是国内代数图论研究最早的学术论文，现成为此研究领域的经典论文之一。在此期间，李乔和冯克勤还从数学角度介入当时国内兴起的“量子化学的图论研究”，成为国内最早开展此项研究的学者。1977年8月在上海举行的全国第一次量子化学学术会议上，李乔介绍了他与冯克勤在这方面的研究成果。 组合学是经典的数学分支，被人熟知。图论是组合学的一个活跃分支，但当时数学界对它还不大了解。1977年底，李乔对数学系师生做了题为《图论》的介绍性报告。他以图论语言简洁证明“在任意六人中必存在三人, 要么都相识,要么都不相识”为开场，来介绍图论，生动有趣。正是这个报告引起了不少人对图论的兴趣。 在此以前，国内出版的图论教材只有李修睦于1962年译自法国图论专家C.Berge的《图的理论及其应用》。J.A.Bondy和U.S.R.Murty的图论教科书《图
运筹学图论问题
工商管理中的运筹学问题—建模及求解 项目报告 姓名： 课题组的分工或贡献： 课程名称：运筹学 指导教师： 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。