图论习题答案1

图论习题课作业1，3，6，8，10Byjgy•作业1：第一章：1,2,4,12,20,29,35•作业3：第二章：14,28,30第三章：1,5,7,8•作业6：第五章：18,33•作业8：第六章：6,12,17•作业10：第七章10第八章5,6,8作业1|E(G)|,2|E(G)|2G1.1举出两个可以化成图论模型的实际问题略1.2证明其中是单图证明：（思路）根据单图无环无重边的特点，所以最大的情形为任意两个顶点间有一条边相连，即极端情况为。•1.20证明每顶皆二次的连通图是圈•证明：（思路）易证每顶皆二次的连通图中有圈。设图中最大圈为H，假设除H外还有其他顶点集U，任取uk，因为连通，uk与H中任意顶均有一条道路，存在H中一顶hj与uk相邻，则hj为三次。•1.29证明二分图的子图是二分图•方法一：•定理1.2图G是二分图当且仅当G中无奇圈•反证：设二分图为G，子图为S，假设S非二分图，由定理1.2知S中有奇圈，则G中有奇圈，这与G是二分图矛盾。•方法二：•（思路）定义：V(G)=XUY,XnY=空,且X中任二顶不相邻，且Y中任二顶不相邻。•证明：•(a)第一个序列考虑度数7,第二个序列考虑6,6,2•(b)将顶点v分成两部分v’和v’’•v’={v|v=vi,1≤i≤k},•v’’={v|v=vi,kI≤n}•以v’点为顶的原图的导出子图度数之和小于•然后考虑剩下的点贡献给这k个点的度数之和最大可能为•2.14画出带权0.20.170.130.10.10.080.060.060.070.03的huffman树•排序：①0.030.060.060.070.080.10.10.130.170.2•②0.060.070.080.090.10.10.130.170.2•③0.080.090.10.10.130.130.170.2•④0.10.10.130.130.170.170.2•⑤0.130.130.170.170.20.2•⑥0.170.170.20.20.26•⑦0.20.20.260.34•⑧0.260.340.4•⑨0.40.60.030.060.090.030.060.090.060.070.130.030.060.090.060.070.130.170.08①③②0.030.060.090.060.070.130.170.080.10.10.20.130.26Huffman树为0.170.340.20.40.61•2.28证明T是顶数至少为2的树，则T是二分图•证明1：•定理1.2图G是二分图当且仅当G中无奇圈•T是树，所以T中无奇圈，由‘图G是二分图当且仅当G中无奇圈’知T是二分图。•证明2：•二分图定义。•考虑这样一种构造方法，从树根出发，树根结点放入顶集合X，树的第一层结点放入顶集合Y，树的第2K层结点放入X，树的第2K+1层结点放入Y。•2.30若G是加权连通图，且有一个长为m的圈C，C上的边的权相等，且是E(G)中边权最小的值，则G中至少有m棵不同的最优树，试加证明。•证明：思路：kruskal算法。圈C上必有m-1条边被选入，方法为𝐶𝑚𝑚−1=m.情况讨论。是等价的，没有必要分另，注意，这些边完全：画出即可hints。删去一条边皆是平面图与证明3.13,3K5K是一个自对偶平面图。条幅的轮时，）（从而又由欧拉定理，面数对偶图，则顶点数为自由于证明：顶自对偶图。构作一个自1-nW1422)(2)(2G)1(n,4,)2(2)(2)(对偶图，则为G若(1)nnGvGnNnGvG•5.对偶图的概念。自对偶图：平面图G与其对偶图同构。证明：不是平面图G从而,6)(3)(时，11当27313v得63）127（21解）127（21)(则6)(3)(又,2)1()()(证明：不是平面图G个，则11的顶点数不少于G若7.3c22cccccGvGvvvvvvGGvGvvGG假设有其它交点，如图AB与CD交于O，则有AO+COACBO+DOBD所以AC+BDAO+CO+BO+DO=2，与S中任两点距离至少为1矛盾，故得证对。6n3中至多S的顶对在1，则距离恰为1中任两点距离至少为S，3n，是平面上点组成的集合},...,,{8.321nxxxS面图）。点外没有其他交点（平下证Ｇ中任两边除了端.1距离为间，中相连以边当且仅当G在与Ｇ，为顶点集构造一个单图S证：以jijixxxx•5.18χ(G)+χ(𝐺𝑐)≤v+1,其中𝐺𝑐为G的补图•证明：数学归纳法。•假设v=k时成立，即χ(G)+χ(𝐺𝑐)≤v+1•下证v=k+1时成立，即χ(G)+χ(𝐺𝑐)≤v+2，在v=k的图中添加一点u，设u与图G顶相连个数为d(u),与𝐺𝑐相连为d’(u),下讨论d(u),d’(u).•①d(u)χ(G),•χ(G)=χ(G+u),同时χ(𝐺𝑐+u)≤χ(𝐺𝑐)+1，所以χ(𝐺𝑐+u)+χ(G+u)≤χ(G)+χ(𝐺𝑐)+1•②d’(u)χ(𝐺𝑐)，同①•③d(u)≥χ(G),d’(u)≥χ(𝐺𝑐)•d(u)+d’(u)≥χ(𝐺𝑐)+χ(G),又d(u)+d’(u)≤v•所以χ(𝐺𝑐+u)+χ(G+u)≤v+2•5.33求证：对G的任子图，α(H)≥1/2|V(H)|G是二分图α(H)：最大独立集顶的个数，独立数。•证明：①对G的任子图H,α(H)≥1/2|V(H)|=G是二分图•反证，设G不是二分图，则图中有奇圈H，则不满足α(H)≥1/2|V(H)|，矛盾。故G是二分图。•②G是二分图=对G的任子图H,α(H)≥1/2|V(H)|•G的任何子图H是二分图，V(H)=X’∪Y’，且X’∩Y’=空集。则X’或Y’为H的一个最大独立集，α(H)≥max{|X|,|Y|}≥1/2|V(H)|•6.6图6.24是不是hamilton图？为什么？•不是。•证明：定理6.4，G是hamilton的必要条件是任取S⊂V(G),S≠Φ,则w(G-S)≤|S|.•如图，删去途中圈出的三个点后，所得联通片的个数为4，•4≥|S|=3。•6.126.24是不是hamiltion图？为什么？•6.17证明：若u,vϵV(G)，u与v不相邻，且d(u)+d(v)≥|V(G)|，则G为Hamilton图的充分必要条件是G+uv是Hamilton图。•证明：①G为Hamilton图=G+uv是Hamilton图，显然。•②G+uv是Hamilton图=G为Hamilton图•反证矛盾。)v(d)u(这与1)V(d)V(即),u(1)v(d因而圈Hamilton的G是uv...vvvv...uv否则Evv则,Euv若:1i2（i若对于某个vv，uv其中,vv...uv轨Hamilton中有G这时1211-i21ii211-2vdvddvGGvvivvvuV1Vi-1Vv-1vVi•7.10证明：顶数不小于3的竞赛图中有得分相同的顶的充要条件是此图中有长为3的有向圈。•证明：顶数不小于3的竞赛图中，有得分相同的顶此图中有长3的有向圈。•①=反证，证得分相同但没有向圈。设得分相同的顶为u，v，考虑其它顶与u，v的关系，考虑四种关系，（省略），只有有向圈可以使uv比分持平。•②=假设没有得分相同的顶，则每顶得分必为1,2,……,n-1,可以看出得分为n-1的顶不会是长3的有向圈中的顶点，删除得分为n-1的顶，同理，继续删除剩下得分最多的顶，，直到最后三个顶也无圈。矛盾，所以一定有得分相同的顶。•8.5对于网络N{G,s,t,c(e)}，其中每个顶v(G)-{s,t}，有一个顶容量c(v)，即通过v的流量不得超过c(v)，c(v){0,1,2,…}，试为这种具有顶容量的网络设计一种从s到t的最大流量流函数的有效算法。•算法设计：•思路对于网络N{G,s,t,c(e)}，其中每个顶vi属于(G)-{s,t}可用含有两个顶的边vi’vi’’替代，且vi’vi’’的容量c(vi’vi’’)=c(vi).再用2F算法。•8.6写出一个算法确定其容量c(e)增大时，N(G,t,t,c(e))中的对大流量亦增大的边，这种边一定有吗？•解题思路：•1）用2F算法标记所有顶点，找出其中所有f(e)=c(e)的边集合E•2）增大E中任一边的c(e),再用2F算法，如果最大流增大了，则找到了要找的边•3）如果E中所有边均不满足2），则找不到。•不一定有，举个反例。•8.8图8.16哪个网络没有可行流？