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.
网友评论