离散数学课件第四部分图练习题答案.docVIP

《离散数学》第四部分---图论练习题答案 一、选择或填空 1、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图 (2) 树 　(3) 平面图 (4)　连通图 答：(4)答：（2） 答：所有结点一次且恰好一次答：以v为起点的边的条数， 以v为终点的边的条数答：1答：, n-1n与边数m关系是(　　　　)。 答：m=n-1 答：所有边一次且恰好一次 答：2n-2 答：(1) 答：n(n-1),2n-2 答：它是连通图 答：（3） 答：2 答：1，树 答：（1） 答：（4） 答：(4) 答：有向图 答：偶数 答：（3） 答：（2） 答：（4） 答：（1） 答：（3） 答：（2） 证明在有n个结点的树中，其结点度数之和是2n-2。 证明： 设T=V,E是任一棵树，则|V|=n，且|E|=n-1。 由欧拉握手定理，树中所有结点的度数之和等于2|E|. 从而结点度数之和是2n-2。 任一图中度数为奇数的结点是偶数个。 证明： 设G=〈V,E〉是任一图。设|V|=n。 由欧拉握手定理可得 deg(v)=2|E|可得，图中所有结点度数之和是偶数。显然所有偶数度结点的度数之和仍为偶数，从而所有奇数度结点的度数之和也是偶数。因此，图中度数为奇数的结点一定为偶数个。 连通无向图G的任何边一定是G的某棵生成树的弦。这个断言对吗？若是对的请证明之，否则请举例说明。 证明： 不对。 反例如下：若G 本身是一棵树时，则G的每一条边都不可能是G的任一棵生成树（实际上只有惟一一棵）的弦。 设T=V,E是一棵树，若|V|1，则T中至少存在两片树叶。 证明： （用反证法证明）设|V|=n。 因为T=〈V,E〉是一棵树，所以|E|=n-1。 由欧拉握手定理可得 deg(v)=2|E|=2n-2。 假设T中最多只有1片树叶，则deg(v)2(n-1)+12n-2。 得出矛盾。 画一个使它分别满足： 有欧拉回路和哈密尔顿回路； 有欧拉回路，但无条哈密尔顿回路； 无欧拉回路，但有哈密尔顿回路； 既无欧拉回路，又无哈密尔顿回路。 解 设无向图G=V,E，|E|=12。已知有6个3度顶点，其他顶点的度数均小于3。问G中至少有多少个顶点？ 解： 设G中度数小于3的顶点有k个，由欧拉握手定理 24= 知，度数小于3 的顶点度数之和为6。故当其余的顶点度数都为2时，G的顶点最少。即G中至少有9个顶点。 设图G=V,E，|V|=n，|E|=m。k度顶点有nk个，且每个顶点或是k度顶点或是k+1度顶点。证明：nk=(k+1)-2m。 证明： 由已知可知，G中k+1度顶点为n-nk个。再由欧拉握手定理可知 2m==knk+(k+1)(n-nk)=(k+1)n+-nk 故nk=(k+1)-2m。 设G=V,E是一个连通且|V|=|E|+1的图，则G中有一个度为1的结点。 证明： (用反证法证明） 设|V|=n，则|E|=n-1。 由欧拉握手定理可得 deg(v)=2|E|=2n-2。 因为G连通，所以vV，deg(v)1。假设G中没有1片树叶，则deg(v)2n2n-2。 得出矛盾。 若n阶连通图中恰有n-1 条边，则图中至少有一个结点度数为1。 证明： （用反证法证明）设G=V,E有n-1条边且|V|=n。 由欧拉握手定理可得 deg(v)=2|E|=2n-2。 因为G是连通图，所以G中任一结点的度数都大于等于1。 假设G中不存在度数为1 的结点，则G中任一结点的度数都大于等于2.故deg(v)2(n-1)+12n-2, 得出矛盾。 若G有n个结点，m条边，f个面，且每个面至少由k(k3)条边围成，则 mk(ｎ－2)／(ｋ－2)。 证明： 设连通简单无向平面图G=〈V,E,F〉，则|V|=n,|E|=m,|F|=p。 由已知对任一fF, deg(f)k。 由公式deg(f)=2|E|可得，2|E|k|F|。 再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+|E|2。 即k(n-2)(k-2)m。 所以mk(ｎ－2)／(ｋ－2)。 设G=V,E是连通的简单平面图，|V|=n3，面数为k,则k2n-4。 证明： 记|E|=m。因为G=V,E是连通的简单平面图，故每个面的度数都不小于3。从而由公式deg(f)=2|E|可得 3k2m 再由欧拉公式|V|-|E|+|F|=2有 m=n+k-2 及 kn+k-