离散数学刘任任课后答案习题5.ppt

离散数学习题集 第五章 图与子图 2、设G（p,q）是简单二分图求证： 。 3、设G（p,q）是简单图,求证:q≤p(p-1)/2，在什么情况下, q=p(p-1)/2? ? 证明：因 是简单图。所以G中任意两颗点之间最多只有一条边。故 。 当G为完全图时，有q=p(p-1)/2 。 4、试画出四个顶点的所有非同构的简单图. 共有11个。即 5、证明图5.14中的两个图是同构的, 图5.15中的两个图不是同构的.试问,图5.16中的两个图是否同构? 1.?????? 令 ， （2）如下图，若(a)与(b)同构，则对任何双射， 必有 。于是推得 但d(b) ≠d(v)，故(a)与(b)不同构。 ? (3)下面两个图是同构。令 , 6、设G（p,q）是简单二分图，且 ≌ ,求证 . ∵G ≌ , ∴ 且 于是|E(G)|=p(p-1)/4。 显然|E(G)|是整数。于是P或P-1是4的倍数。 因此， 或 。 7、构造一个简单图G,使得 ≌ . 如下图，令 ， 则有 ≌ . 8、求证:对任何图G（p,q）,有: ∵ 而 ∴ 因此 即 9 、设G（p,q）是简单图,p≥2.求证:G中至少有两个顶点的度数相等. 证明：假设G（p,q)中任何顶点的度均不相等, 则p个顶点的度分别为0,1,2,…,p-1。 （1）设 ，则 中存在孤立点 ； （2）设 ，则 中无顶点v 满 足 ，此与（1）矛盾。 总之，0和p-1不能同时出现。由抽屉原理知，必有， 使 。 10、求证:在图G（p,p+1）中,至少有一个顶点v,满足d(v) ≥3. 证明：若对任意 ，均有 ，则有 即 ， 也即 。 从而 ，矛盾。故存在 ， 使 。 11、求证:在任何有n(n≥2)个人的人群中,至少有两个人在其中恰有相同个数的朋友. 证明：作一个n阶简单图，n个顶点分别表示n个人。两个人是朋友当且仅当表示这两个人的顶点邻接。这样，问题就转化成中至少有两个顶点的度数相等。此结论题9已证。 12、求证:每一个p阶简单图G,都与Kp的子图同构. 证明：因任何一个P阶简单图G≤Kp。又 。 故结论成立。 13、求证:任何完全图的每个点导出子图仍是完全图. 证明：由点导出子图的定义及完全图的结构即知结论成立。 14、求证:二分图的每个顶点数不小于2的子图仍是二分图. 证明：设 ，且 。 令 ， 显然 ， 且 。 因此 。 15、设G（p,q）是简单图，整数n满足1 n p – 1,求证:若p≥ 4,且G的所