图论习题参考答案.docx
《图论习题参考答案.docx》由会员分享，可在线阅读，更多相关《图论习题参考答案.docx（17页珍藏版）》请在冰点文库上搜索。
图论习题参考答案
二、应用题
题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,Ng（x）工［n/2］;
（2）对V的任一个子集S,只要S=［n/2］,S中有两个顶点相邻或V-S中有
两个顶点相邻。
需要证明G中有三个顶点两两相邻。
反证，若G中不存在三个两两相邻的顶点。
在G中取两个相邻的顶点Xi和yi,记Ng（xi）
={yi,y2,,yt}和NG（yi）={xi,X2,,Xk},贝UNg（xi）和NG（yi）不相交，并且Ng（xi）（NG（yi））中没有相邻的顶点对。
情况一；n=2r:
此时［n/2］=「，由（i）和上述假设，t=k=r且NG（yi）=V-Ng（xi），但Ng（xi）中没有相邻的顶点对，由
（2）,NG（yi）中有相邻的顶点对，矛盾。
情况二；n=2r+i:
此时［n/2］=r,由于Ng（xi）和NG（yi）不相交，t亠r,k",所以r+i亠t,r+i丄k。
若t=r+i,则k=r，即NG（yi）=r,Ng（xi）=V-NG（yi），由
（2）,Ng（xi）或NG（yi）中有相邻的顶点对，矛盾。
故kzr+i，同理r+i。
所以t=r,k=r。
记w^V-Ng（xi）UNG（yi）,由
（2）,w分别与Ng（xi）和NG（yi）中一个顶点相邻，设wxio，E,wyjo，E。
若Xioyjo・E,则w,Xio,yjo两两
相邻，矛盾。
若XioyoE，则与Xio相邻的顶点只能是（NG（xi）-{yjo}）U{w},与yjo相邻的顶点只能是（NG（yi）-{xjo}）U{w}o但与w相邻的点至少是3,故Ng（xi）UNG（yi）中存在一个不同于Xio和yjo顶点z与w相邻，不妨设乙Ng（Xi），则z,w,Xio两两相邻，矛盾。
题1:
已知图的结点集V={a,b,c,d}以及图G和图D的边集合分别为:
E（G）={（a,a）,（a,b）,（b,c）,（a,c）}
E（D）={,,,,}
解:
图G中：
deg（a）=4,deg（b）=2,deg（c）=2,deg（d）=O
图D中：
deg（a）=3,deg（b）=2,deg（c）=4,deg（d）=1图D是简单图.
其中deg+（a）=2,deg（a）=1,deg+（b）=0,deg（b）=2,deg+（c）=3,deg（c）=1,deg（d）=1.
为2.求G中有多少个结点.
题4无向完全图K3,K4,及3个结点的有向完全图
题5:
两个图同构有下列必要条件:
（1）结点数相同;
（2）边数相同;
（3）
度数相同的结点数相同
不同构.
到目前为止，判断两个图同构，只能根据定义，还没有其它简单而有效的方法
题6:
三名商人各带一随从乘船过河，一只小船只能容纳2人，由他们自己划行。
随从们密约,
在河的任一案，一旦随从的人数比商人多，就杀人越货。
但是如何乘船渡河的大权掌握在商人手中，商人们怎样安排每次乘船方案才能安全渡河？
解：
用图论模型求解如下:
每个状态有三个因素：
此岸构成，彼岸构成，船所在。
此岸albl,al为商人个数，bl为随从个数，al>bl,a1,b1=0,1,2,3，或a1=0,b1=0,1,2,3。
彼岸a2b2,a2为商人个数，b2为随从个数，a2>b2,a2,b2=0,1,2,3，或a2=0,b2=0,1,2,3。
注：
a1+a2=b1+b2=3;0表示船在此岸，1表示在彼岸。
可行状态有：
33|00|0,32|01|0,31|02|0,22|11|0,11|22|0,03|30|0,02|31|0,01|32|0,
00|33|1。
根据上图，求从33|00|0到00|33|1的路径，可得解如下：
33|00|0--31|02|1--32|01|0--30|03|1--31|02|0--11|22|1-22|11|0--02|31|1--03|30|0--01|32|1--02|31|0--00|33|1。
或：
33|00|0--31|02|1--32|01|0--30|03|1--31|02|0--11|22|1-22|11|0--02|31|1--03|30|0--01|32|1--11|22|0--00|33|1。
或：
33|00|0--22|11|1--32|01|0--30|03|1--31|02|0--11|22|1-22|11|0--02|31|1--03|30|0--01|32|1--11|22|0--00|33|1。
题7在平面上有n个点S={xi,x2,……,xn},其中任两个点之间的距离至少是1,证明在这
n个点中距离为1的点对数不超过3n。
证明首先建立一个图G=（V,E）,其中V就取S中的n个顶点，V中两个点有边相连当且仅当两点之间的距离恰好是1。
则所得图G是一个简单图，S中距离为1的点对数就是G的边数。
因此我们只需证明m（G）空3n。
我们考虑G中每个顶点的度，可以证明：
deg（Xi）乞6,i=1,2,……,n。
让Xi是G中的任一个顶点，且与Xi相邻的顶点为y1,y2,……,yk，贝Uy1,y2,……,yk分布在以Xi为圆心的单位圆周上。
所以k=deg（Xi）乞6,i=1,2,……,n。
由握手定理得
n
2m（G）='d山）乞6n
i±
故m（G）岂3n。
题8n个点由若干线段连接着。
已知每一点与另外任何一点都有道路相连通。
而任何两点都没有两种不同的道路。
证明：
线段总数为n-1。
证明构造图G:
将问题中给定的n个点作为顶点，线段作为边。
根据给定的条件，所得图G是含有n个顶点的简单图，每一对顶点之间有且只有一条路连接，因此G是连通图，并
且没有回路（否则，该回路上两个不同的顶点之间有两条不同的路），所以图G是一棵树。
题9:
设无向图G有12条边，已知G中度数为3的节点个数为6个，其余结点的度数均小于3,问G中至少有多少顶点？
解：
由定理可知，图中所有节点的度数之和应为边数的2倍，即12X2=24，却掉度数为3
的6个结点的总度数18,还剩6度，又由于其余结点的度数小于3,故度数只能是0,1,2,若其余结点的度数均为2，则至少需3个结点，故图G中至少有9个结点。
题10:
若图G是不连通的，则G的补图G是连通的。
证明：
设G=（V,E）不连通，则设其连通分支为G1,G2,…Gs，其相应的节点集为V1,
V2,…Vs,任取G中的两个节点u,v€V,
1）、若u,v分属于G中不同的连通分支，则（u,v）€G，因此u,v在G中连通。
_
2）、若u,v分属于G中同一个连通分支，则从另一连通分支中任取一结点w,则（u,w）€G,（v,w）€G，于是在G中存在一条道路uwv，使得u,v连通。
综上所述可知，对于G中任意2个结点，u,v总有路相连，故G是连通的。
题11：
当且仅当G的一条边e不包含在G的回路中，e才是G的割边（桥）。
证明：
必要性：
设e是连通图G的割边，e关联的两个结点为u和v。
若e包含在G的一个回路中，则除边e=（u,v）外还有一条以u,v为端点的道路，故删去边e后，G仍是连通的，这与e是割边矛盾。
充分性：
若e不包含在G的任一回路中，那么连接节点u和v只有边e,而不会有其他连接u和v的路，因为若连接u和v还有不同于边e的路，此路与边e就组成一个包含e的
题12：
n个城市由k条公路网络连接（一条公路定义为两个城市间的一条道路，它们之间不能通过任何中间城市），证明：
如果有
1
k>_（n-1）（n-2）
2
n个结点k
则人们总能通过连接城市的公路在任何城市间旅行。
证明：
将城市作为结点，将连接两个城市的公路作为边，则问题等价于证明具有
1
条边的简单无向图G,若满足k>_（n-1）（n-2），则是连通图。
当n=2时，结论显然成立，下
2
面证明n>2时，结论也成立。
假设G不连通，不妨设G有2个连通分支，则可将G中的结点集V分为两个子集V1和V2,
满足V1和V2分属于不同的连通分支。
设由V1生成的G的子图G1中有n1个结点k1条边，
设由V2生成的G的子图G2中有n2个结点k2条边，则
n1+n2=n，k1+k2=k，n1，n2_1
由于G是简单无向图，故G1和G2也是简单无向图，从而有：
11
k1_—n1（n1-1），k2_—n2（n2-1）
22
111
k>—（n1+n2-1）（n1+n2-2）=—n1（n1+n2-2）+—（n2-1）（n1+n2-2）
222
11
n1（n1-1）+—n2（n2-1）
22
与式
（1）矛盾，故G是连通图。
题13：
判断下图是否能一笔画出，并说明理由。
解：
图（a）中所有结点（除vo，Vn外）的度数为2或4，degv°=degvn=1，故有欧拉定理可知，图（a）包含欧拉通路，由V0出发到达Vn必有一条包含所有边且只包含一次的通路。
图（b）中所有结点（除vo,vn外）的度数为2或4,degvo=degvn=5,故有欧拉定理可知，图（b）包含欧拉通路，由vo出发到达Vn必有一条包含所有边且只包含一次的通路。
题14：
构造一个欧拉图，其结点数n与边数m满足下列条件
（1）、n，m的奇偶性一样的简单图。
（2）、n，m的奇偶性相反的简单图。
如果不可能，请说明原因。
2，是欧拉图，见
2，是欧拉图，见
解：
（1）、4个结点4条边，结点数和边数都是偶数，每个结点的度数均为下图（a）。
3个结点3条边，结点数和边数都是奇数，每个结点的度数为下图（b）。
（2）、6个结点9条边，3个结点的度数为2，3个结点的度数均为图（c）。
5个结点10条边，每个结点的度数为4,是欧拉图，见下图（
题15：
设G是一个具有n个结点的简单无向图，n_3,设G的结点表示n个人，G的边表示他们间的友好关系，若两个结点杯一条边连接，当且仅当对应的人是朋友。
（1）、结点的度数能做怎样的解释？
（2）、G是连通图能做怎样的解释？
（3）、假定任意两个人合起来认识所留下的n-2个人，证明n个人能站成一排，使得中间每个人两旁站着自己的朋友，而两端的两个人，他们每个人旁边只站着他的一个朋友。
（4）、证明对于n_4，（3）中保证n个人能站成一圈，使每个人的两旁站着自己的朋友。
解：
（1）、结点u的度数deg（u）表明u与deg（u）个人是朋友。
（2）、G是连通图表明任意两个人可通过其朋友及朋友的朋友结识，建立友好关系。
（3）、由已知任意两个人合起来认识其余的n-2个人，即对G中任意两个结点u，v，deg（u）+deg（v）亠n-2，且其余n-2个结点与u或v邻接。
若u与v邻接，则deg（u）+deg（v）_n-2+1=n-1。
若u与v不邻接，若deg（u）+deg（v）=n-2，则对于任意的w€V-{u,v}，w与u邻接（w与v邻接），但不能同时与u，v邻接，设w与u邻接，则w必不与v邻接，则结点w和u都不与v邻接，也就是w和u都不认识v，从而结点w和结点u的度数之和因此，deg（u）+deg（v）_n-1，即图G
中存在哈密顿通路，按照此通路的结点排列可得n个人排列成一排，使中间的每个人两边都
是朋友，而两端的两个人，一边站着的也是朋友。
（4）、由（3）可知，当n^3时，对G中任意两个结点u，v有，deg（u）+deg（v）兰n-1。
下面证明，当n_4时，deg（u）+deg（v）_n。
若u和v邻接，显然成立。
若u和v不邻接，则deg（u）+deg（v）>n-1，否则，若deg（u）+deg（v）=n-1，则V-{u,v}至少有2个结点（因n_4），设为w、t，且w与u，v均邻接，t只与u，v之一邻接。
设t与u邻接，则t和u与结点v都不邻接，与假设矛盾，故对任意结点u，v，deg（u）+deg（v）>n-1，即
deg（u）+deg（v）_n。
故图G中存在哈密顿回路，按照此回路的结点排列，即为所求的圈，满
足n个人能站成一圈，使每个人的两旁站着自己的朋友。
题16:
设G是有11个或更多结点的图，证明G或G（补图）是非平面图。
证明：
反证法：
设G和G都是平面图，设G和G的结点数分别为n和n，边数分别为m和m，贝U
1
n=n,m+m=—n（n-1）
2
由欧拉定理可知，
mm3n-6,m<3n-6
1
n（n-1）=m+mm3n-6+3n-6=6n-12
2
2
即n-13n+24乞0
从而得出*11,与n_11相矛盾，故G和G不可能同时为平面图，即n_11时，G或G（补
图）是非平面图。
题17：
一棵树有n2个结点度数为2,n3个结点度数为3，…，nk个结点度数为k，问它有几个度数为1的结点。
解:
设树T中有n1个度数为1的结点，则树中边数m为：
m=m+n2+n3+…+nk-1
又由于任意图中结点度数之和等于边数的2倍，故：
n1+2n2+3n3+…+knk=2（n1+n2+n3+…+nk-1）
故:
n1=（3-2）n3+（4-2）n4+…+（k-2）nk+2
题18:
证明在完全二叉树中，边的总数m等于2（nt-1）,nt是树叶总数。
证明：
对分枝结点数i用数学归纳法：
当i=1时，边数m=2，树叶数nt=2，故m=2（n“）成立。
假设i=k时（k_1）成立，下面证明i=k+1时结论成立。
由于树T是完全二叉树，因此T中必存在一分枝结点v,v的两个儿子v1,v2均是树叶。
在T中删去v1,v2得T'则T'是分枝结点数为k的完全二叉树，此时v为树叶，
分枝结点数i'=i-仁k+1-仁k
树叶数nt'=nt-2+仁nt-1
边数m'=m-2
由归纳假设，m'=2（nt'-1）
所以：
m-2=2（nt-1-1），即m=2（nt-1）。
题19：
给设d=（d1,d2,…,dn）,其中di为正数，i=1,2,…,n。
若存在n个结点的简单图，使得结点Vi的度数为di，则称d是可图解的。
下面给出的各序列中哪些是可图解的，哪些不是，为什么？
（1）、
（1,
1,
1,
2,
3）
（2）、
（0,
1,
1,
2,
3,
3）
（3）、
（3,3,
3,
3）
（4）、
（2,
3,
3,
4,
4,
5）
（5）、
（2,
3,
4,
4,
5）
（6）、
（2,3,
3,
3）
（7）、
（2,
3,
3,
4,
5,
6）
（8）、
（1,
3,
3,
4,
5,
6,6）
（9）、
（2,2,
4）
（10）、（1,2,2,3,4,5）
题20:
给无向完全图Kn（n》7）的各边随意涂上红色或绿色，若已知从某个结点v0引出
的n-1条边中至少有六条边涂红色，则存在红色的K4或绿色的K3。
证明：
设x1,x2,x3,x4,x5,x6是与v0相邻的六条边涂红色。
根据Ramsey（3，3）=6的证明可知，在x1,x2,x3,x4,x5,x6中，或有3个相互邻接的顶点（涂红色），这3个顶点与v0—起构成红色的K4;或者有3个互不相邻的顶点（绿色），这3个顶点构成绿色的K3。
题21:
证明：
在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。
证明：
此题可转化为图论的问题来处理：
把每个人对应成相应的结点，两个人具有朋友关系
当且仅当相应的结点相邻，显然该图是简单图，所以原命题等价于证明在该无向简单图中一定存在两个结点的度数相等。
反设，该无向简单图G中任何一对结点的度数都不相等，并设结点数为n。
又因为图G是简单图，所以结点的度数只能为：
0,1,2，…，n-1。
那么在图G中，存在度数为n-1的结点，与所有结点相邻，同时又存在度数为0的结点，
与所有结点都不相邻，因此产生矛盾。
所以该无向简单图中一定存在两个结点的度数相等。
所以在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。
题22、设G为n个结点的简单无向图。
（1）、若G的边数m=（1/2）（n-1）（n-2）+2，证明G是哈密尔顿图。
（2）、若G的边数m=（1/2）（n-1）（n-2）+1，那么图G是否一定为哈密尔顿图？
请阐述你的理由。
［分析］:
因为有定理：
设G=（V,E）是n阶（n》3）无向简单图，若对于任意的不相邻的结点Vi,Vj€V，有dev（vj+dev（vj）》n,贝UG是哈密尔顿图。
那么只要证明对任意的不相邻结点Vi,Vj€V，有dev（Vi）+dev（Vj）》n即可。
解：
（1）反证法：
假设存在不相邻的结点Vi,Vj€V，有dev（vi）+dev（vj）另V1={vi,Vj},G1=G-V1，则G1是（n-2）阶简单图，它的边数mj满足
m1=（1/2）（n-1）（n-2）+2-（dev（vi）+dev（vj））>（1/2）（n-1）（n-2）+2-（n-1）=（1/2）（n-2）（n-3）+1这与G1是（n-2）阶的简单图矛盾（注：
（n-2）阶的简单图的最大边数为（1/2）（n-2）（n-3））
所以G中任何两个相邻的结点度数之和均大于等于n。
再根据定理：
设G=（V,巳是n阶（n》3）无向简单图，若对于任意的不相邻的结点Vi,
vj€V，有dev（vi）+dev（vj）》n,贝UG是哈密尔顿图。
所以G是哈密尔顿图。
（2）若G的边数m=（1/2）（n-1）（n-2）+1，那么图G是不一定为哈密尔顿图，请看下图不是哈密尔顿图。
题23、把平面分成x个区域，每两个区域都相邻，问x最大为几？
（可作为选择题）
［分析］:
如果把每个区域放一个结点，当两区域相邻就在相应的两个结点间连一条边，这样就构造了一个简单和完全的平面图，类似于把平面区域图转化成对偶图来考虑。
解：
在每个区域放一个结点，当两区域相邻时就在相应的两个结点间连一条边，如此就构造
了一个平面图且是完全图Kx,而最大的平面完全图是K4,所以x最大为4。
注意：
根据平面图的常用定理，对于定点n\3的连通的简单的平面图G,有m<3n-6成立,其中n为结点数，m为边数，所以对于完全平面图Kn,其边数m=（1/2）n（n-1）。
要使3n-6,得n=3或4。
题24、设图G有n个结点，m条边，其中有m个结点的度数为k,其余结点的度数均为k+1,试证明：
nk=（k+1）n-2m。
解：
用握手原理容易得证。
题26、求出下图中以v1为起点的一条中国邮路。
1D
10
20
题28、求下面PERT图的关键路径。
T，并求出其W（T）。
题29、利用Huffman算法，求权为20,30,50,70,80的最优二叉树
解：
20,30,50,70,80〃50,50,70,80〃70,80,100〃100,150〃250〃
W（T）=550。
Huffman算法构造一棵最优
题30：
给定权1，4，9，16，25，36，49,64,81，100,利用
二叉树，并求出其W（T）。
题31、
用Dinic算法求下图最大流。
题32、
用2F标号算法求下图的最大流。
题33、用匈牙利算法求下图的最大匹配。
题34、对下图顶点进行着色。
题35：
、利用Dijkstra算法，求下图从1出发到其余各点的最短路径。
解:
步骤
V1
V2
V3
V4
V5
V6
1
0
19
30
OO
5
20
2
19
21
15
5v1
20
3
19
21
15/V5
20
4
19V1
21
20
5
21
20V1
6
21}V5
最终结果:
题36、现有4名教师：
张、王、李、赵，要求他们去教四门课程：
数学、物理、电工和计算机科学。
已知张老师能教数学和计算机科学，王老师能教物理和电工，李老师能教数学、物理和电工，而赵老师只能教电工。
如何安排才能使4位教师都能教课，并且每门课都有人教，共有几种方案？
升级会员 