同等学力离散数学经典题目

1. 有些人运气好， 但并非所有人都运气好

2．自然数不是奇数就是偶数， 且奇数不能被2整除

3. 每个人的指纹都不相同。

4. 存在一个唯一的偶素数

5. 有些大学生不尊敬老人。

6证明：对任意集合 A， B， C,有(A ∩ B)UC=A ∩ (B ∪ C)当且仅当 C ⊆ A

7．已知集合A={1,2， ...， 6}上的等价关系R定义为：R=IA∪

{<1,5>,<5,1>,<2,3>,<3,2>,<2,6>,<6,2>,<3,6>,<6,3>}求出由R诱导的A的划分（即由R的商集诱导的划分）

解：

   A/R ={{1，5}，{2，3，6}，{4}}

8．设R是非空集合A上的二元关系， R满足条件：（1）R是自反的；（2） 若<a， b>∈ R ∧<a， c>∈ R， 则<b， c>∈ R；试证明R是A上的等价关系。

解：

  要证明R是等价关系，只需证明R具有反身性、对称性和传递性。

①由条件（1）可知，对于任意的a∈A，均有a R a，故R具有反身性。

②对于任意的a、b∈A，若a R b，a R a，根据条件（2），则有b R a，故R具有对称性。

③对于任意的a、b、c∈A，若a R b，b R c，因为R具有对称性，则有b R a，c R b，由条件（2）可得a R c，故R具有传递性。

综上所述，R是等价关系。

9．用“ »” 表示等势， 试证明(0,1]» (a,b]    (a,bÎR, a <b, R为实数集)

证明：集合里的等势是指,两个集合之间一一对应,或者说在两个集合间存在一个一一映射.也说是具有“相等的势”.可以构造一个从f: (0,1]->(a,b] 的一一映射

f(x)=a+(b-a)x   x∈(0,1],y

∈(a,b]显然f是入射函数

构造函数g: (a,b] →(0,1],g(x) = (x-a)/(b-a)  显然g是入射函数。

故（0,1]和(a,b]等势。

10.  G是 n 个顶点的简单连同平面图且每个面的度数（也称次数）都是 3， 则此图的边数是多少？

解：根据题意，n≥3由于G是简单连通平面图，且每个面的度数都是3，那么我们可以先用3个顶点构成一个面，然后每增加一个顶点就增加一个面，则面数f与定点数n的关系为n＝f+2，同理，我们可以先用两条边构成一个面，然后每增加两条边则又构成一个面，则总面数f与边数e的关系为e＝2f+1。根据上述两个关系式，我们可以推出此图的边数e＝2n-3

11．设T是一棵有13个顶点的树，树中度为1的顶点为叶子。 如果T的顶点的度只可能是1,2,5且T恰好有3个度为2的顶点， 那么，T中有多少个叶子？

解：主要应用的定理有：

D(v) = 2m  m = n -1

设T中有x个叶子，由于n = 13， 根据公式边数m = n-1 = 12

因此顶点的总度数d(v) = 2m = 24

因为叶子节点的度数为1，度数为2的节点数为2， 且由于顶点的度数只有1,2,5三种，所以剩余的节点都是5度节点，其个数为13-x-3 = 10-x

因此所有顶点的度数和d（v）= x *1 + 2*3 + (10-x)*5 = 24

解方程得x=8

12、具有n 个顶点的连通图至少有________条边。

解：具有n个顶点的连通图至少有n-1条边。这是一个与生成树相关的问题。生成树是一个连通图，它具有能够连通图中任何两个顶点的最小边集，任何一个生成树都具有n-1边。因此，具有n个顶点的连通图至少有n-1条边。

13、设图G有14个顶点， 27条边，

每个顶点的度只可能为3、4或5，

且G有6个度为4的顶点，

问G有多少个度为3的顶点？ 多少个度为5的顶点？

解：

设有x个三度顶点，y个5度顶点。则有方程：

x+y+6 = 14

3x+6*4+5y =27*2  (握手定理)

解得x=5 y=3

14. 设kn是n个顶点（n为正整数） 的完全图， 对kn的每条边进行红、 蓝两种颜色任意着色， 至少存在一个红色边三角形或蓝色边三角形，则最小的n是多少？

解：

    红蓝颜色组成红色边三角形或者蓝色边三角形所以需要有红色边3条或者蓝色边三条，此题转化为 有n条边分到一个红色区域和蓝色区域，至少有3个红色或者三个蓝色。根据鸽巢原理，[n/2]>=3 所以有n >=6 ,所以最小n为6.

15.设G是一个顶点个数为n（n>=5）、边数为m的连通平面图，如果G的最小圈的长度是5，证明：m <= (5/3)*(n-2)

证明：设G的平面的个数为f。因为G的最小圈的长度为5，故G的每个面的度数至少为5. 因为边数m的连通平面图是指除了任何两条边除了端点之外没有其他交点。所以有面的度数之和等于边数的2倍,由于最小圈的长度是5，按最小圈算便有。5f <= 2m

根据欧拉公式： n-m+f =2, 所以f = m+2-n  将f代入上面公式。

5m + 10 -5n <= 2m

3m <= 5(n-2) 所以m <= (5/3 )*(n-2)

16. 设Q 是一个有理数集。

对任意的a,b∈ Q，定义二元运算a△b =(a× b)/2， 则Q关于运算△的单位元是多少？， 其中“× ” 是有理数中通常的乘法运算。

解：单位元又叫幺元。

任取一个x属于非空集合S，如若在非空集合S中存在一个元素e，e*x＝x且x*e＝x就表示e是<S,*>的单位元，也就是幺元。

任取一个x属于非空集合S，如若在非空集合S中存在一个元素o，o*x＝0且x*o＝0就表示o是<S,*>的零元。

任取一个b属于非空集合S，如若在非空集合S中存在一个元素a，a*b＝e且b*a＝e就表示a是b的逆元，也可以说b是a的逆元。

所以e △x = x  即e * x /2 = x  所以e = 2

同样若求0元设为o， 则 有 o △ x = 0，即 （o * x）/2 = 0 由于x不是0，

所以o = 0.