《离散数学》图论部分习题_离散数学图论习题答案

2020-02-28 其他范文下载本文

《离散数学》图论部分习题由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学图论习题答案”。

《离散数学》图论部分习题

1.已知无向图G有12条边，6个3度顶点，其余顶点的度数均小于3，问G至少有几个顶点？并画出满足条件的一个图形.（24-3*6）/2 +6=9 2.是否存在7阶无向简单图G，其度序列为1、3、3、4、6、6、7.给出相应证明.不存在；7阶无向简单图G中最大度≤6 3.设d1、d2、…、dn为n个互不相同的正整数.证明：不存在以d1、d2、…、dn为度序列的无向简单图.Max{d1，d2，…，dn}≥n，n阶无向简单图G中最大度≤n-1 4.求下图的补图.5.1)试画一个具有5个顶点的自补图

2)是否存在具有6个顶点的自补图，试说明理由。

对于n阶图，原图与其补图同构，边数应相等，均为(n*(n-1)/2)/2，即n*(n-1)/4且为整数，n=4k或n=4k+1，不存在6阶自补图。

6.设图G为n(n>2且为奇数)阶无向简单图，证明：G与G的补图中奇度顶点个数相等.n(n>2且为奇数)，奇度点成对出现

7.无向图G中只有2个奇度顶点u和v，u与v是否一定连通.给出说明或证明。

只有2个奇度顶点u和v，如果不连通，在u和v在2个连通分支上，每个分支上仅有一个奇度顶点，与握手引理相矛盾。

8.图G如下图所示：

1)写出上图的一个生成子图.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.说明：δ(G)=min{ d(v)| vV } ；κ(G)=min{ |V’| |V’是图G的点割集} ； λ(G)=min{ |E’| |E’是图G的边割集} 9.在什么条件下无向完全图Kn为欧拉图？

n为奇数时

10.证明：有桥的图不是欧拉图.假设是欧拉图：桥的端点是u和v，并且图各顶点度均为偶数；桥为割边，删除桥，图不再连通，u和v应该在2各不同的连通分支上；且u和v度数变为奇数；由于其他顶点度数均为偶数，则u和v所在的连通分支上只有一个奇度顶点，与握手引理矛盾。

11.证明：有桥的图不是哈密尔顿图.若G是K2，显然不是哈密尔顿图；

否则n≥3，则桥的两个端点u和v至少有一个不是悬挂顶点（容易证明悬挂顶点不是割点）；设u不是悬挂点，则u是割点，存在割点显然不是哈密尔顿图。

12.树T有2个4度顶点，3个3度顶点，其余顶点全为树叶，问T有几片树叶？

X+2*4+3*3=2*（2+3+x-1）

x=9 13.证明：最大度Δ（T）≥k的树T至少有k片树叶。

设有n个顶点，其中x片树叶

2*（n-1）≥1*K+（n-x-1）*2+x*1

x≥k 14.已知具有3个连通分支的平面图G有4个面，9条边，求G的阶数.n-9+4=3+1

n=9

15.给出全部互不同构的4阶简单无向图的平面图形。