离散数学的论文选题

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） 若∈ R ∧∈ R， 则∈ 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-311．设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=812、具有 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=314. 设kn是n个顶点（n为正整数） 的完全图， 对kn的每条边进行红、 蓝两种颜色任意着色， 至少存在一个红色边三角形或蓝色边三角形，则最小的n是多少？ 解：     红蓝颜色组成红色边三角形或者蓝色边三角形所以需要有红色边3条或者蓝色边三条，此题转化为 有n条边分到一个红色区域和蓝色区域，至少有3个红色或者三个蓝色。根据鸽巢原理，[n/2]>=3 所以有n >=6 ,所以最小n为.设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是的单位元，也就是幺元。 任取一个x属于非空集合S，如若在非空集合S中存在一个元素o，o*x＝0且x*o＝0就表示o是的零元。 任取一个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.