《《离散数学》图论部分习题.pdf》由会员分享，可在线阅读，更多相关《《离散数学》图论部分习题.pdf（2页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学图论部分习题离散数学图论部分习题1.已知无向图 G 有 12 条边，6 个 3 度顶点，其余顶点的度数均小于 3，问 G 至少有几个顶点？并画出满足条件的一个图形.（24-3*624-3*6）/2+6=9/2+6=92.是否存在 7 阶无向简单图 G，其度序列为 1、3、3、4、6、6、7.给出相应证明.不存在；不存在；7 7 阶无向简单图阶无向简单图 G G 中最大度中最大度6 63.设 d1、d2、dn为 n 个互不相同的正整数.证明：不存在以 d1、d2、dn为度序列的无向简单图.Maxd1Maxd1，d2d2，dndnn n，n n 阶无向简单图阶无向简单图 G G 中最大度中
2、最大度n-1n-14.求下图的补图.5.1)试画一个具有 5 个顶点的自补图2)是否存在具有 6 个顶点的自补图，试说明理由。对于对于 n n 阶图，原图与其补图同构，边数应相等，均为阶图，原图与其补图同构，边数应相等，均为(n*(n-1)/2)/2(n*(n-1)/2)/2，即，即 n*(n-1)/4n*(n-1)/4 且为整且为整数，数，n=4kn=4k 或或 n=4k+1n=4k+1，不存在，不存在 6 6 阶自补图。阶自补图。6.设图 G 为 n(n2 且为奇数)阶无向简单图，证明：G 与 G 的补图中奇度顶点个数相等.n(n2n(n2 且为奇数且为奇数)，奇度点成对出现，奇度点成对出
3、现7.无向图 G 中只有 2 个奇度顶点 u 和 v，u 与 v 是否一定连通.给出说明或证明。只有只有 2 2 个奇度顶点个奇度顶点 u u 和和 v v，如果不连通，在，如果不连通，在u u 和和 v v 在在 2 2 个连通分支上，每个分支上仅有个连通分支上，每个分支上仅有一个奇度顶点，与握手引理相矛盾。一个奇度顶点，与握手引理相矛盾。8.图 G 如下图所示：1)写出上图的一个生成子图.2)(G)，(G)，(G).(G)=2(G)=2，(G)=1(G)=1，(G)=2.(G)=2.说明：说明：(G)=min d(v)|v(G)=min d(v)|v V V ；(G)=min|V(G)=m
4、in|V|V|V 是图是图 G G 的点割集的点割集 ；(G)=min|E(G)=min|E|E|E 是图是图 G G 的边割集的边割集 9.在什么条件下无向完全图 Kn为欧拉图？n n 为奇数时为奇数时10.证明：有桥的图不是欧拉图.假设是欧拉图：桥的端点是假设是欧拉图：桥的端点是 u u 和和 v v，并且图各顶点度均为偶数；，并且图各顶点度均为偶数；桥为割边，删除桥，图不再连通，桥为割边，删除桥，图不再连通，u u 和和 v v 应该在应该在 2 2 各不同的连通分支上；且各不同的连通分支上；且 u u 和和 v v 度数度数变为奇数；变为奇数；由于其他顶点度数均为偶数，由于其他顶点度数
5、均为偶数，则则 u u 和和 v v 所在的连通分支上只有一个奇度顶点，所在的连通分支上只有一个奇度顶点，与握手引理矛盾。与握手引理矛盾。11.证明：有桥的图不是哈密尔顿图.若若 G G 是是 K K2 2，显然不是哈密尔顿图；，显然不是哈密尔顿图；否则否则 n n3 3，则桥的两个端点，则桥的两个端点 u u 和和 v v 至少有一个不是悬挂顶点至少有一个不是悬挂顶点（容易证明悬挂顶点不是（容易证明悬挂顶点不是割点）割点）；设；设 u u 不是悬挂点，则不是悬挂点，则 u u 是割点，存在割点显然不是哈密尔顿图。是割点，存在割点显然不是哈密尔顿图。12.树 T 有 2 个 4 度顶点，3 个
6、 3 度顶点，其余顶点全为树叶，问 T 有几片树叶？X+2*4+3*3=2*X+2*4+3*3=2*（2+3+x-12+3+x-1）x=9x=913.证明：最大度（T）k 的树 T 至少有 k 片树叶。设有设有 n n 个顶点，其中个顶点，其中 x x 片树叶片树叶2*2*（n-1n-1）1*K+1*K+（n-x-1n-x-1）*2+x*1*2+x*1x xk k14.已知具有 3 个连通分支的平面图 G 有 4 个面，9 条边，求 G 的阶数.n-9+4=3+1n-9+4=3+1n=9n=915.给出全部互不同构的 4 阶简单无向图的平面图形。16.如果 G 是平面图,有 n 个顶点、m 条边、f 个面，G 有 k 个连通分支。试利用欧拉公式证明:：n-m+f=k+1.