第六章图论
§8.1 图论发展史
第一阶段：瑞士数学家欧拉（E. Euler）在1736年发表了一篇题为“依据几何位置的解题方法”的论文，有效地解决了哥尼斯城堡“七桥难题”，从此开创了图论的历史新纪元；所谓“七桥难题”是指：18世纪的哥尼斯堡城中流过一条河，河上有七座桥连接着河的两岸和河中的两个小岛，如图8-1所示：一个游者怎样才能一次连续走过这七座桥而每座桥只走一次，回到原出发点；没有人想出这种走法，又无法说明走法不存在。欧拉将这个问题归结为如图8-2 所示的问题。他用A,B,C,D四点表示河的两岸和小岛，用两点间的连线表示桥。七桥问题变为：从A,B,C,D任意点出发，能否通过每条边一次且仅一次，再回到原点？欧拉证明了这样的走法不存在，并给出了这类问题的一般结论。
图8-1 图8-2
第二阶段：1847年，数学家基尔霍夫（Kirchhoff）运用图论解决了电路理论中的求解联立方程的问题，他引入了“树”的概念，可惜由于他的思想超出了时代的发展而长期未被重视；到1857年，英国数学家凯莱（Cayley）又从化学的角度进一步扩展了“树”的概念，从此图论又有了新的发展。
第三阶段：1857年，英国数学家哈密尔顿（Hamilton）发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个顶点分别表示世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次且仅一次再回到原出发点的路，这就是“环球旅行”问题。要在图中找一条经过每个点一次且仅一次的路，能成为哈密尔顿回路。
第四个阶段：20世纪以后，随着计算机的不断发展，图论也有了突飞猛进的进展，广泛应用于各科领域：如物理、化学、信息论，博弈论，计算机网络，等等；目前图论已经发展成完整的一个数学分支，并且越来越多的数学爱好者倾向于研究图论。
§8.2 图与网络的基本概念
一、图与网络的基本概念
1、图的相关概念及其分类
引例：在一次聚会中有五位代表其中与，与，
与，与，与是朋友，则我们可以用一个带有五个顶点、五条边的图形来表示这五位代表之间的朋友关系（图8-3）：
图8-3
定义1、设是一个非空有限集合，
是与不相交的有限集合，一个图是指一个有序二元组，其中称为图的顶点集，称为的边集；，.
如引例中五位代表之间的朋友关系可以用图来表示，，
，其中：，，，，
.
定义2、两个端点重合的边称为环；两点之间多于一条边的，称为多重边；
不含有环和多重边的图称为简单图。
定义3、任意两个顶点之间都有边相连的无向简单图称为完全图，有个顶点的完全图。
定义4、图的点集可以分为两个非空子集即：
，使得中每一条边的两个端点必有一个端点属于，另一个端点属于，则称为二部图（偶图），记作：。
2、顶点的次
定义5、以点为端点的边数叫做顶点的次（度），记作
: 。
例如上述引例图中：。
定理1、任何图中顶点次数的总和等于边数的2倍。
推论1.1、任何图中，次为奇数的顶点必有偶数个。
证明：设必有下式成立:
由于2m为偶数，而为若干偶数之和也是偶数。所以也为偶数，即是偶数。
3、子图
定义6、图
和图，若，则称是的子图，记作：；特别的，当时，称为的生成子图。
例1、如下图中（b）为（a）的子图，（c）为（a）生成子图。
4、网络
在实际问题中，往往只用图来描述所研究对象之间的关系还不行，与图联系在一起的，通常还有与点或边有关的某些参数指标，我们称之为“权”，权可以代表如距离、费用、通过能力（容量）等等。这种点或边带有某种数量指标的图成为网络。与无向图和有向图相对应，网络又分为无向网络和有向网络；
例2、图（a），（b）是常见的网络例子。
一、连通图
定义7、在无向图中，若图中某些点与某些边的交替序列可以排成如下
的形式，且
,则称这个点边序列为联接v i0和v ik的一条链，链长为；没有重复顶点和边的链称为路；起点和终点重合的路称为回路。
例3、如下图中是一条从到的链；
是一条从到的路；
是一条从到的回路。
二、图的矩阵表示
用矩阵表示图对研究图的性质及应用常常是比较方便的，图的矩阵表示方法有多种，下面介绍两种重要的矩阵：邻接矩阵和边权矩阵；
定义8、网络（赋权图），边有权，构造矩阵其
中：当时，否则为0 ，则称矩阵为网络的边权矩阵；网络图
中，，构造一个矩阵，其中当时，否则为0；称图的邻接矩阵。
例4、分别求下列两个网络图的邻接矩阵和边权矩阵：
图
8-4
图8-5
解：（1）图8-4的边权矩阵为： （2） 图8-5的邻接矩阵为：
四、中国邮路问题 1、欧拉道路与欧拉回路
定义9、连通图中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉
道路；若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路；具有欧拉回路的图称为欧拉图（E 图）。在引言中提到哥尼斯堡“七桥问题”就是要在图中寻找一条欧拉回路。
定理2、无向连通图是欧拉图，当且仅当中无奇点。
推论2.1、无向连通图为欧拉图，当且仅当的边集可划分为若干个初等回路。
推论2.2、无向连通图有欧拉道路，当且仅当中恰有两个奇点。
2、中国邮路问题
一个邮递员，负责某一地区的信件投递。他每天要从邮局出发，走遍该地区所有街道再返回邮局，问应如何安排送信的路线可以使所走的总路程最短？这个问题是我国管梅谷同志在1962年首先提出的。因此国际上统称为中国邮路问题。用图论的语言描述：给定一个连通图，每边有非负权，要求一条回路过每边至少一次，且满足总权最小。
所谓中国邮路问题实际上就是从网络图中寻找权最小的欧拉回路即最优环游，对于欧拉图来讲欧拉图中的任意一条回路都是最优环游，下面介绍网络图中寻找最优环游的算法：“Fluery”算法的基本步骤：
（1）任意选取一个顶点，置；
（2）假定已经选出，再在中选取满足与
关联，且尽可能不是割边；
（3）当（2）不能执行时，停止；否则让，转（2）。
下面通过一个例题来讨论当网络图为非欧拉图的连通图时，寻找最优环游的方法：“奇偶点图上作业法”的基本步骤；
例5、求解图8-6所示网络的中国邮路问题。
图8-6
图8-7
第一步：确定初始可行方案。
先检查图中是否有奇点，如无奇点则已是欧拉图，找出欧拉回路即可。如有奇点，由前知奇点的个数为偶数，所以可以两两配对，每对顶点间选一条路，使得这条路上均为二重边。
图8-6中有四个奇点，将，配对，连接的路有好几条，任
取一条，如，类似地，对得到图8-7，已是欧拉图。对应这个可行方案，重复边的总长为：
.
第二步：调整可行方案，是重复边最多为一次。
去掉各两条，得到图8-8，重复边总长度下降为：
第三步：检查图中每个初等圈是否满足定理条件（2）。如不满足则进行调整，直至满足为止。
检查图8-8，发现圈总长度的长为14，大于该圈总长度的一半，可以做一
次调整，以，得到图8-9，重复边总长度下降为：
图8-8
图8-9
再检查图8-9，圈总长度为24，而重复边长为13。再次调整得图8-10，重复边总长度为15。
检查图8-10，条件（1），（2）均满足，得到最优方案。途中任意欧拉回路即为最优邮递路线。
图8-10
§8.3 树
一、树的概念和性质
例6、乒乓球单打比赛抽签后，可用图来表示相遇情况，如下图所示。
定义10、连通且不含圈的无向图称为树，树中次为1的点称为树叶，次大于1的点称为支点。
定理3、图，则下列关于书的说法是等价的。
（1）T是一个树。（2）T无圈，且m=n-1。
（3）T连通，且m=n-1。（4）T无圈，但每加一新边即唯一一个圈。
（5）T中任意两点，有唯一链相连（6）T连通，但每舍去一边就不连通。
二、图的生成树
定义11、若图的生成子图是一棵树，则称该树为的生成树；或简称图的树。
例7、如图8-11中（b）为（a）图的生成树，边为树枝，为弦。
图8-11
定理4、图有生成树的充分必要条件为是连通图。
下面给出寻找连通图的生成树的两种算法：“避圈法”与“破圈法”；
（1）“避圈法”是指首先将连通图中的所有的顶点都画出来，然后逐个的将图中的边加进去，每加一条边都要保证不含圈，直到加的边数是顶点数减1为止，得到的连通图一定是图的生成树；
（2）“破圈法”是指在给定的连通图中，逐个将图中的每一个圈都去掉一条边使其变成路，直到最后只剩下边数是顶点数减1条的连通图即为图的生成树。
例8、一个乡有9个自然村，其间道路如图8-12（a）所示，要以村为中心建有线广播网络，如要求沿道路架设广播线，应如何架设？
图8-12
解：本问题用上述“破圈法”，任取一圈从中去掉边，再选圈
，去掉边，以同样方法进行，直到无圈。图8-12（b）就是一种方案。
三、最小生成树问题
定义12 、连通图每条边上有非负的权。一棵生成树的所有树枝上的权总和，称为这个生成树的权。具有最小的权的生成树被称为最小生成树，简称最小树。
下面介绍寻找最小树的两种算法。
算法1（Kruskal）算法
这个方法类似于生成树的“避圈法”，基本步骤如下：
每步从未选的边中选取边e，使它与已选边不构成圈，且e是位选边中的最小权边，直到选够n-1条边为止。
例9、仍用上节例8，若已知各条道路长度如图8-12（a）所示，各边上的数字表示距离，问如何拉线才能使用线最短？这就是一个最小生成树问题，用Kruskal算法。
先将（a）中边按大小顺序由小至大排列：
然后按照边的排列顺序，取定
由于下一个未选中的最小权边构成圈，所以排除。选。
得到（b）就是图G的一颗最小树，它的权是13。
算法2“破圈法”
基本步骤：（1）从图G中任选一棵树。
（2）加上一条弦中立即生成一个圈。去掉此圈中最大权边，得到新树
，重复（2）在检查剩余的弦，直到所有的弦都检查完毕为止。
例10、仍用例8，先求出图的一棵生成树如图8-13的（a），加弦
,去掉最大权边：再加上弦,得圈,去掉最大权边直到全部的弦都已经试过，图8-13（b）即为所求。
图8-13
四、根树及其应用
定义13、若一个有向图在不考虑边的方向时是一棵树，则这个有向图为有向树。
定义14、有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树。
根树中入次为0的点称为根；根树中出次为0的点称为分枝点。由根到某一顶点的道路长度（设每边长度为1），成为顶点的层次。
例11、如图8-14所示的树是根树，其中为分枝点，其余各点为叶，顶点的层次为1，顶点的层次为3等等。
图8-14
定义15、在根树中，若每个顶点的次小于或等于，称这棵树为叉树。若每个顶点的出次恰好等于或零，则称这棵树为完全叉树。当=2时，称为二叉树、完全二叉树。
在实际问题中常讨论叶子上的距离（层次）为，这样二叉树T的总权数
满足总权数最小的二叉树成为最有二叉树。霍夫曼（D A Huffman）给出了一个求最有二叉树的算法，所以又称霍夫曼树，算法基本步骤为：
（1）将s个叶子节点按权由大排列，不失一般性，设
（2）将二个具有最小权的叶子合并成一个分枝点，其权为，将新的分枝点作为一个叶子。令若s=1停止，否则转（1）。
例12、最优检所问题。使用计算机进行图书分类。现在五类图书共100万册，其中有A 类50万册，有B类20万册，D类10万册。问如何安排分拣过程，可是总的运算（比较）次数最小？
解构造一棵具有5个叶子的最优二叉树，其叶子的权分别为50，20，5，10，15，见图8-15（a）所示，按（b）进行分类。总权为：
图8-15
分拣过程是先把A类50万册从总数中捡出来，其次将B类20万册分检出来，然后再将E 类15万册分检出来，最后再将D，C分检。
例13、某厂购进一批元件。欲进行检验后按质量分为六等。已知一等品的概率为0.45，二等品的概率为0.25，三等品0.12，四等品0.08，五等品0.05，等外品0.05。假设分等测试一次只能分辩出一种等级，而每次测试的时间皆为t。问如何安排测试过程，是期望的时间达到最短？
解：构造一棵具有6个叶子的最优二叉树的总权。经计算得
图8-16
§8.4 最短路问题
最短路问题的一般提法如下：设为连通图，图中各边
，为图中任意两点，求一条道路，使它是从
的所有道路中总的权最小的道路。即：
最小
有些最短问题也可以使求网络中某指定点到其余所有结点的最短路，通过求网络中任意两点间的最短路。下面我们介绍三种算法，可分别用于求解这几种最短路问题。
一、Dijkstra算法
本算法由Dijkstra于1959年提出，可用于求解指定两点间的最短路，或从指定点
到其余各点的最短路，目前被认为是求非负权网络最短路问题的最好方法；算法的基本步骤：（1）给。
（2）若点为刚得到P标号的点，考虑这样的点属于E，且
的T标号进行如下的更改：
（3）比较所有具有T标号的点，把最小者改为P标号为P标号，即:
当存在两个以上最小者时，可同时改变为P标号。若全部均为P标号则停止。否则用
转回（2）。
例1、用Dijkstra算法求图8-17中点的最短路。
解：
图8-17
（1）首先给，给其余所有点T标号，
（2）由于边属于E，且为T标号，所以修改这两个点的标号：
（3）比较所有T标号，最小，所以令。
（4）为刚得到P标号的点，考察边端点。
（5）比较所有T标号，最小，所以令。
（6）考虑点，有
（7）全部T标号中，
（8）考察，
（9）全部T标号中，
（10）考察，
（11）全部T标号中，。
（12）考察
（13）全部T标号中，。
（14）考察，
（15）因只有一个T标号，计算结束。
从到的最短路为，路长为。
二、逐主次逼近算法
本算法可用于网络中有带有负权的边时，求某指定点到网络中任意点的最短路。算法的基本思路是基于以下事实：如果的最短路总沿着该路从，然后
再沿边到达，则到的这条路必然也是到的最短路；若令表示从到
的最短路长，为到的最短路的长，则必有方程：
用迭代方法解这个方程。开始时令
即用的直接距离作初始解，若。从第二步起，是用迭代公式
求，当进行到第t步，若出现
则停止，点到各点的最短路长。
例2、求图8-18中点到各点的最短路。
图8-18
解初始条件：
第一轮迭代：
类似可得：
可以看出最短路长。
迭代进行到第六步时，发现则停止。表中最后一列数字分别表示
点到各点的最短路长。
如果需要知道点到各点的最短路径，可以采取“反向追踪”的办法。如需要求出
点的最短路径，已知
而在表中寻求满足等式的。
在考察，由于。
考察
考察。
由于递推公式中的，实际意义为从点、至多含有k-1个中间点的最短路权，所以在含有n各点的图中，如果不含有总的权和小于零的回路，求从点到任一点的最短路权，用上述算法最多经过n-1次迭代必定收敛。
例3、已知某地区的交通网络如图8-19所示，其中点代表居民区，便表示公路，为小区间公路距离，问区中心医院建在哪个小区，可使得距离最远的小区居民就诊时所走的路
第八章图论方法 §1 图论中图的概念 在人们从事的各种活动中，为了反映事物之间的关系，常在纸上用点和线画出各种各样的示意图。例如，为了反映某地区的铁路交通、公路网分布情况，画出铁路、公路交通图。在这些图中以点表示城镇，用点与点之间的连线表示城镇之间的铁路或公路的沟通情况。诸如此类的图还有电缆线分布图、供水道及下水道分布图、航空线图等等。 再如，在一场有5支球队参加的球类比赛中，比赛情况也可以用图表示出来，如图6-1，我们用点代表各个球队，某两个队比赛过一次，就在两个点之间画一条箭线。从图中可以看出A队与其他各队都比赛过，只有一场败给C 队。而B队和E队各比赛过两场，成绩都是一胜一负，等等。 图6-1 从上述例子中可以看出，图的最基本要素是：点、以及点与点之间的一些连线。通常用点表示我们所要研究的对象（如城市、运动队、状态等等），用线表示研究对象间的某种特定关系（如两个城市之间有铁路，两个运动队之间已经比赛过等）。因此可以说，图是反映对象之间关系的一种工具。如果两个对象之间有某种特定关系，那么就用一条线连接这两个点。 必须指出：上述图中点的相对位置如何，点与点之间连线的长短曲直，对于反映研究对象之间的关系并不很重要，因此，图论中的图与几何图、工程图本质上是不同的。 另外在许多情况下，我们要研究的“关系”只用一条线反映还是不够完全。比如说比赛，我们关心的如果不只是两个队是否比赛过，还要了解比赛的胜负情况，我们可以用一条箭线（有向线）来表示，如果A队胜了B队，就表示为
A→B。如图6-1所示，从图中可以看出A队三胜一负，D队三场全负等。类似的情况在生产和生活中也是常见的，例如交通运输中的“单行线”、部门之间的领导与被领导关系、一项生产活动中各工序之间的先后次序关系等等。图论中把不带箭头的连线叫做边，把带箭头的连线叫做弧。 如果一个图是由点和边所构成的，则称之为无向图，记作G=（V，E），其中V表示图G中的所有点组成的点集合，E表示图G中所有边组成的边集合。如，交通图。 如果一个图是由点和弧所构成的，则称之为有向图，记作G=（V，A），其中V表示图G中的点集合，A表示图G中所有弧组成的弧集合（如上图）。 其次，为了反映两个城市之间铁路线的公里数（或运行时间等），就要在这两个城市之间的连线旁边写上里程数（或运行时间等）。这就是说，根据问题的需要，还可以在图的点旁或连线旁标上数，统称为权数。权数在不同的场合可以有不同的含义，如距离（长度），时间、费用、容量等等。如果给图中每一条连线赋予一个数，则称这样的图G为赋权图，所谓网络就是指定了起点（发点）和终点（收点）的赋权图。 对要研究的问题确定具体对象及各对象间的关系，并用图的形式表示出来，这样的图就是对研究问题建立的图模型。用建立图模型的方法往往能帮助我们解决一些用其他方法难以解决的问题。 例1、有甲、乙、丙、丁、戊、已六名运动员报名参加A、B、C、D、E、F六个项目的比赛。表中打√的是各运动员报名参加的比赛项目。问六个项目的比赛顺序应如何安排，才能保证每名运动员都不连续地参加两项比赛。 解：把比赛项目作为研究对象，用点表示。如果两个项目有同一名运动员参加，就在代表这两个项目的点之间连成一条线，可得一图。在该图中只要找出一个点的序列，使依次排列的两个点间没有连线，就能保证每名运动员不会
习题一 作者---寒江独钓 1.证明：在n 阶连通图中 (1) 至少有n-1条边； (2) 如果边数大于n-1，则至少有一条闭迹； (3) 如果恰有n-1条边，则至少有一个奇度点。 证明: (1) 若G 中没有1度顶点，由握手定理： ()2()21v V G m d v n m n m n ∈= ≥?≥?>-∑ 若G 中有1度顶点u ，对G 的顶点数作数学归纳。 当n=2时，结论显然；设结论对n=k 时成立。 当n=k+1时，考虑G-u,它仍然为连通图，所以，边数≥k-1.于是G 的边数≥k. (2) 考虑G 中途径： 121:n n W v v v v -→→→→L 若W 是路，则长为n-1;但由于G 的边数大于n-1,因此，存在v i 与v j ,它们相异，但邻接。于是： 1i i j i v v v v +→→→→L 为G 中一闭途径，于是 也就存在闭迹。 (3) 若不然，G 中顶点度数至少为2，于是由握手定理： ()2()21v V G m d v n m n m n ∈= ≥?≥?>-∑ 这与G 中恰有n-1条边矛盾！ 2.(1)2n ?12n 2?12n ?1 (2)2n?2?1 (3) 2n?2 。 证明 :u 1的两个邻接点与v 1的两个邻接点状况不同。所以， 两图不同构。 4.证明下面两图同构。 u 1 v 1
证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对?v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 5.指出4个顶点的非同构的所有简单图。 分析：四个顶点的简单图最少边数为0，最多边数为6，所以 可按边数进行枚举。 (a) v 2 v 3 u 4 u (b)
图论及其应用答案电子科 大 This model paper was revised by the Standardization Office on December 10, 2020
习题三： 证明：e是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u，v）必含e . 证明：充分性: e是G的割边，故G ?e至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G中的u ,v不连通， 而在G中u与v连通，所以e在每一条(u ,v )路上，G中的(u ,v )必含e。 必要性：取12,u V v V ∈∈，由假设G中所有(u ,v )路均含有边e，从而在G ?e中不存在从 u与到v的路，这表明G不连通，所以e 是割边。 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G是块，任取G的一点u，一边e，在e边插入一点v，使得e成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G中的u,v 位于同一个圈上，于是G 1中u 与边e都位于同一个圈上。 （2）→（3）： G无环，且任意一点和任意一条边都位于同一个圈上，任取G的点u ，边e ，若u在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u不在e上，由定理，e的两点在同一个闭路上，在e边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 （3）→（1）： G连通，若G不是块，则G中存在着割点u，划分为不同的子集块V 1, V 2, V 1, V 2无环，12,x v y v ∈∈，点u在每一条(x ,y )的路上，则与已知矛盾，G是块。 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。 证明：v是单图G的割点，则G ?v有两个连通分支。现任取x ,y ∈V (G ?v ), 如果x ,y 不在G ?v的同一分支中，令u是与x ,y处于不同分支的点，那么，x ,与y在G ?v的补图中连通。若x ,y在G ?v的同一分支中，则它们在G ?v的补图中邻接。所以，若v是G 的割点，则v不是补图的割点。 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）}
第二章 图的连通性 在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图，其连通的程度也有高有低。例如，下列三个图都是连通图。对于图G 1，删除一条边或一个顶点便可使其变得不连通；而对于图G 2，至少需要删除两条边才能使其不连通，也可以删除一个顶点使其不连通；对于图G 3，要破坏其连通性，则至少需要删除三条边或三个顶点。 本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性程度。通过研究割边和割点来刻画1连通图的特性；定义连通度和边连通度来度量连通图连通程度的高低；通过不交路结构和元素的共圈性质来反映图的2连通和k 连通性。 §2.1 割点和割边 定义2.1.1 设)(G V v ∈，如果)()(G w v G w >?，则称v 为G 的一个割点。 （注：该定义与某些著作中的定义有所不同，主要是在环边的顶点是否算作割点上有区别）。 例如，下图中u , v 两点是其割点。 定理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 是割点。证毕。
图论第一次作业 By byh
|E(G)|,2|E(G)|2G υυ??≤ ??? ?? ??? 1.1 举出两个可以化成图论模型的实际问题 略 1.2 证明其中是单图 证明：（思路）根据单图无环无重边的特点，所以 最大的情形为任意两个顶点间有一条边相连，即极 端情况为。
?1.4 画出不同构的一切四顶单图 ?0条边：1条边： ?2条边：3条边： ?4条边：5条边：?6条边：
1.10G?H当且仅当存在可逆映射θ:V G→V H，使得uv∈E G?θuθv∈E H，其中G和H是单图。（证明充分性和必要性） ?必要性 ?若G?H，由定义可得，存在可逆映射θ:V G→V Hφ:E G→E(H)当且仅当ψ G e=uv时，ψHφe=θuθ(v)，所以uv∈E G? θuθv∈E H ?充分性 ?定义?:E G→E(H)，使得uv∈E G和θuθv∈E(H)一一对应，于是?可逆，且ψ e=uv的充要条件是ψHφe=θuθv，得G?H G
1.12求证(a)?K m ,n =mn，(b)G是完全二分图，则?G≤1 4 v G2 ?(a)对于K m ,n ，将顶集分为X和Y，使得X∪Y=V K m,n， X∩Y= ?，X=m，Y=n，对于X中的每一顶点，都和Y中所有顶点相连，所以?K m,n =mn ?(b)设G的顶划分为X,Y，X=m,Y=v?m，则?G≤ ??K m ,v-m =v?m m≤v2 4
?证明： ?(a)第一个序列考虑度数7,第二个序列考虑6,6,1 ?(b)将顶点v分成两部分v’和v’’ ?v’ = {v|v= v i, 1≤ i≤ k}, ?v’’ = {v|v= v i, k< i≤ n} ?以v’点为顶的原图的导出子图度数之和小于 ?然后考虑剩下的点贡献给这k个点的度数之和最大可能为
图论例讲 （陶平生） 1、设有2n 阶简单图G ，若其每个顶点的度数皆不小于n ，证明：从G 中必可选出 n 条边，其端点互不相同． 2、某地网球俱乐部的20名成员举行14场单打比赛，每人至少上场一次，证明：必有六场比赛，其中的12名参赛者各不相同．（美国1989） 3、设G 为n 阶图，且没有长为4的圈；证明：其边数( 14n q ?? ≤ +??? ? ． 4、任意给定() 2n n ≥个互不相等的n 位正整数，证明：存在{}1,2,,k n ∈ ，使得 将它们的第k 位数字都删去后，所得到的n 个1n -位数仍互不相等. 5、设G 为n 阶图()5n ≥，其边数4e n ≥+，证明G 中存在两个无公共边的圈. 6、若简单图G 有21n +个顶点，至少31n +条边(2)n ≥，证明：G 中必有偶圈． 7、一次足球邀请赛共安排了n 支球队参加，每支球队预定的比赛场数分别是 12,,,n m m m ，如果任两支球队之间至多安排了一场比赛，则称12(,,,)n m m m 是一个有 效安排；证明：如果12(,,,)n m m m 是一个有效安排，且12n m m m ≥≥≥ ，则可取掉一支球队，并重新调整各队之间的对局情况，使得11231 2(1,1,,1,,,)m m n m m m m m ++--- 也 是一个有效安排． 8、十个城市之间有两个航空公司服务，其中任意两个城市之间都有一条直达航线（中 间不停），所有航线之间都是可往返的． 证明：至少有一个航空公司可以提供两条互不相交的环形旅行线路，其中每条线路上的城市个数都为奇数． （与其等价的图论说法是：10阶完全图10K 的边红蓝2-染色，则必存在两个无公共顶点的同色奇圈（顶点个数为奇数的圈，且这两个圈的边或者同为红色，或者同为蓝色））． 9、在一次学术讲演中有五名数学家参加，会上每人均打了两次旽，且每两人均有同时 在打旽的时刻，证明：一定有三人，他们有同时在打旽的时刻． 10 、() 2n n n ?≥矩阵A 中，每行及每列的元素中各有一个1和一个1-，其余元素 皆为0；证明：可以通过有限次行与行的交换以及列与列的交换，化为矩阵B ，使得 0A B +=.（即A 中的每个数都变成了其相反数） 11、有七种颜色的珍珠，共计14颗，其中每种颜色的珍珠各两颗；今把这些珍珠分装 于七个珠盒中，使得每个珠盒中各有一对不同颜色的珍珠； (1)、证明：不论各盒中的珍珠怎样搭配，总可以将这七个珠盒分别放置于一个正七边 形的七个顶点之上，使得七边形的任两个相邻顶点处所放置的盒中，四颗珍珠互不同色． (2)、如将以上条件与待证结论中的“七”一律改为“五” ，14改为10，则情况如何？
二、应用题 题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)={, ,
图论第三次作业 一、第六章 2.证明： 根据欧拉公式的推论，有m ≦l*(n-2)/(l-2), (1)若deg(f)≧4,则m ≦4*(n-2)/2=2n-4; (2)若deg(f)≧5,则m ≦5*(n-2)/3,即：3m ≦5n-10; (3)若deg(f)≧6,则m ≦6*(n-2)/4,即：2m ≦3n-6. 3.证明： ∵G 是简单连通图，∴根据欧拉公式推论，m ≦3n-6; 又，根据欧拉公式：n-m+φ=2,∴φ=2-n+m ≦2-n+3n-6=2n-4. 4.证明： (1)∵G 是极大平面图，∴每个面的次数为3， 由次数公式：2m==3φ, 由欧拉公式：φ=2-n+m, ∴m=2-n+m,即：m=3n-6. (2)又∵m=n+φ-2,∴φ=2n-4. (3)对于3n >的极大可平面图的的每个顶点v ，有()3d v ≥，即对任一一点或者
子图，至少有三个邻点与之相连，要使这个点或子图与图G 不连通，必须把与之相连的点去掉，所以至少需要去掉三个点才能使()(H)w G w G <-，由点连通度的定义知()3G κ≥。 5.证明： 假设图G 不是极大可平面图，那么G 不然至少还有两点之间可以添加一条边e ，使G+e 仍为可平面图，由于图G 满足36m n =-，那么对图G+e 有36m n '=-，而平面图的必要条件为36m n '≤-，两者矛盾，所以图G 是极大可平面图。 6.证明： (1)由()4G δ=知5n ≥当n=5时，图G 为5K ，而5K 为不可平面图，所以6n ≥，（由()4G δ=和握手定理有24m n ≥，再由极大可平面图的性质36m n =-，即可得6n ≥）对于可平面图有()5G δ≤，而6n ≥，所以至少有6个点的度数不超过5. (2)由()5G δ=和握手定理有25m n ≥，再由极大可平面图的性质36m n =-，即可得12n ≥，对于可平面图有()5G δ≤，而12n ≥，所以至少有12个点的度数不超过5. 二、第七章 2.证明： 设n=2k+1,∵G 是Δ正则单图，且Δ>0, ∴m(G)==>k Δ,由定理5可知χˊ(G)=Δ(G)+1.
图论复习题答案 一、 判断题，对打√，错打 1．无向完全图是正则图。( √ ) 2．零图是平凡图。( ) 3．连通图的补图是连通图. ( ) 4．非连通图的补图是非连通图。( ) 5．若连通无向简单图G中无圈，则每条边都是割边。( √ ) 6．若无向简单图G是（n，m）图，并且m=n-1，则G是树。( ) 7．任何树都至少有2片树叶。( ) 8．任何无向图G都至少有一个生成树。( ) 9．非平凡树是二分图。( √ ) 10．所有树叶的级均相同的二元树是完全二元树。( ) 11．任何一个位置二元树的树叶都对应唯一一个前缀码。( √ ) 12．3,3 K是欧拉图也是哈密顿图。( ) 13．二分图的对偶图是欧拉图。( ) 14．平面图的对偶图是连通图。( √ ) 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的强分图。 a b e 图1
解： （1） M=????????????????00010 1000000001 010******* M 2 =?? ?? ??? ? ??? ?????010******* 00010 1000001000 M 3=????????????????1000001000010000001010000 M 4=??????? ?????????0001001000100000100000010 由M 3可知，D 中长度等于3的通路有5条，长度等于3的回路有3条。 （2） I+M+M 2+M 3+M 4 =????????????? ???100000100000100 0001000001 +??????????? ?? ???000101000000001 010******* +??? ???? ? ??? ?? ???010000001000010 1000001000 + ????????????????1000001000010000001010000 +??? ?? ???????????0001001000100000100000010 = ??? ???? ? ????????21020 13010111110202011021 D 的可达性矩阵为 R=B （I+M+M 2+M 3+M 4 ）=??? ???? ? ????? ???110101********* 1101011011 （3）R T =????????????????11111 1111100100 1111100101 R×R T =??? ???? ? ??? ?????11010 11010 001001101000001 由矩阵R×R T 可知，该有向图的强分图有：{a}，{ b ，d ，e}， { c} a b e 图1
第二章 图的连通性 连通图：任二顶点间有路相连。 例 可见在连通图中，连通的程度也是有高有低。 本章的目的就是定义一种参数来度量连通图连通程度的高低。 §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 ===?=?，
习题三： ● 证明：是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意及, G 中的路必含. 证明：充分性: 是的割边，故至少含有两个连通分支，设是其中一个连通分支的顶点集，是其余分支的顶点集，对12,u V v V ?∈?∈，因为中的不连通，而在中与连通，所以在每一条路上，中的必含。 必要性：取12,u V v V ∈∈，由假设中所有路均含有边，从而在中不存在从与到的路，这表明不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 ： 是块，任取的一点，一边，在边插入一点，使得成为两条边，由此得到新图，显然的是阶数大于3的块，由定理，中的u,v 位于同一个圈上，于是 中u 与边都位于同一个 圈上。 ： 无环，且任意一点和任意一条边都位于同一个圈上，任取的点u ，边e ，若在上，则三个不同点位于同一个闭路，即位于同一条路，如不在上，由定理，的两点在同一个闭路上，在边插入一个点v ，由此得到新图，显然的是阶数大于3的块，则两条边的三个不同点在同一条路上。 ： 连通，若不是块，则中存在着割点，划分为不同的子集块,,,无环，12,x v y v ∈∈，点在每一条的路上，则与已知矛盾，是块。 ● 7.证明：若v 是简单图G 的一个割点，则v 不是补图的割点。 证明：是单图的割点，则有两个连通分支。现任取, 如果不在的
同一分支中，令是与 处于不同分支的点，那么，与在的补图中连通。若在的同一分支中，则它们在的补图中邻接。所以，若是的割点，则不是补图的割点。 ● 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给 出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）} ()25G κ= 最小点割{6,7,8,9,10} 2()5G λ= 最小边割{（2,7）…（1,6）} ● 13.设H 是连通图G 的子图，举例说明：有可能k(H)> k(G). 解： 通常. 整个图为，割点左边的图为的的子图， ，则. e H
第三章 匹配理论 §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 可扩展路。这与条件矛盾。 证毕。
电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k ≥2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。 图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3． 下列图中，是欧拉图的是（ D ） 4． 下列图中，不是哈密尔顿图的是（B ） 5． 下列图中，是可平面图的图的是（B ） A C D A B C D
6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。 解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8 分)求下图G 的色多项式P k (G). 解：用公式 (G P k -G 的色多项式： )3)(3)()(45-++=k k k G P k 。 六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。 解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 由上面两式可得：n 1=n 2+2n 3+…+(k -1)n k 七．证明：(8分) 设G 是具有二分类(X,Y)的偶图，证明(1)G 不含奇圈；（2）若|X | v v 1 3 图G
第1章 图论预备知识 1.1 解：(1) p={φ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} (2) p={,{a},{{b,c}},{a,{b,c}}} (3) p={,{}} (4) p={,{},{{}},{,{}}} (5)p={,{{a,b}},{{a,a,b}},{{a,b,a,b}},{{a,b},{a,a,b}},{{a,b},{a,b,a,b}},{{a,b},{a,a,b},{a,b,a,b}}} 1.2 解：(1) 真 (2) 假 (3)假 (4)假 1.3 解：(1) 不成立，A={1} B={1,2} C={2} (2) 不成立，A={1} B={1,2} C={1,3} 1.4 证明：设(x,y)∈(A ∩B)X(C ∩D) 说明x ∈A ∩B,y ∈C ∩D 由于 x ∈A,y ∈C 所以 (x,y) ∈A X C 由于x ∈B,y ∈D 所以 (x,y) ∈B X D 所以 (x,y) ∈（A X C ）∩（B X D ） 反过来，如果（x,y ）∈(A X C) ∩（B X D ） 由于 (x,y) ∈（A X C ）所以 x ∈A,y ∈C 由于 (x,y) ∈（B X D ）所以x ∈B,y ∈D 所以x ∈(A ∩B) y ∈(C ∩D) 所以 (x,y) ∈(A ∩B)X(C ∩D) 所以(A ∩B)X(C ∩D)= (A X C) ∩（B X D ） 1.5 解：Hasse 图 φφφφφφφφφ
极大元{9,24,10,7} 极小元{3,2,5,7} 最大元{24} 最小元{2} 1.6 解 (2)关系图为： (3)不存在最大元，最小元为{2} 1.7 解：(1)R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>} (2)略 (3)I A ?R 故R 是自反的。 <1,2>∈R <2,3>R 但是<1,3> ?R 故不满足传递性 1.8 解：(1) 不成立 A={1} B={2} C={3} D={4} 则左式={<1,3>，<1,4>,<2,3>,<2,4>} 右式={<1,3>,<2,4>} (2) 不成立 A={1,3} B={1} C={2,4} D={2} 则左式={<3,4>} 右式={<1,4>,<3,2>,<3,4>} (3) 不成立 A={1} B={2} C={3} D={4} 则左式={<1,3>,<1,4>,<2,3>,<2,4>} 右式={<1,3>,<2,4>} (4) 成立 证明：设
作业解答 练习题2 利用matlab编程FFD算法完成下题： 设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。 解答一： function [num,s] = BinPackingFFD(w,capacity) %一维装箱问题的FFD（降序首次适应）算法求解:先将物体按长度从大到小排序, %然后按FF算法对物体装箱 %输入参数w为物品体积，capacity为箱子容量 %输出参数num为所用箱子个数，s为元胞数组，表示装箱方案，s{i}为第i个箱子所装 %物品体积数组 %例w = [60,45,35,20,20,20]; capacity = 100; % num=3,s={[1,3],[2,4,5],6}; w = sort(w,'descend'); n = length(w); s = cell(1,n); bin = capacity * ones(1,n); num = 1; for i = 1:n for j = 1:num + 1 if w(i) < bin(j) bin(j) = bin(j) - w(i); s{j} = [s{j},i]; if j == num + 1 num = num + 1; end break; end end end s = s(1:num); 解答二： clear; clc; V=100; v=[60 45 35 20 20 20]; n=length(v); v=fliplr(sort(v)); box_count=1; x=zeros(n,n);
V_Left=100; for i=1:n if v(i)>=max(V_Left) box_count=box_count+1; x(i,box_count)=1; V_Left=[V_Left V-v(i)]; else j=1; while(v(i)>V_Left(j)) j=j+1; end x(i,j)=1; V_Left(j)=V_Left(j)-v(i); end temp=find(x(i,:)==1); fprintf('第%d个物品放在第%d个容器\n',i,temp) end output: 第1个物品放在第1个容器 第2个物品放在第2个容器 第3个物品放在第1个容器 第4个物品放在第2个容器 第5个物品放在第2个容器 第6个物品放在第3个容器 解答三： function box_count=FFD(x) %降序首次适应算法 v=100; x=fliplr(sort(x)); %v=input('请输入箱子的容积:'); n=length(x); I=ones(n); E=zeros(1,n); box=v*I; box_count=0; for i=1:n j=1; while(j<=box_count) if x(i)>box(j) j=j+1; continue; else
学号：201321010808 姓名：马涛 习题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的两个图是同构的。 6．设G 是具有m 条边的n 阶简单图。证明：m =???? ??2n 当且仅当G 是完全图。 证明 必要性 若G 为非完全图，则? v ∈V(G),有d(v)< n-1 ? ∑ d(v) < n(n-1) ? 2m 证明 由于G 为k 正则偶图，所以，k | V 1 | =m = k | V 2 | ? ∣V 1∣= ∣V 2 ∣。 12.证明：若δ≥2，则G 包含圈。 证明 只就连通图证明即可。设V(G)=｛v 1,v 2,…,v n ｝,对于G 中的路v 1v 2…v k ,若v k 与v 1邻接，则构成一个圈。若v i1v i2…v in 是一条路，由于δ≥ 2，因此，对v in ，存在点v ik 与之邻接，则v ik ?v in v ik 构成一个圈 。 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 中连通。 习题2 证明：每棵恰有两个1度顶点的树均是路。 证明：设树T 为任意一个恰有两个1度顶点的树，则T 是连通的，且无圈，令V 1 、V 2 为度为1的顶点，由于其他的顶点度数均为0或者2，且T 中无圈，则从V 1到V 2 有且只有一条连通路。所以，每棵恰有两个1度顶点的树均是路。得证。 证明：正整数序列),...,,(21n d d d 是一棵树的度序列当且仅当)1(21-=∑=n d n i i 。 证明：设正整数序列),...,,(21n d d d 是一棵树T 的度序列，则满足E d n i i 21 =∑=，E 为T 的边数，又有边数和顶点的关系1+=E n ，所以)1(21 -=?∑=n d n i i 证明：若e 是n K 的边，则3)2()(--=-n n n n e K τ。 若e 为Kn 的一条边，由Kn 中的边的对称性以及每棵生成树的边数为n-1，Kn 的所有生成树的总边数为：2)1(--n n n ，所以，每条边所对应的生成树的棵数 为： 32 2)1(2 1 )1(--=--n n n n n n n ，所以，K n - e 对应的生成树的棵数为： 332)2(2)(----=-=-n n n n n n n n e K τ Kruskal 算法能否用来求： 图论复习题答案 一、 判断题，对打√，错打 1．无向完全图是正则图。( √ ) 2．零图是平凡图。( )只有结点没有边的图称为零图 3．连通图的补图是连通图. ( ) 4．非连通图的补图是非连通图。( ) 5．若连通无向简单图G 中无圈，则每条边都是割边。( √ ) 6．若无向简单图G 是（n ，m ）图，并且m=n-1，则G 是树。( ) 连通 7．任何树都至少有2片树叶。( )平凡树 8．任何无向图G 都至少有一个生成树。( )连通 9．非平凡树是二分图 。( √ ) 无向图G 为二分图的充分必要条件是，G 至少有两个顶点, 且其所有回路的长度均为偶数。 10． 所有树叶的级均相同的二元树是完全二元树。( ) 11．任何一个位置二元树的树叶都对应唯一一个前缀码。( √ ) 12．3,3K 是欧拉图也是哈密顿图。( )欧拉图每个顶点度数是偶数 13． 二分图的对偶图是欧拉图。( ) 14．平面图的对偶图是连通图。( √ ) 15．设G*是平面图G 的对偶图，则G*的面数等于G 的顶点数。( ) 二、填空题 1．无向完全图K 6有 15 条边。 2．有三个顶点的所有互不同构的简单无向图有 4 个。 3．设树T 中有2个3度顶点和3个4度顶点，其余的顶点都是树叶，则T 中 有 10 片树叶。1.树m=n-1 2.握手定理 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 个面。 顶点数n-边数m+面数φ=2 三、解答题 1．有向图 D 如图1所示，利用D 的邻接矩阵及其幂运算 a b e2004图论复习题答案
相关主题
文本预览