第八章图论方法
§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六个项目的比赛。表中打√的是各运动员报名参加的比赛项目。问六个项目的比赛顺序应如何安排，才能保证每名运动员都不连续地参加两项比赛。
解：把比赛项目作为研究对象，用点表示。如果两个项目有同一名运动员参加，就在代表这两个项目的点之间连成一条线，可得一图。在该图中只要找出一个点的序列，使依次排列的两个点间没有连线，就能保证每名运动员不会
连续参加两项比赛。例如，从图上可看出，按照A、C、B、F、E、D顺序安排比赛，即可满足要求。
书P136练习6.3
有十名研究生要参加六门课程的考试。由于选修的课程不同，考试门数也不一样。表6-4给出了每个研究生应参加考试的课程（打△号的）。规定考试应在三天内结束，每天上下午各安排一门。研究要求每人每天最多考一门，又课程A必须安排在第一天上午考，课程F安排在最后一门考，课程B只能安排在下午考试，试列出一个满足各方面要求的考试日程表。
表6-4
解：把考试课程作为研究对象，用点表示。如果两门课程有同一名研究生参加考试，就在代表这两门课程的点之间连成一条线，可得一图如下。
这个图就是练习6.3问题的图模型。在该图中第一天上午写入A，第三天下午写入F，因B课程与课程A和F有联系，故只能排入第二天下午，剩下的课程C、D、E要找出两个点间没有连线，例如，从图上可看出，按照A点与E 点间无连线，故E课程可排第一天下午，同理C、D课程安排第二天与第三天上午，即可满足要求。
§2 树和图的最小生成树
在各式各样的图中，有一类简单而且十分有用的图，即所谓树图（简称树，记作T（V，E））。树图就是无圈（即回路）的连通图。这类图与大自然中树的特征相似，因而得名为树图。铁路专用线、管理组织机构、学科分类往往都可以用树图的形式表示。例如，下面图（1）就是树图，而图（2）因为图中有圈（回路），所以它不是树；图（3）因为不连通，所以也不是树图。可见，树必须是连通的而且是不含圈的图。任一树图中的连线数一定比其点数少一。
V1 V1 V1 V8
V2 V3 V2 V3 V2 V9
V6
V5 V4 V4 V5 V3 V4
V8
V7 V6
V8 V9 V7 V5 V7图（1）图（2）图（3）
从一个给定的无向图G=（V，E）中，去掉图G中一些连线，保留图G中的所有点，所得的树图被称为图G的生成树。由一个图G可以生成若干树图，但不同生成树的连线总长度也是不同的，其中连线总长度最小的生成树就称为最小生成树。
§3 最小生成树的算法
求图的最小生成树问题就是在一个网络中，从一个起点出发到所有结点，找出一条或几条路线，构成线路总长度最小的一个树问题。
为了解决这个问题，我们用一个在住宅小区安装供水管道的例子来用说明求图的最小生成树的普赖姆算法。
图6-2是各座住宅楼之间可以安装供水管道的距离图，图中圆圈代表住宅楼，连线上的数字代表距离（以米为单位）。
图6-2 各座住宅楼之间可以安装供水管道的距离图
最小生成树的普赖姆算法就是把最近的未连接点连接到那些已经连接的结点上去，连接的方法如下：
1.从始点出发，我们来查找与始点1最近的结点，发现结点3与1的距离最近，为100米，于是把1——3连接好，见图6-3。
2.从已连接点1、3出发，查找与结点1、3最近的结点，发现结点4与1的距离最近，为300米，于是把1——4连接好，见图6-3。
3.从已连接点1、3、4出发，查找与始点1、3、4最近的结点，发现结点7与1的距离最近，为400米，于是把1——7连接好，见图6-3。
4. 从已连接点1、3、4、7出发，查找与始点1、3、4、7最近的结点，发现结点5与3的距离最近，为500米，于是把3——5连接好，见图6-3。
5.用同样的方法查到5与6的距离最近，为200米，7与2的距离最近，为900米，于是把5——6、7——2连接好，见图6-3。
必须指出：在查找与连接过程中，要避免出现回路，即圈（否则就不是要
求的树图），直到所有结点都被连接到起点为止。
图6-3 各座住宅楼之间供水管道的最小生成树
图6-3就是各座住宅楼之间供水管道的最小生成树。为了给各座住宅楼供水，总共需要2400米水管。
关于最小生成树问题，我们再举例一个例子如下：
已知连接5个城市的公路交通图6-4，图中连线旁边数字是距离（单位：公里）。现在要在这5个城市之间架设有线电视电缆，为了便于维修，要求电缆必须沿公路架设，而且电缆线的总长度要最少。
我们用普赖姆法（也称选线避圈法）计算如下：
1.开始时，从图选出最小的连线1——4，并将加粗，表示1、4点被连
接;
2.再从图选出次最小的连线1——5，并将加粗，表示1、5点被连接;
3.再从图选出第三最小的连线1——3，并将加粗，表示1、3点被连接，注意这里选择了连线1——3，而未选择连线4——5，是因为连线4——5与连线1——4、连线1——5构成了圈，有圈就不再是要求的树了，所以在选连线时，必须注意避免形成圈;
4.再从图选出第四个最小的连线2——3，并将加粗，表示2、3点被连接,至此最小生成树图已求得，如图6-5。其连线数一定比结点数少1。由所求最小生成树图可知架设的电缆线总长度为54公里。
图6-4 图6-5 网络图的最小生成树算法的应用范围十分广泛，凡是各地区之间架设输电线、电缆线、输油管道、修建上下水管道等等，都可应用这个算法，从而能规划出长度最小的网络。
又如书P137习题6.6：某公司有八口海上油井，相互间距离如表所示，单位：海里。1号井离海岸最近为4.8海里。问：从海岸经1号井铺设油管，把各油井连接起来，应如何铺设可使管道总长度最少（为便于计量和检修，油管只准在各井位处分叉连接）？
各油井间的距离（单位：海里）Array
解：依题意可得最小生成树如下：
§4最短路线问题
下面我们用例子来介绍最短路线问题。
例1 赵某是A市一家运输公司的卡车调度员。他的公司已经签订了一份运输合同，要把A市的一批货物运送到B市。赵某看了这个城市之间可以选择的行车路线，并绘制了下面的公路网络。图6-6中，圆圈也称结点，代表起点、目的地和途中要经过的其他城市。箭线代表各城市之间的公路，每条公路上标着里程。赵某的任务是找出从A市到B市的最短路线。
图6-6
一、最短路线的手工计算方法为：
1．从起点开始逐步向前推算：若经过结点2，因结点1到2只有一条路线，没有选择的余地，所以边1——2就是结点1到2的最短路线，其里程是100，将其写在结点2上方括号中。同理，在结点3、4上方标上175和150。
2．再看结点6，因到达结点6有两条路线可以选择，若选择边2——6到达结点6，其里程是100+300=400，若选择边4——6到达结点6，其里程是150+200=350，所以从起点1到达结点6的最短路线的里程是350，将其写在结点6上方括号中。同理，在结点5、7上方标上325和425。
3．再看结点9，因到达结点9有两条路线可以选择，若选择边6——9到达结点6，其里程是350+200=550，若选择边5——9到达结点9，其里程是325+400=725，所以从起点1到达结点9的最短路线的里程是550，将其写在结点9上方括号中。同理，在结点8上方标上550。
4．再看结点10，因到达结点6也有两条路线可以选择，若选择边9——
10到达结点10，其里程是550+100=650，若选择边9——10到达结点10，其里程是550+150=700，所以从起点1到达结点10的最短路线的里程是650，将其写在结点10上方括号中。
最后我们可以根据结点1到10的最短路线里程反向找出最短路线，见图6-7中加粗的箭线组成的路线1——4——6——9——10。
图6-7
求网络图的最短路线方法可以应用于公路运输、铁路运输、电缆架设、管道铺设以及企业设备更新等方面。
二、最短路问题的应用（见书P138习题6.10）
例2某人购买一台摩托车，准备在今后四年内使用。他可在第一年初购买一台新车连续使用四年，也可于任何一年年末卖掉，于下一年初换一台新车。已知各年初的新车购置价见表6-7。不同役龄车的年使用维护费及年末处理价见表6-8。要求确定此人使用摩托车的最优更新策略，使四年内用于购买、更换及使用维护的总费用为最省。
表6-8 单位：万元
例3 某公司在六个城市A、B、C、D、E、F设有分公司。各城市间的
求A城市到各城市间票价最低的航线。
答案：由表知从A到B、C、D、E、F票价最低的航线分别为：
A 10 F 25 B； A 25 E 20 C；A 25 E 10 F；
A 25 E；A 10 F 。
三、选址问题
选址问题通常是针对服务性单位或企业选择合适地址，如邮电局、洗浴中心、商场等地址的选择。选址问题的标准一般有两种。
（1）使所选地址到最远的服务对象距离尽可能小——中心点；
（2）使所选地址到各服务对象的总距离最小——中位点。
对于有时间限制的服务性单位或企业的选址问题多用中心点；对于有总资源限制的服务性单位或企业的选址问题多用中位点。
1．中心点选址
中心点选址的原则：位置在结点上，定点在距最远结点距离最近的结点。
确定中心点的方法是以结点到结点的最短距离为基础，按大中取小的原则确定。
例4 求下面网络图的中心点。图中数字为两个结点间的直接距离。
解：利用Excel规划求解，求出各结点到其他结点的最短距离，列出最短距离矩阵如下：
max
???????
?????????03
303
62
54
43601
32510244320 4min 46654??
?????? 利用最大最小原则确定中心点，可知其中心点为结点①或⑤。
2． 中位点选址 中位点选址的原则：位置在结点上，它到其他结点的最短距离的总和最小。 确定中位点的方法是以结点到结点的距离为基础，按某结点到其他结点最短距离的总和中取小原则确定。
例5 求图6-8的中位点。图中数字为两个结点间的直接距离。
解：利用Excel 规划求解，求出各结点到其他结点的最短距离，列出最短距离矩阵 如下：
sum
???????
?????????03
303
62
54
43601
32510244320 10min 1218131013??
???
???
按总和中取小原则确定中位点，可知其中心点为结点②。
§5 容量网络的最大流问题
在有一个起点和一个终点的网络中，求最大流量问题就是企图找出，在单位时间内，从起点出发，通过该网络到达终点的最大流量（它可以车流、液体、飞机等等）。
一、最大流量问题的手工算法
下面我们举一个实际例子来说明最大流量问题的算法。
例1 某市从北往南的交通，平时是利用有5号路通行，由于5号路要道路维修，有一个星期，车辆不能通行，因此交通管理部门需要计算在这个星期内，该市从北往南是否有把握每小时通过6000车辆，这些车辆在正常情况下是要利用5号路行驶的。
图6-8
图6-8中标出了穿过该市从北往南的几条路线，结点旁边的数字是该行车道上的车流容量（即每小时能通过的最大千车辆数）。
最大流量的手工算法
以图6-8为例，图中各条道路上每小时车辆流动能力依次为：
1——2线：6千辆; 1——3线：5千辆; 1——4线：3千辆;
2——5线：4千辆; 2——3线：7千辆; 3——5线：5千辆;
3——4线：3千辆; 4——6线：7千辆; 5——6线：2千辆。
1．任意选择从起点到终点的第一条路线。这里，选择路线1→2→5→6。我们用三个步骤来完成。首先，在1→2→5→6路线上找出允许流量最小的连线5→6，其最小流量能力为每小时2千辆，用2表示。这表明，5→6连线是这条路线上的瓶颈，沿1→2→5→6路线行驶的车辆，每小时最大车流量只能是2千辆。为此，在其中三条连线的终结点，即结点2、5、6处标上2（1），见图6-9，表示在第一条路线1→2→5→6上的流量能力为每小时2千辆汽车。然后，将路线1→2→5→6上每条连线的允许流量减去最小流量能力“2”，把差数写在相应连线的起始点处圆括号内，如，2→5点连线上的允许流量是“4”，则在点2处标出4（4-2），即4（2），其中（2）表示剩余流量能力为4。这样，在1→2、2→5、5→6三条连线的起始点1、2、5处标出6（4），4（2），2（0），见图6-9。
2．再选择从起点到终点的第二条路线。如1→4→6。同样，首先在该路线上找出流量能力最小的连线1→4，其最小允许流量为每小时3千辆，用3表示。然后按上述方法，在连线1→4，4→6的终结点4和6处均标出3（2），见图6-9，在连线1→4，4→6的起始点1和4处均标出3（0）和7（4），见图6-9。表示在第二条路线1→4→6上的流量能力为每小时3千辆汽车。
3．再选择从起点到终点的第三条路线。如1→3→4→6。同样，首先在该
路线上找出流量能力最小的连线3→4，其最小流量能力为每小时3千辆，用3表示。然后按上述方法，在连线1→3，3→4，4→6的终结点3、4、6处均标出3（3），见图6-9，在连线1→3，3→4，4→6的起始点1、3、4处均标出5（2），3（0）和7（4）（1），见图6-9。在连线4→6起始点4旁边标出7（4）（1），见图6-9，其中（4）是减去第二条路线的最小流量能力3后的第一次剩余流量能力为4，此时又减去第三条路线的最小流量能力3，其第二次剩余流量能力为1。所以我们在结点4旁边标出7（4）基础上，又标出了（1），见图6-9。第三条路线的流量能力也是每小时3千辆汽车。
4．从起点到终点已经找不到这样一条路线。在这条路线上，所有连线的流量能力全为正数。如在连线1→2→3→5→6上，连线1→2、2→3、3→5都还有流量能力4千辆、7千辆、5千辆，但在连线5→6上已无剩余的流量能力，导致这条路线的流量能力为0。
在这个交通网络中，成为瓶颈的连线还有1→4、3→4，要想提高整个网络的流量能力，就得改进这些薄弱环节的状况。
综上，我们已经求出了这个网络的最大流量：即第一条路线上的2千辆，第二条路线上的3千辆，第三条路线上的3千辆，共计为8千辆。计算结果表明，该市从北往南有把握每小时通过6千车辆。
计算网络最大流量问题，对规划铁路、公路的运输工作以及城市交通流量等方面都一定用途。
图6-9
注：1.对于多发点和多收点的容量网络问题，可以虚设一个发点和一个收
点再用上述方法求其最大流，求解过程中将虚设的发点和收点与原发点和收点之间的弧容量取无穷大。求解后再去掉虚设的发点和收点。
2.对于图中已经存在初始流的容量网络最大问题，可先不考虑其初始流，即去掉其初始来求其最大流，但要注意最大流可能并不是唯一的，而最大流量是相同的。如书上P132的例7。
例2 用标号法求下面网络图的最大流，图中弧旁数字为),(ij ij f c 。
图6-10
去掉图6-10中初始流后的容量网络图为图6-11.
图6-11
求得最大流如图6-12所示。
图6-12
最大流量为14单位。但最大流不唯一，因经调整还可得另一个最大流图6-13。
图6-13
二、最大流量问题的数学模型
例2 下面图6-14是某石油公司输油管道的一部分，该管道网络可把石油从开采地①输送到销售地⑦。图中每条弧上标出的数字就是容量（即单位时间内能通过的最大流量），单位：万加仑/小时。问从开采地①输送到销售地⑦每小时最多可送多少万加仑的成品油。
图6-14
设f ij 为弧（i,j ）是的流量，即单位时间内的实际通过量。v(f)为单位时间内的通过该网络上的总流量。则有
???????????≤≤
=+=++=+++=+=+=可行条件对所有弧平衡条件
)
(0)(max
674636573525363543234746431425
2312
1412ij
ij c f f f f f f f f f f f f f f f f f f f f f v
在该LP 模型中，前5个约束条件是中间结点平衡条件，每个中间点的流入应等于流出。而约束条件ij ij c f ≤≤0是每条弧必须满足的可行条件。我们把满足中间点平衡条件的每条弧可行条件的一组流{f ij }称为可行流（即上述LP 的可行解），使开采地①部流出量最大的可行流称为最大流（即上述LP 的最优解），最优目标函数值max v(f)是单位时间内的通过该网络上的最大流量。
一般的求网络最大流问题的数学模型可归结为：
()
???
?
?
????≥≤==
∑∑∑
===)
(0)()(max 1
11
1对所有弧对所有弧代表所有中间结点
ij ij ij n
j mj
n
i im n
j j
f c f m
f f f f v
实际中，网络流问题往往带有费用，若设通过弧（i,j ）的单位流量费用为b ij ，则求网络的最小费用流问题的数学模型为：
()
()???????????≥≤===∑∑∑∑∑=====)
(0
)(k min 111
11
1对所有弧对所有弧不能超过最大流量
，为指定发点发出的流量
代表所有中间结点
ij
ij ij n j j n
j mj
n
i im n
i n
j ij
ij
f c f k k f m
f f f b
F
三、网络最大流问题的计算机解法 以例2为例来说明计算机解法如下。
我们把图6-14中每条弧的容量ij c 代入模型用计算机求解，即在Excel 工作表上建立容量矩阵表（C ij ）、和变量（f ij ）表，如图6-15所示。
图6-15 容量矩阵表和变量表
将工作表的B11:H16区域作为可变单元格，在单元格I11中输入目标函数表达式“=SUMPRODUCT（B11 ：H11）”。
在单元格I12 ：I16中输入表示各结点流出量的表达式“=SUM（B12：H12）”，┄“=SUM（B16：H16）”，在单元格C17 ：G17中输入表示各结点流入量的表达式“=SUM（C11：C16）”，┄，“=SUM（G11：G16）”，添加约束条件后进行规划求解，“规划求解”对话框如图6-16所示。
图6-16 规划求解对话框
用Excel规划功能求解结果如图6-17所示。
图6-17 求解结果
即最大流方案为：
f12=5, f14=5, f23=2, f25=3, f35=2, f36=2,
f43=2, f46=1, f47=2, f57=5, f67=3,
最大流量为10万加仑。
练习：P139 习题6.13(C)或（D）
第八章图论方法 §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）}
第八讲图论中的匹配与逻辑推理问题 先看一个例题.中、日、韩三个足球队进行比赛，已知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中任意一点，不会
本系列共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构造一个新的二分图：
图论第一次作业 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个点的度数之和最大可能为
二、应用题 题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
习题三： ● 证明：是连通图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
电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：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
第二章 图的连通性 连通图：任二顶点间有路相连。 例 可见在连通图中，连通的程度也是有高有低。 本章的目的就是定义一种参数来度量连通图连通程度的高低。 §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 ===?=?，
第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 e 习题一 1. （题14）：证明图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的两个图是同构的。 2. （题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 ∣。 4. （题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 构成一个圈 。 5. （题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度顶点的树均是路。得证。 5、证明：正整数序列),...,,(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 14、证明：若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 τ 16、Kruskal 算法能否用来求： （1）赋权连通图中的最大权值的树？ （2）赋权图中的最小权的最大森林？如果可以，怎样实现？2004图论复习题答案
(完整版)图论及其应用1-3章习题答案(电子科大)
相关主题
文本预览