《图论与代数结构》(戴一奇-清华大学出版社)习题解答

习题一1.一个工厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；这样就得到一个无向图。若每点的度数为3，则总度数为27，与图的总度数总是偶数的性质矛盾。若仅有四个点的度数为偶数，则其余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是偶数的性质矛盾。2.若存在孤立点，则m不超过Kn-1的边数,故m=(n-1)(n-2)/2,与题设矛盾。3.4.用向量(a1,a2,a3)表示三个量杯中水的量,其中ai为第i杯中水的量,i=1,2,3.以满足a1+a2+a3=8(a1,a2,a3为非负整数)的所有向量作为各结点,如果(a1,a2,a3)中某杯的水倒满另一杯得到(a’1,a’2,a’3),则由结点到结点画一条有向边。这样可得一个有向图。本题即为在此图中找一条由(8,0,0)到(4,4,0)的一条有向niiniininininiiiniiniiiiaannaaannnanavv1111121212/)1()1(2)1(])1[(。，　所以　　因为　　，＋　　　的负度数，则为结点的正度数，为结点记－－－－－22222iiCaa路，以下即是这样的一条：5.可以。7.同构。同构的双射如下：vV1V2V3V4V5V6f(v)bacedfV1V3V2V5V4V6V1V2V4V3V6V5(8,0,0)(5,3,0)(5,0,3)(2,3,3)(2,5,1)(7,0,1)(7,1,0)(4,4,0)(4,1,3)8.记e1=(v1,v2),e2=(v1,v4),e3=(v3,v1),e4=(v2,v5),e5=(v6,v3),e6=(v6,v4),e7=(v5,v3),e8=(v3,v4),e9=(v6,v1),则邻接矩阵为：关联矩阵为：边列表为：A=(1,1,3,2,6,6,5,3,6),B=(2,4,1,5,3,4,3,4,1).正向表为：A=(1,3,4,6,6,7,10),B=(2,4,5,1,4,3,3,4,1).习题二1.用数学归纳法。k=1时，由定理知结论成立。设对于k命题成立。对于k+1情形，设前k个连通支的结点总个数为n1,则由归纳假设，前k个连通支的总边数m1=(n1－k+1)(n1－k)/2。最后一个连通支的结点个数为n－n1,其边数m2=(n－n1)(n－n1－1)/2，100110000001001000010100010011010100000001001100000111,001101000100000000001001010000001010所以，G的总边数m=m1+m2=(n1－k+1)(n1－k)/2+(n－n1)(n－n1－1)/2n1=n－1时，m=((n-1)－k+1)((n-1)－k)/2+0=((n－k)((n－k－1)/2,命题成立。n1＜=n－2时，由于n1=k,故m=((n－2)－k+1)(n1－k)/2+(n－n1)(n－k－1)/2＝(n－k)(n－k－1)/2,命题成立。2．若G连通，则命题已成立；否则，G至少有两个连通支。任取结点v1,v2，若边(v1,v2)不在中，则v1,v2在G的同一个连通支（假设为G1）中。设G2是G的另一连通支，取v3G2,则v1v3v2是中v1到v2的一条道路，即结点v1,v2在中有路相通。由v1,v2的任意性，知连通。3．设L1,L2是连通图G的两条最长路，且L1,L2无公共结点。设L1,L2的长度(边数)为p.由于G是连通的，故L1上必有一结点v1与L2上一结点v2有道路L’相通。结点v1将L1分为两部分，其中一部分的长度p/2,记此GGGGG部分道路为L3。同样，结点v2将L2分为两部分，其中一部分L4的长度p/2。这样，L3＋L’＋L4就是G的一条新的道路，且其长度大于p,这与G的最长路(L1)的长度是p的假设矛盾。4.对结点数n作归纳法。（1）n=4时m≥5.若有结点的度≤1,则剩下的三结点的度数之和≥4，不可能。于是每个结点的度≥2，从而存在一个回路。若此回路为一个三角形，则还有此回路外的一结点，它与此回路中的结点至少有二条边，从而构成一个新的含全部四个结点的回路，原来三角形中的一边（不在新回路中）即是新回路的一条弦。若此回路为含全部四个结点的初等回路，则至少还有一边不在回路上，此边就是该回路的一条弦。（2）设n-1情形命题已成立。对于n情形：若有结点的度≤1,则去掉此结点及关联边后，依归纳假设命题成立。若有结点v的度=2,设v关联的两结点为s,t，则去掉结点v及关联边、将s,t合并为一个结点后，依归纳假设命题成立。若每个结点的度≥3，由书上例2.1.3的结果知命题成立。6．问题可化为求下列红线表示的图是否存在一条欧拉道路的问题：存在欧拉道路！8．由推论2.4.1,只需验证G的任意一对结点的度数之和大于或等于n即可。若存在结点v1,v2满足deg(v1)+deg(v2)n,则G－{v1,v2}的边数=Kn-2的边数=(n-2)(n-3)/2.另一方面，由题设知G－{v1,v2}的边数＝m－（deg(v1)+deg(v2)）＞[(n-1)(n-2)/2+2]－n=(n-2)(n-3)/2,与上式矛盾。13．1）将边按权值由小到大排序：边：a23a35a15a13a34a45a24a12a25a14权：262729333435384249522)分支定界：S1:a23a35a15a13a34,非H回路,d(S1)=149;将a34置换为其后的a45,a24，a12，a25，a14，也全都是非H回路；S2:a23a35a15a34a45,非H回路,d(S2)=151;将a45置换为其后的a24，a12，a25，a14，也全都是非H回路；S3:a23a35a15a45a24,非H回路,d(S8)=155;将a24置换为其后的a12，a25，a14，也全都是非H回路；S4:a23a35a15a24a12,非H回路,d(S4)=162;S5:a23a35a15a24a25,非H回路,d(S5)=169;S6:a23a35a15a24a14,H回路,d0:=172;S7:a23a35a15a12a25,非H回路,d(S7)=173;S8:a23a35a13a34a45,非H回路,d(S8)=155;将a34,a45置换为其后的数，也全都是非H回路；S9:a23a35a34a45a24,非H回路,d(S9)=160;将a45,a24置换为其后的数，也全都是非H回路；S10:a23a35a45a24a12,非H回路,d(S10)=168;将a12置换为其后的a25,a14，也全都是非H回路；S11:a23a35a45a12a25,非H回路,d(S11)=179;将a12,a25置换为其后的数，其路长差于d0，故不必考虑；S12:a23a35a24a12a25,非H回路,d(S12)=182;将a24，a12，a25,置换为其后的数，其总长差于d0，故不必考虑；继续下去所得组长度会比S6差，故可终止计算。所以，H回路为S6,路长为172。14.这是一个旅行商问题(具体计算略)：(0,0)(2,5)(6,6)(9,3)(8,9)7951017125671215.这是一个最短路问题(具体计算略)：16.5+35+65+178+17+16+15+15+15+115+115+35+66+66+37+3V1V2V3V5V4254298452V6V3V2V1V5V432921485329V3V2V6V4V1V5333627343023.习题三1．因为n个结点的树的边有n-1条，故其总度数为2(n-1)，故度为1的结点个数为2(n-1)－2n2－3n3－……－knk.2.设L是树T的一条最长路，L中的结点依次为v1,v2,…,vk。因为L中各结点都有边相连，所以它们的度数均大于或等于1。若deg(v1)1,则除了边(v1,v2)外，还存在边(v1,v’)。因为树中不存在回路，故v’{v1,v2,…,vk}，于是，(v’,v1,v2,…,vk)是T的一条新的路，其长度比L更长。这与L是T的最长路矛盾。所以deg(v1)＝1，类似可证deg(vk)＝1。4．(a)直接根据图确定B5B5T可得树的棵数：.1014201241001411013)det(55TBB(b)去掉边(v1,v5)，则直接根据图确定B5B5T可得不含边(v1,v5)的树的棵数：,754201241001411012)det(55TBB于是，含边(v1,v5)的树的棵数为：101－75＝26。(c)去掉边(v4,v5)，则直接根据图确定B5B5T可得不含边(v1,v5)的树的棵数：.603201241001411013)det(55TBB5.(a)因为,0000010010100100010001100010000000100001,1100110010101100010001110010000000111001*11BB(b)去掉边(v1,v5)后，有,000001000100100010011000100000010001,110011000101100010011100100000011101*11BB..2420011310113110021)Bdet(BT1*1为根的根树的个数为因此以v..81001131011311002),(1)Bdet(BT1*151的根树的个数为为根且不含边因此以vvv(c)去掉到v3的其它全部边(v4,v3)、(v5,v3)后，有,00010010110001000000100000100001,10110010110001000100100000111001*11BB10.(1)余树为｛e1,e2,e5,e8｝,重排B5的各列得..92001131000111002),(321)Bdet(BT1*1的根树的个数为为根且含边因此以vvv.1000010000100001CICeeeeeeee,C3.4.4,,01-0000011-01011-00B,1-0001-01001-010011-B,)BB(01-0000011-01011-001-0001-01001-010011-eeeeeeeef12f7643851f121211121176438511001001011001111)(10010010110011111001100010110100100010100101001121121152基本回路矩阵为由定理则　＝TTBBB(2)由定理3.4.8,基本割集矩阵为.10000100001000011011-0011-01011-001IC-ISSeeeeeeeeTf12f11f7643851)()(214．(a)这是一个求最优二叉树的问题。各字符出现次数为：staec空格345114余树树T4482355所以最优二进制编码为：e:1100c:1101s:111t:00空格：01a:10此时字符串的二进制编码总长度为43.(b)去掉空格，类似(a)计算。1124435445112354481123551011235510448180100