图论习题参考答案

二、应用题题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，)(xNG[n/2]；（2）对V的任一个子集S，只要S＝[n/2]，S中有两个顶点相邻或V-S中有两个顶点相邻。需要证明G中有三个顶点两两相邻。反证，若G中不存在三个两两相邻的顶点。在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)不相交，tr,kr,所以r+1t,r+1k。若t=r+1,则k=r，即NG(y1)=r，NG(x1)＝V-NG(y1)，由（2），NG(x1)或NG(y1)中有相邻的顶点对，矛盾。故k≠r+1，同理t≠r+1。所以t=r,k=r。记wV-NG(x1)∪NG(y1),由（2），w分别与NG(x1)和NG(y1)中一个顶点相邻，设wxi0E,wyj0E。若xi0yj0E，则w，xi0,yj0两两相邻，矛盾。若xi0yj0E，则与xi0相邻的顶点只能是(NG(x1)-{yj0})∪{w},与yj0相邻的顶点只能是(NG(y1)-{xj0})∪{w}。但与w相邻的点至少是3，故NG(x1)∪NG(y1)中存在一个不同于xi0和yj0顶点z与w相邻，不妨设zNG(x1)，则z，w，xi0两两相邻，矛盾。题1：已知图的结点集V={a,b,c,d}以及图G和图D的边集合分别为：E(G)={(a,a),(a,b),(b,c),(a,c)}E(D)={a,b,a,c,c,d,c,a,c,b}试作图G和图D，写出各结点的度数，回答图G、图D是简单图还是多重图？解：adadbcbc图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)=3,deg-(c)=1,deg-(d)=1.题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2271821243xx＝9图G有9个结点．图见例3图．（图不唯一）题3：设简单连通无向图G有9条边，G中有4个3度结点，2个1度结点，其余结点度数为2．求G中有多少个结点．题4无向完全图K3，K4，及3个结点的有向完全图.题5：两个图同构有下列必要条件：（1）结点数相同；（2）边数相同；（3）度数相同的结点数相同.但它们不是两个图同构的充分条件，下图中(a)和(b)满足上述三个条件，但这两个图并不同构.(a)(b)例3图K3K43个结点的有向完全图到目前为止，判断两个图同构，只能根据定义，还没有其它简单而有效的方法.题6：三名商人各带一随从乘船过河，一只小船只能容纳2人，由他们自己划行。随从们密约，在河的任一案，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人手中，商人们怎样安排每次乘船方案才能安全渡河？解：用图论模型求解如下：每个状态有三个因素：此岸构成，彼岸构成，船所在。此岸a1b1，a1为商人个数，b1为随从个数，a1≥b1，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，32|01|1，31|02|1，30|03|1，22|11|1，11|22|1，02|31|1，01|32|1，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。33|00|032|01|031|02|022|11|011|22|003|30|002|31|001|32|032|01|131|02|130|03|122|11|111|22|102|31|101|32|100|33|1题7在平面上有n个点S＝{x1,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，则y1,y2,……,yk分布在以xi为圆心的单位圆周上。所以k=deg(xi)6,i=1,2,……,n。由握手定理得2m(G)=niivd1)(6n故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的回路，从而导致矛盾，所以，删去边e后，u和v就不连通，故边e为割边。题12：n个城市由k条公路网络连接（一条公路定义为两个城市间的一条道路，它们之间不能通过任何中间城市），证明：如果有k21(n-1)(n-2)则人们总能通过连接城市的公路在任何城市间旅行。证明：将城市作为结点，将连接两个城市的公路作为边，则问题等价于证明具有n个结点k条边的简单无向图G，若满足k21(n-1)(n-2)，则是连通图。当n=2时，结论显然成立，下面证明n2时，结论也成立。假设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也是简单无向图，从而有：k121n1(n1-1)，k221n2(n2-1)k=k1+k221n1(n1-1)+21n2(n2-1)(1)另一方面，由已知k21(n-1)(n-2)=21(n1+n2-1)(n1+n2-2)(2)由于n2，因此n1和n2至少有一个大于等于2，不妨设n12，由(2)得k21(n1+n2-1)(n1+n2-2)=21n1(n1+n2-2)+21(n2-1)(n1+n2-2)21n1(n1-1)+21n2(n2-1)与式（1）矛盾，故G是连通图。题13：判断下图是否能一笔画出，并说明理由。图（a）图（b）解：图（a）中所有结点（除v0，vn外）的度数为2或4，degv0=degvn=1，故有欧拉定理可知，图（a）包含欧拉通路，由v0出发到达vn必有一条包含所有边且只包含一次的通路。V0VnVnV0图（b）中所有结点（除v0，vn外）的度数为2或4，degv0=degvn=5，故有欧拉定理可知，图（b）包含欧拉通路，由v0出发到达vn必有一条包含所有边且只包含一次的通路。题14：构造一个欧拉图，其结点数n与边数m满足下列条件（1）、n，m的奇偶性一样的简单图。（2）、n，m的奇偶性相反的简单图。如果不可能，请说明原因。解：（1）、4个结点4条边，结点数和边数都是偶数，每个结点的度数均为2，是欧拉图，见下图（a）。3个结点3条边，结点数和边数都是奇数，每个结点的度数为2，是欧拉图，见下图（b）。（2）、6个结点9条边，3个结点的度数为2，3个结点的度数均为4，是欧拉图，见下图（c）。5个结点10条边，每个结点的度数为4，是欧拉图，见下图（d）。（a）（b）（c）（d）题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是连通图表明任意两个人