资源描述：
《图论习题参考答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、二、应用题题0：（1996年全国数学联赛）有n（n6）个人聚会，已知每个人至少认识其中的[n/2]个人，而对任意的[n/2]个人，或者其中有两个人相互认识，或者余下的n-[n/2]个人中有两个人相互认识。证明这n个人中必有3个人互相认识。注：[n/2]表示不超过n/2的最大整数。证明 将n个人用n个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G。由条件可知，G是具有n个顶点的简单图，并且有（1）对每个顶点x，[n/2]；（2）对V的任一个子集S，只要＝[n/2]，S中有两个顶点相邻或V-S中有两个顶点相邻。需要证明G中有三个顶点两两相邻。反证，若G中不存在三
2、个两两相邻的顶点。在G中取两个相邻的顶点x1和y1,记NG(x1)＝{y1,y2,……,yt}和NG(y1)={x1,x2,……,xk},则NG(x1)和NG(y1)不相交，并且NG(x1)（NG(y1)）中没有相邻的顶点对。情况一；n=2r：此时[n/2]＝r，由（1）和上述假设，t=k=r且NG(y1)＝V-NG(x1)，但NG(x1)中没有相邻的顶点对，由（2），NG(y1)中有相邻的顶点对，矛盾。情况二；n=2r+1:此时[n/2]＝r，由于NG(x1)和NG(y1)不相交，tr,kr,所以r+1t,r+1k。若t=r+1,则k=r，即NG(y1)=r，NG(x1)＝V-NG
3、(y1)，由（2），NG(x1)或NG(y1)中有相邻的顶点对，矛盾。故k≠r+1，同理t≠r+1。所以t=r,k=r。记wV-NG(x1)∪NG(y1),由（2），w分别与NG(x1)和NG(y1)中一个顶点相邻，设wxi0E,wyj0E。若xi0yj0E，则w，xi0,yj0两两相邻，矛盾。若xi0yj0E，则与xi0相邻的顶点只能是(NG(x1)-{yj0})∪{w},与yj0相邻的顶点只能是(NG(y1)-{xj0})∪{w}。但与w相邻的点至少是3，故NG(x1)∪NG(y1)中存在一个不同于xi0和yj0顶点z与w相邻，不妨设zNG(x1)，则z，w，xi0两两相邻，矛盾
4、。题1：已知图的结点集V={a,b,c,d}以及图G和图D的边集合分别为：E(G)={(a,a),(a,b),(b,c),(a,c)}E(D)={,,,,}试作图G和图D，写出各结点的度数，回答图G、图D是简单图还是多重图？解ahhdahhdbhhcbhhc图G图D例2图：图G中：deg(a)=4，deg(b)=2，deg(c)=2，deg(d)=0图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
5、)=3,deg-(c)=1,deg-(d)=1.例3图题2：设简单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G中有多少个结点．试作一个满足该条件的简单无向图．解：设图G有x个结点，有握手定理2´1+2´2+3´4+3´（x-2-2-3）＝12´2x＝9图G有9个结点．图见例3图．（图不唯一）题3：设简单连通无向图G有9条边，G中有4个3度结点，2个1度结点，其余结点度数为2．求G中有多少个结点．题4无向完全图K3，K4，及3个结点的有向完全图.3个结点的有向完全图K3K4题5：两个图同构有下列必要条件：（1）结点数相同；（2）边数相同
6、；（3）度数相同的结点数相同.但它们不是两个图同构的充分条件，下图中(a)和(b)满足上述三个条件，但这两个图并不同构.(a)(b)到目前为止，判断两个图同构，只能根据定义，还没有其它简单而有效的方法.题6：三名商人各带一随从乘船过河，一只小船只能容纳2人，由他们自己划行。随从们密约，在河的任一案，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人手中，商人们怎样安排每次乘船方案才能安全渡河？解：用图论模型求解如下：l每个状态有三个因素：此岸构成，彼岸构成，船所在。l此岸a1b1，a1为商人个数，b1为随从个数，a1≥b1，a1,b1=0,1,2,3，或a1=0,b
7、1=0,1,2,3。l彼岸a2b2，a2为商人个数，b2为随从个数，a2≥b2，a2,b2=0,1,2,3，或a2=0,b2=0,1,2,3。l注：a1+a2=b1+b2=3；0表示船在此岸，1表示在彼岸。可行状态有：33
8、00
9、0，32
10、01
11、0，31
12、02
13、0，22
14、11
15、0，11
16、22
17、0，03
18、30
19、0，02
20、31
21、0，01
22、32
23、0，32
24、01
25、1，31
26、02
27、1，30
28、03
29、1，22
30、11
31、1，11
32、22
33、1，02
34、31
35、1，01
36、32
37、1，0
