图论大作业.doc

图论及其应用大作业指导老师 郝荣霞知行1503 徐鹏宇 15291200第一题（讲过）2.1.9证明：若G是森林且恰有2k个奇点，则在G中有k条边不重的路P1,P2.PK,使得E(G)=E(P1)E(P2).E(PK)。证明：对奇点数k使用数学归纳法。当k=1时，G是森林，且有且只有2个奇点G只能为一颗树，且G的所有奇度顶点为两个1度顶点G是一条路满足题设假设当k=t时，结论成立。接下来考虑k=t + 1时的情况。在G中一个分支中取两个叶子点u与v，令P是连接该两个顶点的唯一路。由于P上除u，v以外的点均被P经过两次，即G-P后除u，v以外的点奇偶性不变。则GP是有2t个奇度顶点的森林由归纳假设知，GP可以分解为t条边不重合的路之并，即E(G-P)=E(P1)E(P2).E(Pt)。则G可分解为t+1条边不重合的路之并，即E(G)=E(P1)E(P2).E(Pt)E(P)。即证。第二题（讲过）2.4.4证明：若e是Kn的边，则（Kn-e）=（n-2）nn-3证明：由定理2.9：（Kn）=nn-2由于（Kn-e）=（Kn）-（含有e的生成树棵树）现在需要求含有e的生成树棵树，（含有e的生成树棵树）=2nn-3（Kn-e）=（Kn）-（含有e的生成树棵树）=（n-2）nn-3第三题（讲过）3.2.4证明：不是块的连通图至少有两个块，其中每个恰有一个割点。证明：设G为不是块的连通图，由于G连通且不是块G有割点当G只有1个割点v时，延割点分开，G1，G2内无割点，且连通，由块的定义知G1,G2是块，且分别含一个割点v。vG2G1当G含有2个及2个以上割点时，取相距距离最远的两个割点u和v，此时分G为三部分G1,G2,G3。由于u，v是相距最远的两割点G1和G3不含割点。又由于G连通，G1,G3为G的一部分故G1,G3连通。G1，G3内无割点，且连通。G1，G3是块，且分别含割点u，v。即证uvG3G2G1第四题5.2.2（a）证明：偶图G有完美对集当且仅当对所有SV有。 （b）举例说明：舍弃G是偶图这个条件之后，上述语句就不再成立。（a） 证明：必要性偶图G有完美对集MSG由于即证。充分性偶图G对所有SG有。将G分为偶图的两部分X和Y。取。，又。同样，取。同理，。由定理5.2，偶图G对所有SX有，则G为含有饱和X每个顶点的对集。又因为X，Y的对称性。偶图G有完美对集。（b） 证明：例：当G为时，满足对所有SV有，但没有完美对集。即上述语句不再成立。第五题5.3.3证明一棵树G有完美对集当且仅当对于所有成立。证明：必要性一棵树G有完美对集M，由定理5.4，由于G是完美对集，则。且由于G是完美对集，则为偶数为奇数。，即证。充分性由于对所有的有，即存在中唯一的奇分支C0(v),令C0(v)与v的关联边为e（v）=uv。此时v与e（v）存在一一对应关系，且e（u）=uv。由于v选择的任意性，于是。M为G的一个完美匹配。第六题6.1.6证明：若G是偶图，且，则G有一个边着色，使得所有种颜色都在每个顶点上表现。 证明：（反证法）假设G是偶图，且，但是无法使得所有种颜色都在每个顶点上表现。 即G存在一个最优边着色，满足d（v）（v上表现的不同颜色数目）由于引理6.1.2（G存在一个最优边着色，对于G中的一个顶点u和颜色i，j，使得i不在u上表现，而j在u上至少表现两次，则G中包含u的那个分支是奇圈。）G中包含奇圈G不是偶图，导出矛盾。原命题成立。第七题7.1.1（a）证明：G是偶图当且仅当对G的每个子图H均有（b）证明：G是偶图当且仅当对G的每个适合的子图H均有证明：必要性由于G是偶图，G含有二分类（X，Y）。由于H是G的子图，H也为含有二分类（X，Y）的偶图。令,即得，。必要性得证。充分性（反证法）假设G非偶图，则G必含有奇圈H，由于奇圈的性质与题设矛盾，充分性得证。(b)证明：必要性由于G是偶图，G含有二分类（X，Y）。由于H是G的子图，H也为含有二分类（X，Y）的偶图。故对于子图H，。此时满足定理7.3的条件必要性得证。充分性（反证法）假设G非偶图，则G必含有奇圈H，由于奇圈的性质，有，与题设不符。即假设为否。充分性得证。第八题（外找：图论的应用）在平面上有n个点Sx1，x2,xn，其中任两个点之间的距离至少是1，证明在这n个点中距离为1的点对数不超过3n。证明：首先，将本题叙述转化为图的形式：将平面上S中两点之间距离d（u，v）恰好等于1的点对相连。得到图G（V,E），其中E，每条边连接的都是距离为1的点。分析任一个顶点,设在图G中与u相连的点数为v1，v2，v3.vk。由于题意：S中任两个点之间的距离至少是1，所以，以u为圆心画半径为1的圆，圆上最多有6个点。即。每个S中顶点的度数由握手定理（定理1.1）即即证明这n个点中距离为1的点对数不超过3n。第九题（外找：补图）若图G是不连通的，则G的补图是连通的。证明：设G=（V，E）不连通，其连通分支为G1，G2，Gs，其相应的节点集为V1，V2，Vs，任取中的两个节点u，vV，若u，v分属于G中不同的连通分支，则(u,v)，因此u，v在中连通。若u，v分属于G中同一个连通分支，则从另一连通分支中任取一结点w，则(u,w)，(v,w)，于是在中存在一条道路uwv，使得u，v连通。综上所述，对于中任意2个结点，u，v总有路相连，故是连通的。u vG1 G2 v w第十题（外找：欧拉公式的应用）设G是有11个或更多结点的图，证明G或（补图）是非平面图。证明：（反证法）设G和都是平面图，设G和的顶点数分别为n和，边数分别为m和，则n=，m+=（1/2）n(n-1)（补图的性质）由欧拉定理可知， m3n-6，3n-6（推论9.5.2）（1/2）n(n-1)= m+3n-6+3n-6=6n-12即 n2-13n+240 从而得出nn-1,即证。现证有一度顶点情况。若G中有1度顶点，对顶点数n作数学归纳。当n=2时，G显然至少有一条边，结论成立。设当n=k时，结论成立，当n=k+1时，设d(v)=1，则G-v是k阶连通图，因此至少有k-1条边，所以G至少有k条边。即证。 第十二题（外找：连通度）和是简单图G的最大度和最小度，则2m / n。证明：第十三题（外找：连通度）证明：若2，则G包含圈。证明：只就连通图证明即可。设V(G)=v1,v2,vn,对于G中的路v1v2vk,若vk与v1邻接，则构成一个圈。若vi1，vi2，vin是一条路，由于d 2，因此，对vin，存在点vik与之邻接，则vikvin，vik构成一个圈 。 第十四题（外找：对偶图）（a）证明图是可平面图的充要条件是它的每一块均是可平面的。（b）推导极小非可平面图（即任意真子图均为可平面图）是一个单块。证明：（a）必要性由定义可得。充分性使用数学归纳法。假设G连通，对块数n使用归纳法。当n=1时，结论成立。假设nk时结论成立。现证当的情形：设v是G的割点，且G -v=G1+G2，显然G1,G2的块数均小于k。由归纳法设G1,G2均是可平面图，再有定理9.3得到G的一个平面嵌入。充分性得证。（b）若G是极小非可平面图，G应是单图。又若G不是单块，于是G中存在割点，将G分解为G1,G2,G3.由（a）知，这些块中必有非可平面块，这与G是极小非可平面图矛盾。即证明G是一个单块。第十五题（外找：对偶图）9.2.4设G是平面图，证明：G*G的充要条件是G是连通的证明：必要性由于G是平面图，G中的点和边将G所在的平面划分成内点不相交的闭