图论习题参考答案

二、应用题题 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 中取两个相邻的顶点x1 和 y1 ,记 ng(x 1)y 1,y 2,y t和 n g(y 1)=x 1,x 2,x k,则 n g (x 1)和 ng(y 1 )不相交，并且ng (x 1)（ ng (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)和 ng(y 1)不相交，tr,kr,所以 r+1t,r+1k。若 t=r+1, 则 k=r ，即 ng (y 1)=r ，ng(x 1) v-n g(y 1)，由（ 2），n g(x 1 )或 ng(y 1)中有相邻的顶点 对，矛盾。故k r+1 ，同理 tr+1 。所以 t=r,k=r 。记 wv- n g(x 1 ) n g (y 1),由（ 2 ），w 分别与 n g(x 1 )和 ng (y 1)中一个顶点相邻，设wx i0e, wy j0e。若 x i0y j0e，则 w， x i0, y j0 两两相邻，矛盾。若xi0 yj0e，则与 xi0 相邻的顶点只能是(n g (x 1)-y j0 )w, 与 y j0 相邻的顶点只能是 (n g(y 1 )-x j0) w 。但与w 相邻的点至少是3，故 ng(x 1)n g(y 1 )中存在一个不同于xi0和 yj0 顶点 z 与 w 相邻，不妨设zn 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)=, , , , 试作图 g 和图 d，写出各结点的度数，回答图g、图 d 是简单图还是多重图？解：adadbcbc图 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 个结点，有握手定理精品资料例 3 图2 1+22+34+3（ x 2 23） 1223x24211827x 9图 g 有 9 个结点图见例 3 图（图不唯一）题 3： 设简单连通无向图g 有 9 条边， g 中有 4 个 3 度结点， 2 个 1 度结点，其余结点度数为 2 求 g 中有多少个结点题 4无向完全图k3 ， k4，及 3 个结点的有向完全图.精品资料k 3k 43 个结点的有向完全图题 5：两个图同构有下列必要条件：（1） ）结点数相同；（2） ）边数相同；（3） ）度数相同的结点数相同.但它们不是两个图同构的充分条件，下图中 (a) 和(b) 满足上述三个条件，但这两个图并不同构 .(a) (b)到目前为止，判断两个图同构，只能根据定义，还没有其它简单而有效的方法.题6 ：三名商人各带一随从乘船过河，一只小船只能容纳2人，由他们自己划行。随从们密约，在河的任一案，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人手中，商人们怎样安排每次乘船方案才能安全渡河？解：用图论模型求解如下：每个状态有三个因素：此岸构成，彼岸构成，船所在。此岸 a1 b1 ，a1 为商人个数， b1为随从个数， a1b1 ，a1,b1=0,1,2,3 ，或a1=0,b1=0,1,2,3 。彼岸 a2 b2 ，a2 为商人个数， b2为随从个数， a2b2 ，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|032|01|031|02|022|11|032|01|131|02|130|03|122|11|111|22|0精品资料11|22|103|30|002|31|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 x 1,x2 ,xn ，其中任两个点之间的距离至少是1，证明在这n 个点中距离为1 的点对数不超过3n。证明首先建立一个图g（ v ， e），其中 v 就取 s 中的 n 个顶点， v 中两个点有边相连当且仅当两点之间的距离恰好是1。则所得图g 是一个简单图，s 中距离为1 的点对数就是 g 的边数。因此我们只需证明m(g)3n 。我们考虑g 中每个顶点的度，可以证明：deg(x i)6,i=1,2,n。让 xi 是 g 中的任一个顶点，且与xi 相邻的顶点为y1 ,y2,yk，则 y1 ,y2,y k 分布在以xi 为圆心的单位圆周上。所以k= deg(x i)6 ,i=1,2,n。由握手定理得2m(g)=nd (vi )6ni 1故 m(g)3n 。题 8n 个点由若干线段连接着。已知每一点与另外任何一点都有道路相连通。而任何两点都没有两种不同的道路。证明：线段总数为n-1 。证明构造图g：将问题中给定的n 个点作为顶点，线段作为边。根据给定的条件，所得图 g 是含有 n 个顶点的简单图，每一对顶点之间有且只有一条路连接，因此g 是连通图， 并且没有回路 （否则， 该回路上两个不同的顶点之间有两条不同的路），所以图 g 是一棵树。题 9： 设无向图 g 有 12 条边，已知g 中度数为3 的节点个数为6 个，其余结点的度数均小于 3 ，问 g 中至少有多少顶点？解：由定理可知，图中所有节点的度数之和应为边数的 2 倍，即 12 x 2 =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， v s，任取 g 中的两个节点 u， vv ，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 条公路网络连接（一条公路定义为两个城市间的一条道路，它们之间不能通过任何中间城市），证明：如果有1k(n-1)(n-2)2则人们总能通过连接城市的公路在任何城市间旅行。证明：将城市作为结点，将连接两个城市的公路作为边，则问题等价于证明具有n 个结点 k1条边的简单无向图g，若满足 k(n-1)(n-2) ，则是连通图。当n=2 时，结论显然成立，下2面证明 n2 时，结论也成立。假设 g 不连通，不妨设 g 有 2 个连通分支， 则可将 g 中的结点集v 分为两个子集v 1 和 v2， 满足 v 1 和 v2 分属于不同的连通分支。设由v 1 生成的 g 的子图 g1 中有 n 1 个结点 k 1 条边， 设由 v 2 生成的 g 的子图 g2 中有 n 2 个结点 k 2 条边，则n1 +n 2=n ， k 1+k 2=k， n 1， n 21由于 g 是简单无向图，故g1 和 g2 也是简单无向图，从而有：1k1n 1(n 1 -1) ， k 2211n 2 (n 2-1)21k=k 1 +k 2n 1(n 1 -1)+2n2(n 2 -1)(1)2另一方面，由已知1k(n-1)(n-2)=21(n 1+n 2 -1)(n 1 +n 2-2)(2)2由于 n2 ，因此 n1 和 n 2 至少有一个大于等于2 ，不妨设n12，由 (2) 得1k(n 1+n 2 -1)(n 1+n 2-2)=211n 1(n 1 +n 2-2)+211(n 2 -1)(n 1 +n 2-2)2与式（ 1）矛盾，故g 是连通图。n1(n 1 -1)+2n 2 (n 2 -1)2题 13 ： 判断下图是否能一笔画出，并说明理由。v 0v n精品资料v 0v n图（ a）图（ b）解：图（ a）中所有结点（除v 0， vn 外）的度数为2 或 4， deg v 0 =deg v n = 1 ，故有欧拉定理可知，图（ a）包含欧拉通路，由v0 出发到达vn 必有一条包含所有边且只包含一次的通路。图（ b）中所有结点（除v 0， vn 外）的度数为2 或 4， deg v 0 =deg v n = 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 个结点的简单无向图，n3 ，设 g 的结点表示n 个人， g 的边表示他们间的友好关系，若两个结点杯一条边连接，当且仅当对应的人是朋友。（1） ）、结点的度数能做怎样的解释？（2） ）、g 是连通图能做怎样的解释？（3） ）、假定任意两个人合起来认识所留下的n-2 个人，证明n 个人能站成一排，使得中间每个人两旁站着自己的朋友，而两端的两个人，他们每个人旁边只站着他的一个朋友。（4） ）、证明对于n4 ，（ 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 ，则对于任意的wv-u,v ， w 与 u 邻接（ w 与 v邻接），但不能同时与u，v 邻接，设 w 与 u 邻接，则 w 必不与 v 邻接，则结点w 和 u 都不与 v 邻接，也就是w 和 u 都不认识v，从而结点w 和结点 u 的度数之和 n-1，否则，若 deg(u)+deg(v) =n-1，则 v-u,v 至少有2 个结点（因n4），设为 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 ，则n= n ， m+ m =由欧拉定理可知，1n(n-1)2m3n-6 ， m3n-61 n(n-1)= m+m3n-6+3n-6=6n-122即n 2 -13n+240从而得出n11 ， 与 n11 相矛盾，故 g 和 g 不可能同时为平面图，即 n11 时，g 或 g（补图）是非平面图。题 17 ： 一棵树有n 2 个结点度数为2， n 3 个结点度数为3 ， nk 个结点度数为k，问它有几个度数为1 的结点。解：设树 t 中有 n1 个度数为1 的结点，则树中边数m 为：m=n 1 +n 2+n 3+n k-1又由于任意图中结点度数之和等于边数的2 倍，故： n 1 +2n 2+3n 3+kn k=2(n 1+n 2 +n 3 +n k-1)故：n 1 = (3-2)n 3+(4-2)n 4+(k-2)n k+2题 18 ： 证明在完全二叉树中，边的总数m 等于 2(n t-1) ， nt 是树叶总数。证明：对分枝结点数i 用数学归纳法：当 i=1 时，边数 m=2 ，树叶数nt=2 ，故 m=2(n t-1) 成立。假设 i=k 时（ k1）成立，下面证明i=k+1 时结论成立。由于树 t 是完全二叉树，因此t 中必存在一分枝结点v， v 的两个儿子v1， v2 均是树叶。在 t 中删去 v1 ， v2 得 t，则 t 是分枝结点数为k 的完全二叉树，此时v 为树叶，分枝结点数i =i-1=k+1-1=k树叶数nt=n t-2+1=n t-1边数m =m-2由归纳假设，m =2(n t-1)所以：m-2=2(n t -1-1) ，即 m=2(n t-1) 。题 19 ：给设 d=（ d 1,d 2 ,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 一起构成红色的k 4；或者有 3 个互不相邻的顶点（绿色），这 3 个顶点构成绿色的k 3 。题 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，vjv，有 dev(v i)+dev(v j)n ，则 g 是哈密尔顿图。那么只要证明对任意的不相邻结点 vi ，vjv ，有 dev(v i)+dev(v j)n 即可。解：（ 1 ）反证法：假设存在不相邻的结点vi， vjv，有 dev(v i)+dev(v j)n-1 。另 v 1=v i， vj，g 1=g-v 1，则 g1 是（ n-2 ）阶简单图，它的边数m 1 满足m 1=(1/2)(n-1)(n-2)+2-(dev(vi)+dev(v j)(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 ，e ）是 n 阶（ n3 ）无向简单图，若对于任意的不相邻的结点vi，vjv，有 dev(v i)+dev(v j)n ，则 g 是哈密尔顿图。所以 g 是哈密尔顿图。（2 ）若 g 的边数 m=(1/2)(n-1)(n-2)+1，那么图g 是不一定为哈密尔顿图，请看下图不是哈密尔顿图。题 23 、把平面分成x 个区域，每两个区域都相邻，问x 最大为几？ （可作为选择题） 分析 ： 如果把每个区域放一个结点，当两区域相邻就在相应的两个结点间连一条边，这样就构造了一个简单和完全的平面图，类似于把平面区域图转化成