图论与代数结构第一二三章习题解答.doc

习题一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 )的一条有向路，以下即是这样的一条：( 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 )5. 可以。

V1V3V2V5V4V6V1V2V4V3V6V56 若9个人中没有4个人相互认识，构造图G，每个点代表一个点，两个人相互认识则对应的两个点之间有边1） 若可以找到点v，d(v)>5，则与v相连的6个点中，要么有3个相互认识，要么有3个相互不认识（作K6并给边涂色:红=认识，蓝=不认识，只要证图中必有同色三角形v1有5条边，由抽屉原则必有三边同色(设为红)，这三边的另一顶点设为v2, v3, v4若 △v2v3v4有一边为红，则与v1构成红色△，若△v2v3v4的三边无红色，则构成蓝色△）若有3个人相互认识，则这3个人与v相互认识，这与假设没有4个人相互认识矛盾，所以这6个人中一定有3个人相互不认识请预览后下载！2） 若可以找到点v，d(v)<5，不与v相连的点至少有4个，由于没有4个人相互认识，所以这4个人中至少有2个人相互不认识，这两个人与v共3个人相互不认识3） 若每个点的度数都为5，则有奇数个度数为奇数的点，不可能7. 同构同构的双射如下：　　 vV1V2V3V4V5V6f (v)bacedf8. 记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，所以，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，若G的补图中边(v1, v2)不存在，则(v1, v2)是G中边，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 , 记此部分道路为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的结果知命题成立5 a)对于任意边(u,v),由于不存在三角形，所以d(u)+d(v)<=n，对所有m条边求和，不等式左边每个d(v)被计算了d(v)次请预览后下载！b) 对n归纳，设小于n时不等式成立，当|V|=n时，删去边(u,v)及点u，v以及相关的边得到G'，由归纳假设，G'最多(n-2)2/4条边，由于(u,v)与G'不构成三角形，因此由G'变回G时最多增加(n-2)+1条边，所以G的边最多(n-2)2/4+(n-2)+1=n2/4注：此题与三角形的存在性无关设最大度数为k，且d(v)=k，令E0={与v相连的边}，E1={不与v相连的边}，则|E0|=k，|E1|<=(n-k-1)*k，其中n-k-1表示去除了v及其邻点，这些点的度数都小于等于km=|E0|+|E1|<=nk-k2<= n2/46．问题可化为求下列红线表示的图是否存在一条欧拉道路的问题：存在欧拉道路！7 设C是H道路，当S中顶点在C上不相邻时，C-S最多被分成|S|+1段，而当S中顶点有相邻时段数将更少，而C是G的生成子图，所以t<=|S|+18．由推论2.4.1, 只需验证G的任意一对结点的度数之和大于或等于n即可。

　　若存在结点v1, v2满足　deg(v1)+deg(v2)=2(n-2)，当n>=4时，2(n-2)>=n所以对任意两个点度数和大于等于n11 对于这q条边，每条边的两个端点压缩合并为一个点，并去掉重边得到G'G'各点度数均大于等于n/2，所以存在H回路，该回路中q个新点恢复成原2q个点，则所代表的q条边仍在此H回路中注：q不能超过n/212 构造图G，每个小立方体对应一个点，两个立方体之间有公共面则对应顶点间有边设最左上角点为黑色，依据相邻点不同色的原则给所有点着色，则黑色点有14个，白色点有13个，若所要求路径存在，则意味着从黑色点开始遍历这27个点到达白色点，这不可能13．1）将边按权值由小到大排序：边： a23 a35 a15 a13 a34 a45 a24 a12 a25 a14权： 26 27 29 33 34 35 38 42 49 52 2)　分支定界： S1: a23 a35 a15 a13 a34 , 非H回路,d (S1)=149;将a34置换为其后的a45, a24，a12，a25，a14，也全都是非H回路； S2: a23 a35 a15 a34 a45, 非H回路,d(S2)=151;　　将a45置换为其后的a24，a12，a25，a14，也全都是非H回路； S3: a23 a35 a15 a45 a24 , 非H回路,d (S8)=155;将a24置换为其后的a12，a25，a14，也全都是非H回路；S4: a23 a35 a15 a24 a12 , 非H回路,d (S4)=162;S5: a23 a35 a15 a24 a25 , 非H回路,d (S5)=169;S6: a23 a35 a15 a24 a14 , H回路,d0:=172;S7: a23 a35 a15 a12 a25 , 非H回路,d (S7)=173;S8: a23 a35 a13 a34 a45 , 非H回路,d (S8)=155;将a34 , a45置换为其后的数，也全都是非H回路；S9: a23 a35 a34 a45 a24 , 非H回路,d (S9)=160;将a45 , a24置换为其后的数，也全都是非H回路；S10: a23 a35 a45 a24 a12 , 非H回路,d (S10)=168;将a12置换为其后的a25 , a14，也全都是非H回路；S11: a23 a35 a45 a12 a25 , 非H回路,d (S11)=179;将a12 ,a25置换为其后的数，其路长差于d0，故不必考虑；S12: a23 a35 a24 a12 a25, 非H回路,d (S12)=182;将a24 ，a12 ，a25,置换为其后的数，其总长差于d0，故不必考虑； 继续下去所得组长度会比S6差，故可终止计算。

请预览后下载！　　　所以，H回路。