习 题 三
1.掷一枚非均质的硬币,出现正面的概率为p (01)p <<,若以X 表示直至掷到正、反面都出现时为止所需投掷次数,求X 的分布列。
解 ()X k =表示事件:前1k -次出现正面,第k 次出现反面,或前1k -次出现反面,第k 次出现正面,所以
11()(1)(1),2,3,.k k P X k p p p p k --==-+-=
2.袋中有b 个黑球a 个白球,从袋中任意取出r 个球,求r 个球中黑球个
数X 的分布列。
解 从a b +个球中任取r 个球共有r
a b C +种取法,r 个球中有k 个黑球的取法有k r k
b a C C -,所以X 的分布列为
()k r k
b a
r
a b
C C P X k C -+==,max(0,),max(0,)1,,min(,)k r a r a b r =--+ , 此乃因为,如果r a <,则r 个球中可以全是白球,没有黑球,即0k =;如果r a >则r 个球中至少有r a -个黑球,此时k 应从r a -开始。
3.一实习生用一台机器接连生产了三个同种零件,第i 个零件是不合格品的概率1
(1,2,3)1
i p i i ==+,以X 表示三个零件中合格品的个数,求X 的分布列。
解 设i A =‘第i 个零件是合格品’1,2,3i =。则
1231111(0)()23424
P X P A A A ===
??=, 123123123(1)()P X P A A A A A A A A A ==++
123123123()()()P A A A P A A A P A A A =++
1111211136
23423423424
=
??+??+??=, 123123123(2)()P X P A A A A A A A A A ==++
123123123()()()P A A A P A A A P A A A =++
12111312311
23423423424
=
??+???+??=, 1231236
(3)()23424
P X P A A A ===??=.
即X 的分布列为
0123
1611624242424
X
P
. 4.一汽车沿一街道行驶,需通过三个设有红绿信号灯的路口,每个信号灯为红或绿与其他信号灯为红或绿相互独立,且每一信号灯红绿两种信号显示的概率均为1
2
,以X 表示该汽车首次遇到红灯前已通过的路口的个数,求X 的概率分布。
解 (0)P X P ==(第一个路口即为红灯)12
=
, (1)P X P ==(第一个路口为绿灯,第二个路口为红灯)111224
=?=, 依此类推,得X 的分布列为
123
1111248
8
X
P
.
5.将一枚硬币连掷n 次,以X 表示这n 次中出现正面的次数,求X 的分
布列。
解 X 为n 重贝努里试验中成功出现的次数,故1
~(,)2
X B n ,X 的分布列为
1()2n
k n P X k C ??== ???
0,1,,k n = 6.一电话交换台每分钟接到的呼叫次数服从参数为4的泊松分布,求(1)每分钟恰有8次呼叫的概率;(2)每分钟的呼叫次数大于10的概率。 解 设X 为每分钟接到的呼叫次数,则~(4)X P
(1)84448444(8)0.29778!!!k k k k q P X e e e k k ∞∞---=====-=∑∑
(2)4
114(10)0.00284.!
k k P X e k ∞
-=>==∑
7.某商店每月销售某种商品的数量服从参数为5的泊松分布,问在月初至少库存多少此种商品,才能保证当月不脱销的概率为0.99977以上。 解 设X 为该商品的销售量,N 为库存量,由题意
5
1150.99977()1()1()1!
k K N K N P X N P X N P X K e k ∞
∞
-=+=+≤≤=->=-==-∑∑
即
5
150.0002
3!
K K N e k ∞
-=+≤∑ 查泊松分布表知115N +=,故月初要库存14件以上,才能保证当月不脱销的概率在0.99977以上。
8.已知离散型随机变量X 的分布列为:(1)0.2,(2)0.3P X P X ====,
(3)0.5P X ==,试写出X 的分布函数。
解 X 的分布列为
123
0.20.30.5
X P
所以X 的分布函数为
0,1,0.2,12,()0.5,23,1, 3.
x x F x x x ?≤
=?≤?≥?
9.设随机变量X 的概率密度为
sin ,0,
()0,c x x f x π<=??其他.
求:(1)常数C ;(2)使()()P X a P X a >=<成立的a .
解 (1)00
1()sin cos 2f x dx c xdx c x c π
π
+∞-∞
=
==-=?
?,1
2
c =
; (2)1111()sin cos cos 2222
a
a P X a xdx x a π
π>=
=-=+?, 0
01111()sin cos cos ,2222
a a
P X a xdx x a <==-=-? 可见 cos 0a =, 2
a π
∴=
。
10.设随机变量X 的分布函数为
()arctan F x A B x =+,x -∞<+∞,
求:(1)系数A 与B ;(2)(11)P X -<≤;(3)X 的概率密度。 解 (1)由分布函数的性质
0()2
1()2F A B F A B ππ?
=-∞=-?????=+∞=+?
??
于是 12
A =,1
B π=,所以X 的分布函数为
11
()arctan 2F x x π
=+ x -∞<<+∞
, (2)11111
(11)(1)(1)()24242
P X F F ππππ-<≤=--=+?--?=;
(3)X 的概率密度为
21
()()(1)
f x F x x π'==+, x -∞<<+∞
. 11.已知随机变量X 的概率密度为
||1
()2
x f x e -=,x -∞<<+∞.
求X 的分布函数. 解
001,0,2()()11,0,2
2x u
x x x u e du x F x f u du e dx e du x -∞
-∞
--∞?≤??==??+>????
??
1,0,2
11,0.2
x
x e x e x -?≤??=??->??
12.设随机变量X 的概率密度为
,01,
()2,12,0,x x f x x x ≤?
=-≤??
其他.
求X 的分布函数.
解 ()f x 的图形为 X 的分布函数为 ()()x F x f u du -∞
=
?
101
0,
0,,01,(2),12,1,
2.x
x
x udu x xdx u du x x ??≤=??+-≤?≥????
22
0,
0,,01,2
21,12,21,
2.x x x x x x x ??≤=??-+-≤?
≥?
13
13.设电子管寿命X 的概率密度为
2100
,100,
()0,100.x x
f x x ?>?=??≤?
若一架收音机上装有三个这种管子,求(1)使用的最初150小时内,至少有两个电了管被烧坏的概率;(2)在使用的最初150小时内烧坏的电子管数Y 的分布列;(3)Y 的分布函数。
解 Y 为在使用的最初150小时内烧坏的电子管数,~(3,)Y B p ,其中 150
2
1001001
(150)3
p P X dx x =≤=
=?, (1)所求概率为23
23121(2)(2)(3)333P Y P Y P Y C ????≥==+==?+ ?
?????
727
=
; (2)Y 的分布列为33
12()33k
k
k P Y k C -????
== ? ?
????
,0,1,2,3,k =
即
01238126127
27
27
27
Y
P
. (3)Y 的分布函数为
0,0,8,012720
(),
12,2726,23,271, 3.
x x F x x x x ??≤??=≤??≤?≥??
14.设随机变量X 的概率密度为 2,01,
()0,.
x x f x <=?
?其他
现对X 进行n 次独立重复观测,以n V 表示观测值不大于0.1的观测次数,试求随机变量n V 的概率分布。 解 ~(,)n V B n p ,其中 0.10
(0.1)20.01p P X xdx =≤==?
,
所以n V 的概率分布列为
()(0.01)(0.99),
,1k k n k n n P V k C k n -=== . 15.设随机变量~[1,6]X U ,求方程210x Xx ++=有实根的概率. 解 设A =‘方程有实根’,则
A 发生2
40X ?-≥ 即 ||2X ≥,因~[1,6]X U ,所以
A 发生2,X ?> 所以
624
()(2)0.8615
P A P X -=>=
==-.
16.设随机变量~[2,5]X U ,现对X 进行3次独立观测,试求至少有两次观测值大于3的概率.
解 设Y 为三次观测中,观测值大于3的观测次数,则~(3,)Y B p ,其中 532
(3)523
p P X -=>==-, 所求概率为
2
3
23
21220
(2)(2)(3)33327
P Y P Y P Y C ??????≥==+==+=
? ? ???????. 17.设顾客在某银行窗口等待服务的时间X (单位:分),服从参数为
1
5
的指数分布。若等待时间超过10分钟,则他就离开。设他一个月内要来银行5次,以Y 表示一个月内他没有等到服务而离开窗口的次数,求Y 的分布列及
(1)P Y ≥。
解 由题意~(5,)Y B p ,其中 25
510
10
1(10)5x x
p P X e dx e e +∞
--+∞-=>==-=?
, 于是Y 的分布为
2255()()(1)0,1,2,3,4,5,k
k k
P Y k C e e k ---==-=
25(1)1(0)1(1)0.5167P Y P Y e -≥=-==--≈.
18.一大型设备在任何长为t 的时间内发生故障的次数()N t 服从参数为t λ的泊松分布。(1)求相继两次故障之间时间间隔T 的概率分布;(2)求在设备已经无故障工作了8小时的情况下,再无故障运行8小时的概率。 解 (1)设T 的分布函数为()T F t ,则 ()()1()T F t P T t P T t =≤=->
事件()T t >表示两次故障的间隔时间超过t ,也就是说在时间t 内没有发生故障,故()0N t =,于是
0()()1()1(()0)11,00!
t
t T t F t P T t P N t e e t λλλ--=->=-==-=->,
可见,T 的分布函数为
1,0,
()0,0.t T e t F t t λ-?->=?≤?
即T 服从参数为λ的指数分布。 (2)所求概率为
1688{16,8}(16)(16|8)(8)(8)P T T P T e P T T e P T P e
λ
λλ--->>>>>====>>.
19.设随机变量2~(108,3)X N 。求
(1)(101.1117.6)P X <<;(2)常数a ,使()0.90P X a <=; (3)常数a ,使(||)0.01P X a a ->=。
解 (1)117.6108101.1108
(101.1117.6)(
)()33
P X --<<=Φ-Φ (32)(23)(32)(23)1=Φ?-Φ-?=Φ?+Φ?-
0.99930.989310.9886=+-=; (2)108
0.90()()3
a P X a -=<=Φ,查表知
108
1.283
a -=,所以111.84a =; (3)0.01(||)1(||)1(02)P X a a P X a a P X a =->=--≤=-<≤
2108
1(
),3
a -=-Φ 所以 2108
(
)0.993
a -Φ=, 查正态分布表知
2108
2.333
a -=, 故 57.495a =。
20.设随机变量2
~(2,)X N σ,且(24)0.3P X <<=,求(0)P X <。
解 42
0.3(24)()(0)P X σ
-=<<=Φ-Φ,
所以 2
(
)0.8σ
Φ=, 02
2
2
(0)(
)()1()0.2P X σ
σ
σ
-<=Φ=Φ-
=-Φ=。
21.某地抽样结果表明,考生的外语成绩X (百分制)近似服从正态分布,平均成绩(即参数μ之值)为72分,96分以上的占考生总数的2.3%,试求考生的外语成绩在60分至84分之间的概率。
解 967224
0.023(96)1
()1(
)
P X σσ
-=>=-Φ=-Φ
24
24
12
()0.977,
2,
1.σ
σ
σ
∴Φ===
所求概率为
8472
60
721212
(60
84)()
(
)
()
()
P X σ
σσσ
--<<=Φ-Φ=Φ-Φ- 12
2(
)120.841310.6826.σ
=Φ-=?-=
22.假设测量的随机误差2~(0,10)X N ,试求在100次重复测量中,至少有三次测量误差的绝对值大于19.6的概率α,并利用泊松分布求出α的近似值。 解 设Y 为误差的绝对值大于19.6的测量次数,则~(100,)Y B p ,其中
(||19.6)1(19.619.6)1(1.96)
p P
X P X =≥=--<≤=-Φ+Φ- 22(1.96)220.975=-Φ=
-?=,
所求概率为
100
1001003
(3)(0.05)(0.95),k
k k k P Y C α-==≥=∑
利用泊松定理
100
5
350.875!
k k e k α-=≈=∑.
23.在电源电压不超过200V ,在200240V -和超过240V 三种情况下,某种电子元件,损坏的概率分别为0.1,0.001和0.2,假设电源电压X 服从正态分布2
(220,25)N ,试求:(1)该电子元件损坏的概率α;(2)该电子元件损坏时,电源电压在200-240V 的概率β。
解 设A =‘电子元件损坏’,i B =‘电源电压在第i 档’,1,2,3i =,则 (1)112233()()(|)()(|)()(|)P A P B P A B P B P A B P B P A B α==++ (200)0.1(200240)0.001(240)0.2P X P X P X =≤?+<≤?+>?
200220240220200220
()0.1[()()]0.001252525---=Φ?+Φ-Φ? 240220
[1(
)]0.225
-+-Φ? 20202020
()0.1[()()]0.001[(1()]0.225252525
=Φ-?+Φ-Φ-?+-Φ?
(10.7881)0.1(20.78811)0.001(10.7881)0.2=-?+?-?+-?
0.0641=
(2)222()(|)0.005756
(|)0.08980.06410.0641
P B P A B P B A β==
==.
24.假设随机变量X 的绝对值不大于1;11
(1),(1)84
P X P X =-===,
在事件{11}X -<<出现的条件下,X 在(1,1)-内任意子区间上取值的概率与
该子区间的长度成正比。试求:(1)X 的分布函数;(2)X 取负值的概率P . 解1 设X 的分布函数为()F x ,则 当 1x <-时,()0F x =,且1
(1)8
F -=, 当 1x ≥时,()1F x =, 115(11)1848
P X -<<=--=, 当 11x -<<时,由题意
{1|11}(1)P X x X k x -<≤-<<=+, 而
1{11|11}2P X X k =-<<-<<=, 所以 1
2
k =
。于是 1
{1|11},2
x P X x X +-<≤-<<= 此时
(){1}(1)F x P X x F =-<≤+- 1{1,11}8
P X x X =-<≤-<<+
1{11}(1|11}8
P X P X x X =-<-<≤-<<+ 5115782816
x x ++=
?+=, 故X 的分布函数为
0,1,
57(),11,161, 1.
x x F x x x <-??+?
=-≤?≥??
(2)7
(0)(0)(0)16
P X F P X <=-==
.
解2 设X 的分布函数为()F x ,则 当 1x <-时,()0F x = 且 1(1)8
F -= 当 1x ≥时,()1F x =,
当11x -<<时,设,(1,1)x x x +?∈-,且0x ?>,由题意 (|11)P x X x x X k x <≤+?-<<=?, 即 (,11)
,(11)
P x X x x X k x P X <≤+?-<<=?-<<
由此得
5
()8
P x X x x k x <≤+?=?, 两边同除以x ?得
()()5
,8
F x x F x k x +?-=?
令0x ?→取极限得 5(),8
F x k '= 两边积分得
5
()8F x kx C =+, 由1(1)8F -=及103
lim ()4
x F x →-=得
1588
3548
k C k C ?=-+????=+??
解之得 71
,162
C k == 故 5757
()161616
x x F x +=
+=,11x -<< 综上所述,X 的分布函数为
0,1,57(),11,161, 1.
x x F x x x <-??+?
=-≤?≥??
(2)7
(0)(0)(0).16
P X F P X <=-==
25.已知离散型随机变量X 的分布列为
210131111115
6
515
30
X
P
-- 求2Y X =的分布列. 解 Y 的分布列为
1491
71115
30
530
Y
P
. 26.设随机变量X
的概率密度为
,0,
()0,0.
x X e x f x x -?≥=?
求X Y e =的概率密度()Y f y
解1 当0x >时函数x y e =单调增,反函数为()ln x h y y ==,于是X
Y e =的概率密度为
ln 211
,1,
,1,()(())|()|0, 1.0, 1.y Y X y e y y
y f y f h y h y y y -??≥?≥??'===????≤?
解2 设Y 的分布函数为()Y F y ,则
,1,
()()()(ln ),
1
X
Y y F y P Y y P e y P X y y =≤=≤=?
≤≥? ln 0
,1,,1,y x y e dx y -?=?≥???ln 00,1,, 1.y
x y e y -?
=?-≥??
ln 0,1,
0,1,11, 1.
1, 1.y
y y y e y y -?
==??-≥-≥???
21
,1,()()0, 1.Y Y y y f y F y y ?≥?'==??
27.设随机变量X 的概率密度为
2
1
(),(1)
X f x x x π=-∞<<∞+
求随机变量1Y =()Y f y
解1
函数1y =3()(1)x h y y ==-,则
2
6
3(1)()(())|()|,.(1(1))
Y X y f y f h y h y y y π-'==-∞<<+∞+-
解2 设Y 的分布函数为()Y F y ,则
3()()(1)1)1((1))Y F y P Y y P y P y P X y =≤==-=-≤- 31{(1)}X F y =--, 所以
2
3
2
63(1)()((1))3(1),(1(1))
Y X y f y f y y y y π-=-?-=-∞<<+∞+-。
28.设~(0,1)X U ,求(1)X Y e =的概率密度;(2)2ln Y X =-的概率
密度。
解 X 的密度为 1,01,
()0,X x f x <=?
?其它.
(1)x y e =在(0,1)上单调增,反函数为()ln h y y =,所以Y 的密度为
1
,1,
()0,.Y y e y f y ?<=???
其他
(2)2ln y x =-在(0,1)上单调减,反函数为2
()y h y e
-=,所以Y 的密度为
2
1,0,
()20,0.y
Y e y f y y -?>?=??≤?
29.设~(0,1)X N ,求||Y X =的概率密度。
解1 函数||y x =在(,0)-∞上单调减,反函数为1()h y y =-, 在[0,)+∞上单调增,反函数为2()h y y =,
所以Y 的密度为 1122(())|()|(())|
()|,0,
()0,
0.
X X Y f h y h y f h y h y y f y y ''?+>=?
≤?
即
2
2,0,()0,0.y
Y y f y y ->=≤?
30.设随机变量X 服从参数为2的指数分布,试证21X Y e -=-在区间(0,1)
上服从均匀分布。
[证] 只须证明Y 的分布函数为
0,0
(),01,1, 1.Y y F y y y y ≤??
=<?≥?
220,
0()(){1}{1},01,1,1X
x Y y F y P Y y P e
y P e y y y --≤??
=≤=-≤=≥-<?≥?
0,0,(2ln(1)),01,1, 1.y P X y y y ≤??=-≥-<?≥?1
20,0,(ln(1)).01,0, 1.y P X y y y -
?≤???
≤-<<=???
≥?? 120,0,(ln(1)),01,1,
1.X y F y y y -?≤???-<<=???
≥??12
2ln(1)0,
01,011,1y y e y y ---≤???=-<?≥??
0,0,,01,1, 1.y y y y ≤??
=<?≥?
31.设随机变量X 的概率密度为
22,0,
()0,.x
x f x ππ?<=???
其它
求sin Y X =的概率密度. 解1 函数sin y x =在(0,]2
π
上单调增,反函数为1()arcsin h y y =
在(
,)2
π
π上单调减,反函数为2()arcsin h y y π=-.
Y 的概率密度为:
()(arcsin )(arcsin Y f y f y f y π=-
222arcsin 22arcsin 01,0,
y y y πππ-?<=??
?其他.
01,0,
.y <<=?其他
解2 设Y 的分布函数为()Y F y ,则
()()(sin )(arcsin arcsin )Y F y P Y y P X y P X y X y π=≤=≤=≤>- (arcsin )1(arcsin )P X y P X y π=≤+-≤- (arcsin )1(arcsin )X X F y F y π=+-- 所以
()(arcsin )(arcsin Y f y f y f y π=+-
01,0
,y <<=?其他.
32.设随机变量X 的分布函数()F x 连续,且严格单调增加,求()Y F X =的概率密度.
解 设Y 的分布函数为()Y F y ,则
1()(){()}{()}Y F y P Y y P F X y P X F y y -=≤=≤=≤=, 当0y ≤时()0Y F y =,当1y ≥时()1Y F y =,故
0,0,(),01,1, 1.Y y F y y y y ≤??
=<?≥?
于是Y 的概率密度为 1,01,
()0,.
Y y f y <=??其他
图论复习题答案 一、判断题,对打,错打 1.无向完全图是正则图。 () 2.零图是平凡图。() 3.连通图的补图是连通图.() 4.非连通图的补图是非连通图。() 5.若连通无向简单图G中无圈,则每条边都是割边。() 6.若无向简单图G是(n,m)图,并且m=n-1,则G是树。() 7.任何树都至少有2片树叶。() 8.任何无向图G都至少有一个生成树。() 9.非平凡树是二分图。() 10.所有树叶的级均相同的二元树是完全二元树。() 11.任何一个位置二元树的树叶都对应唯一一个前缀码。() 12. K是欧拉图也是哈密顿图。() 3,3 13.二分图的对偶图是欧拉图。() 14.平面图的对偶图是连通图。() 页脚内容1
15.设G*是平面图G的对偶图,则G*的面数等于G的顶点数。() 二、填空题 1.无向完全图K6有15条边。 2.有三个顶点的所有互不同构的简单无向图有4个。 3.设树T中有2个3度顶点和3个4度顶点,其余的顶点都是树叶,则T中有10片树叶。 4.若连通无向图G是(n,m)图,T是G的生成树,则基本割集有n-1个,基本圈有m-n+1个。 5.设连通无向图G有k个奇顶点,要使G变成欧拉图,在G中至少要加k/2条边。 6.连通无向图G是(n,m)图,若G是平面图,则G有m-n+2个面。 三、解答题 1.有向图D如图1所示,利用D的邻接矩阵及其幂运算 求解下列问题: (1)D中长度等于3的通路和回路各有多少条。 (2)求D的可达性矩阵。 (3)求D的强分图。 解:(1) a b c d e 图1 页脚内容2
页脚内容3 M=????????????????000101000000001 010*******M 2=?? ? ? ??????? ?????010******* 000101000001000 M 3=????????????????10000 01000010000001010000M 4=??? ???? ? ??? ?????00010 01000 100000100000010 由M 3可知,D 中长度等于3的通路有5条,长度等于3的回路有3条。 (2) I+M+M 2+M 3+M 4=????????????? ???100000100000100 0001000001 +??????????? ?? ???000101000000001 010******* +??????????? ?? ???010000001000010 1000001000 +??? ???? ? ??? ?? ???100000100001000 0001010000 + ????????????????00010 01000100000100000010 =??? ???? ???? ?? ???21020 1301011111 020******* D 的可达性矩阵为 R=B (I+M+M 2+M 3+M 4)=??? ???? ? ????? ???110101********* 1101011011 b c d e 图1
第一章习题 1.1 图示元件当时间t<2s时电流为2A,从a流向b;当t>2s时为3A,从b流向a。根据图示参考方向,写出电流的数学表达式。 1.2图示元件电压u=(5-9e-t/τ)V,τ>0。分别求出t=0 和t→∞时电压u的代数值及其真实方向。 图题1.1图题1.2 1.3 图示电路。设元件A消耗功率为10W,求;设元件B消耗功率为-10W,求;设元件C发出功率为-10W,求。 图题1.3 1.4求图示电路电流。若只求,能否一步求得? 1.5图示电路,已知部分电流值和部分电压值。 (1) 试求其余未知电流。若少已知一个电流,能否求出全部未知电流? (2) 试求其余未知电压u14、u15、u52、u53。若少已知一个电压,能否求出全部未知电压? 1.6 图示电路,已知,,,。求各元件消耗的功率。 1.7 图示电路,已知,。求(a)、(b)两电路各电源发出的功率和电阻吸收的功率。 1.8求图示电路电压。 1.9 求图示电路两个独立电源各自发出的功率。 1.10求网络N吸收的功率和电流源发出的功率。 1.11 求图示电路两个独立电源各自发出的功率。
1.12 求图示电路两个受控源各自发出的功率。 1.13 图示电路,已知电流源发出的功率是12W,求r的值。 1.14求图示电路受控源和独立源各自发出的功率。 1.15图示电路为独立源、受控源和电阻组成的一端口。试求出其端口特性,即关系。 1.16 讨论图示电路中开关S开闭对电路中各元件的电压、电流和功率的影响,加深对独立源特性的理解。 第二章习题 2.1 图(a)电路,若使电流A,,求电阻;图(b)电路,若使电压U=(2/3)V,求电阻R。 2.2 求图示电路的电压及电流。 2.3图示电路中要求,等效电阻。求和的值。 2.4求图示电路的电流I。
* 《概率论与数理统计》作业集及答案 第1章 概率论的基本概念 §1 .1 随机试验及随机事件 1. (1) 一枚硬币连丢3次,观察正面H ﹑反面T 出现的情形. 样本空间是:S= ; (2) 一枚硬币连丢3次,观察出现正面的次数. 样本空间是:S= ; 2.(1) 丢一颗骰子. A :出现奇数点,则A= ;B :数点大于2,则B= . (2) 一枚硬币连丢2次, A :第一次出现正面,则A= ; B :两次出现同一面,则= ; C :至少有一次出现正面,则C= . ? §1 .2 随机事件的运算 1. 设A 、B 、C 为三事件,用A 、B 、C 的运算关系表示下列各事件: (1)A 、B 、C 都不发生表示为: .(2)A 与B 都发生,而C 不发生表示为: . (3)A 与B 都不发生,而C 发生表示为: .(4)A 、B 、C 中最多二个发生表示为: . (5)A 、B 、C 中至少二个发生表示为: .(6)A 、B 、C 中不多于一个发生表示为: . 2. 设}42:{},31:{},50:{≤<=≤<=≤≤=x B x x A x x S :则 (1)=?B A ,(2)=AB ,(3)=B A , (4)B A ?= ,(5)B A = 。 \ §1 .3 概率的定义和性质 1. 已知6.0)(,5.0)(,8.0)(===?B P A P B A P ,则 (1) =)(AB P , (2)()(B A P )= , (3))(B A P ?= . 2. 已知,3.0)(,7.0)(==AB P A P 则)(B A P = . §1 .4 古典概型 1. 某班有30个同学,其中8个女同学, 随机地选10个,求:(1)正好有2个女同学的概率, (2)最多有2个女同学的概率,(3) 至少有2个女同学的概率. 2. 将3个不同的球随机地投入到4个盒子中,求有三个盒子各一球的概率. — §1 .5 条件概率与乘法公式 1.丢甲、乙两颗均匀的骰子,已知点数之和为7, 则其中一颗为1的概率是 。 2. 已知,2/1)|(,3/1)|(,4/1)(===B A P A B P A P 则=?)(B A P 。 §1 .6 全概率公式 1. 有10个签,其中2个“中”,第一人随机地抽一个签,不放回,第二人再随机地抽一个 签,说明两人抽“中‘的概率相同。
集合与图论习题 第一章习题 .画出具有个顶点地所有无向图(同构地只算一个). .画出具有个顶点地所有有向图(同构地只算一个). .画出具有个、个、个顶点地三次图. .某次宴会上,许多人互相握手.证明:握过奇数次手地人数为偶数(注意,是偶数). .证明:哥尼斯堡七桥问题无解. .设与是图地两个不同顶点.若与间有两条不同地通道(迹),则中是否有回路? .证明:一个连通地(,)图中≥. .设是一个(,)图,δ()≥[],试证是连通地. .证明:在一个连通图中,两条最长地路有一个公共地顶点. .在一个有个人地宴会上,每个人至少有个朋友(≤≤).试证:有不少于个人,使得他们按某种方法坐在一张圆桌旁,每人地左、右均是他地朋友.b5E2R。 .一个图是连通地,当且仅当将划分成两个非空子集和时,总有一条联结地一个顶点与地一个顶点地边. .设是图.证明:若δ()≥ ,则包含长至少是δ()地回路. .设是一个(,)图,证明: ()≥,则中有回路; ()若≥,则包含两个边不重地回路. .证明:若图不是连通图,则是连通图. .设是个(,)图,试证: ()δ()·δ()≤[()]([()]),若≡,,( ) () δ()·δ()≤[()]·[()],若≡( ) .证明:每一个自补图有或个顶点. .构造一个有个顶点而没有三角形地三次图,其中≥. .给出一个个顶点地非哈密顿图地例子,使得每一对不邻接地顶点和,均有 ≥ .试求中不同地哈密顿回路地个数. .试证:图四中地图不是哈密顿图. .完全偶图,为哈密顿图地充分必要条件是什么?
.菱形面体地表面上有无哈密顿回路? .设是一个(≥)个顶点地图.和是地两个不邻接地顶点,并且≥.证明:是哈密顿图当且仅当是哈密顿图. .设是一个有个顶点地图.证明:若>δ(),则有长至少为δ()地路. .证明具有奇数顶点地偶图不是哈密顿图. .证明:若为奇数,则中有()个两两无公共边地哈密顿回路. .中国邮路问题:一个邮递员从邮局出发投递信件,然后返回邮局.若他必须至少一次走过他所管辖范围内地每条街道,那么如何选择投递路线,以便走尽可能少地路程.这个问题是我国数学家管梅谷于年首先提出地,国外称之为中国邮路问题.p1Ean。 ()试将中国邮路问题用图论述语描述出来. ()中国邮路问题、欧拉图问题及最短路问题之间有何联系. 第三章习题 .分别画出具有、、个顶点地所有树(同构地只算一个). .证明:每个非平凡树是偶图. .设是一棵树且Δ()≥,证明:中至少有个度为地顶点. .令是一个有个顶点,个支地森林,证明:有条边. .设是一个个顶点地树.证明:若图地最小度δ()≥,则有一个同构于地子图. .一棵树有个度为地顶点,个度为地顶点,…,个度为地顶点,则有多少个度为地顶点? .设是一个连通图.试证:地子图是地某个生成树地子图,当且仅当 没有回路. .证明:连通图地任一条边必是它地某个生成树地一条边. .设是一个边带权连通图,地每条边均在地某个回路上.试证:若地边地权大于地任一其他边地权,则不在地任一最小生成树中.DXDiT。 . 设(,,)是一个边带权连通图,对任意∈,()≥.试证:地一个生成树是地最小生成树,当且仅当时地任一与地距离为地生成树′′满足条件:在中而不在′′中地边地权()不大于在′′中而不在中地边′地权(′).RTCrp。 .某镇有人,每天他们中地每个人把昨天听到地消息告诉他认识地人.已知任何 消息,只要镇上有人知道,都会经这种方式逐渐地为全镇上所有人知道.试证:可选出个居民代表使得只要同时向他们传达某一消息,经天就会为全镇居民知道.5PCzV。 个顶点地图中,最多有多少个割点? .证明:恰有两个顶点不是割点地连通图是一条路.
习题二 3.设在15只同类型零件中有2只为次品,在其中取3次,每次任取1只,作不放回抽样,以X 表示取出的次品个数,求: (1) X 的分布律; (2) X 的分布函数并作图; (3) 133 {},{1},{1},{12}222 P X P X P X P X ≤<≤≤≤<<. 【解】 故X 的分布律为 (2) 当x <0时,F (x )=P (X ≤x )=0 当0≤x <1时,F (x )=P (X ≤x )=P (X =0)= 22 35 当1≤x <2时,F (x )=P (X ≤x )=P (X =0)+P (X =1)=3435 当x ≥2时,F (x )=P (X ≤x )=1 故X 的分布函数 (3) 4.射手向目标独立地进行了3次射击,每次击中率为0.8,求3次射击中击中目标的次数的分布律及分布函数,并求3次射击中至少击中2次的概率. 【解】 设X 表示击中目标的次数.则X =0,1,2,3. 故X 的分布律为 分布函数 5.(1) 设随机变量X 的分布律为 P {X =k }=! k a k λ, 其中k =0,1,2,…,λ>0为常数,试确定常数a . (2) 设随机变量X 的分布律为 P {X =k }=a/N , k =1,2,…,N , 试确定常数a . 【解】(1) 由分布律的性质知 故 e a λ -= (2) 由分布律的性质知 即 1a =. 6.甲、乙两人投篮,投中的概率分别为0.6,0.7,今各投3次,求: (1) 两人投中次数相等的概率;
(2) 甲比乙投中次数多的概率. 【解】分别令X 、Y 表示甲、乙投中次数,则X~b (3,0.6),Y~b (3,0.7) (1) ()(0,0)(1,1)(2,2)P X Y P X Y P X Y P X Y ====+==+==+ 331212 33(0.4)(0.3)C 0.6(0.4)C 0.7(0.3)=++ (2) ()(1,0)(2,0)(3,0)P X Y P X Y P X Y P X Y >===+==+==+ =0.243 7.设某机场每天有200架飞机在此降落,任一飞机在某一时刻降落的概率设为0.02,且设各飞机降落是相互独立的.试问该机场需配备多少条跑道,才能保证某一时刻飞机需立即降落而没有空闲跑道的概率小于0.01(每条跑道只能允许一架飞机降落)? 【解】设X 为某一时刻需立即降落的飞机数,则X ~b (200,0.02),设机场需配备N 条跑道,则有 即 200 2002001 C (0.02)(0.98) 0.01k k k k N -=+<∑ 利用泊松近似 查表得N ≥9.故机场至少应配备9条跑道. 8.已知在五重伯努利试验中成功的次数X 满足P {X =1}=P {X =2},求概率P {X =4}. 【解】设在每次试验中成功的概率为p ,则 故 1 3 p = 所以 4451210(4)C ()33243 P X === . 9.设事件A 在每一次试验中发生的概率为0.3,当A 发生不少于3次时,指示灯发出信号, (1) 进行了5次独立试验,试求指示灯发出信号的概率; (2) 进行了7次独立试验,试求指示灯发出信号的概率. 【解】(1) 设X 表示5次独立试验中A 发生的次数,则X ~6(5,0.3) (2) 令Y 表示7次独立试验中A 发生的次数,则Y~b (7,0.3) 10.某公安局在长度为t 的时间间隔内收到的紧急呼救的次数X 服从参数为(1/2)t 的泊松分布,而与时间间 隔起点无关(时间以小时计). (1) 求某一天中午12时至下午3时没收到呼救的概率; (2) 求某一天中午12时至下午5时至少收到1次呼救的概率. 【解】(1)32 (0)e P X -== (2) 52 (1)1(0)1e P X P X - ≥=-==- 11.设P {X =k }=k k k p p --22) 1(C , k =0,1,2 P {Y =m }=m m m p p --44) 1(C , m =0,1,2,3,4 分别为随机变量X ,Y 的概率分布,如果已知P {X ≥1}=5 9 ,试求P {Y ≥1}. 【解】因为5(1)9P X ≥= ,故4(1)9 P X <=. 而 2 (1)(0)(1)P X P X p <===-
学号:0441 姓名:张倩 习题1 4.证明图1-28中的两图是同构的 证明:将图1-28的两图顶点标号为如下的(a)与(b)图 作映射f : f(v i )?u i (1? i ? 10) 容易证明,对?v i v j ?E((a)),有f(v i v j )?u i u j ?E((b)) (1? i ? 10, 1?j? 10 ) 由图的同构定义知,图1-27的两个图是同构的。 5.证明:四个顶点的非同构简单图有11个。 证明:设四个顶点中边的个数为m ,则有: m=0: m=1 : m=2: m=3: (a) v 1 v 2 v 3 v v 5 v 6 v 7 v 8 v 9 v 10 u 1 u 2 u 3 u 4 u 5 u 6 u 7 u 8 u 9 u 10 (b)
m=4: m=5: m=6: 因为四个顶点的简单图最多就是具有6条边,上面所列出的情形是在不同边的条件下的不同构的情形,则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 11.证明:序列(7,6,5,4,3,3,2)和(6,6,5,4,3,3,1)不是图序列。 证明:由于7个顶点的简单图的最大度不会超过6,因此序列(7,6,5,4,3,3,2)不是图序列; (6,6,5,4,3,3,1)是图序列 ()1 1 123121,1,,1,,,=d d n d d d d d π++---是图序列 (5,4,3,2,2,0)是图序列,然而(5,4,3,2,2,0)不是图序列,所以(6,6,5,4,3,3,1)不是图序列。 12.证明:若δ≥2,则G 包含圈。 证明 只就连通图证明即可。设V(G)={v1,v2,…,vn},对于G 中的路v1v2…vk,若vk 与v1邻接,则构成一个圈。若vi1vi2…vin 是一条路,由于?? 2,因此,对vin ,存在点vik 与之邻接,则vik?vinvik 构成一个圈 。 17.证明:若G 不连通,则G 连通。 证明 对)(,_ G V v u ∈?,若u 与v 属于G 的不同连通分支,显然u 与v 在_ G 中连通;若u 与v 属于g 的同一连通分支,设w 为G 的另一个连通分支中的一个顶点,则u 与w ,v 与w 分别在_ G 中连通,因此,u 与v 在_ G 中连通。
一、填空题(每小题3分,共15分) 1. 设事件B A ,仅发生一个的概率为0.3,且5.0)()(=+B P A P ,则B A ,至少有一个不发 生的概率为__________. 答案:0.3 解: 3.0)(=+B A B A P 即 )(25.0)()()()()()(3.0AB P AB P B P AB P A P B A P B A P -=-+-=+= 所以 1.0)(=AB P 9.0)(1)()(=-==AB P AB P B A P . 2. 设随机变量X 服从泊松分布,且)2(4)1(==≤X P X P ,则==)3(X P ______. 答案: 161-e 解答: λλ λ λλ---= =+==+==≤e X P e e X P X P X P 2 )2(, )1()0()1(2 由 )2(4)1(==≤X P X P 知 λλλ λλ---=+e e e 22 即 0122 =--λλ 解得 1=λ,故 16 1)3(-= =e X P 3. 设随机变量X 在区间)2,0(上服从均匀分布,则随机变量2 X Y =在区间)4,0(内的概率 密度为=)(y f Y _________. 答案: 04,()()0,. Y Y X y f y F y f <<'===? 其它 解答:设Y 的分布函数为(),Y F y X 的分布函数为()X F x ,密度为()X f x 则 2 ()()())))Y X X F y P Y y P X y y y y y =≤=≤ =≤- - 因为~(0,2)X U ,所以(0X F = ,即()Y X F y F = 故
哈工大图论习题
————————————————————————————————作者:————————————————————————————————日期:
1.画出具有4个顶点的所有无向图(同构的只算一个)。 2.画出具有3个顶点的所有有向图(同构的只算一个)。 3.画出具有4个、6个、8个顶点的三次图。 4.某次宴会上,许多人互相握手。证明:握过奇数次手的人数为偶数(注意,0是偶数)。 5.证明:哥尼斯堡七桥问题无解。 6.设u与v是图G的两个不同顶点。若u与v间有两条不同的通道(迹),则G中是否有回路? 7.证明:一个连通的(p,q)图中q ≥p-1。 8.设G是一个(p,q)图,δ(G)≥[p/2],试证G是连通的。 9.证明:在一个连通图中,两条最长的路有一个公共的顶点。 10.在一个有n个人的宴会上,每个人至少有m个朋友(2≤m≤n)。试证:有不少于m+1个人,使得他们按某种方法坐在一张圆桌旁,每人的左、右均是他的朋友。 11.一个图G是连通的,当且仅当将V划分成两个非空子集V1和V2时,G总有一条联结V1的一个顶点与V2的一个顶点的边。 12.设G是图。证明:若δ(G)≥ 2,则G包含长至少是δ(G)+1的回路。 13.设G是一个(p,q)图,证明: (a)q≥p,则G中有回路; (b)若q≥p+4,则G包含两个边不重的回路。 14.证明:若图G不是连通图,则G c 是连通图。 15.设G是个(p,q)图,试证: (a)δ(G)·δ(G C)≤[(p-1)/2]([(p+1)/2]+1),若p≡0,1,2(mod 4) (b) δ(G)·δ(G C)≤[(p-3)/2]·[(p+1)/2],若p≡3(mod 4) 16.证明:每一个自补图有4n或4n+1个顶点。 17.构造一个有2n个顶点而没有三角形的三次图,其中n≥3。 18.给出一个10个顶点的非哈密顿图的例子,使得每一对不邻接的顶点u和v,均有 degu+degv≥9 19.试求Kp中不同的哈密顿回路的个数。 20.试证:图四中的图不是哈密顿图。 21.完全偶图Km,n为哈密顿图的充分必要条件是什么? 22.菱形12面体的表面上有无哈密顿回路? 23.设G是一个p(p≥3)个顶点的图。u和v是G的两个不邻接的顶点,并且degu+degv ≥p。证明:G是哈密顿图当且仅当G+uv是哈密顿图。 24.设G是一个有p个顶点的图。证明:若p>2δ(G),则有长至少为2δ(G)的路。 25.证明具有奇数顶点的偶图不是哈密顿图。 26.证明:若p为奇数,则Kp中有(p-1)/2个两两无公共边的哈密顿回路。 28.中国邮路问题:一个邮递员从邮局出发投递信件,然后返回邮局。若他必须至少一次走过他所管辖范围内的每条街道,那么如何选择投递路线,以便走尽可能少的路程。这个问题是我国数学家管梅谷于1962年首先提出的,国外称之为中国邮路问题。 (1)试将中国邮路问题用图论述语描述出来。 (2)中国邮路问题、欧拉图问题及最短路问题之间有何联系。
第六章 树及割集 习题课1 课堂例题 例1 设T 是一棵树,T 有3个度为3顶点,1个2度顶点,其余均是1度顶点。则 (1)求T 有几个1度顶点 (2)画出满足上述要求的不同构的两棵树。 分析:对于任一棵树T ,其顶点数p 和边数q 的关系是:1q p =-且 1 deg()2i p i v q ==∑,根据这些性质容易求解。 解:(1)设该树T 的顶点数为p ,边数为q ,并设树T 中有x 个1度顶点。于是 1 deg()33122i p i v x q ==?+?+=∑且31p x =++,1q p =-,得5x =。 (2)满足上述要求的两棵不同构的无向树,如图1所示。 图1 例2设G 是一棵树且()G k ?≥,证明G 中至少有k 个度为1顶点。 证:设T 中有p 个顶点,s 个树叶,则T 中其余p s -个顶点的度数均大于等于2,且至少有一个顶点的度大于等于k 。由握手定理可得: 1222()2(1)p i i q p deg v p s k s ==-=≥--++∑,有s k ≥。 所以T 中至少有k 个树叶 。 习题 例1 若无向图G 中有p 个顶点,1p -条边,则G 为树。这个命题正确吗为什么 解:不正确。3K 与平凡图构成的非连通图中有四个顶点三条边,显然它不是树。 例2设树T 中有2n 个度为1的顶点,有3n 个度为2的顶点,有n 个度为3的顶点,则这棵树有多少个顶点和多少条边
解:设T 有p 个顶点,q 条边,则123161q p n n n n =-=++-=-。由 deg()2v V v q ∈=∑有:1223322(61)122n n n q n n ?+?+?==-=-,解得:n =2。 故11,12q p ==。 例3证明恰有两个顶点度数为1的树必为一条通路。 证:设T 是一棵具有两个顶点度数为1的(,)p q 树,则1q p =-且 1 deg()2p i i v q ==∑2(1)p =-。 又T 除两个顶点度数为1外,其他顶点度均大于等于2,故 2 1 1 deg()2deg()2(1)p p i i i i v v p -===+=-∑∑,即 2 1 deg()2(2)p i i v p -==-∑。 因此2p -个分支点的度数都恰为2,即T 为一条通路。 例4 画出具有4、5、6、7个顶点的所有非同构的无向树。 解:4个顶点的非同构的无向树有两棵,如图21(),()a b 所示; 5个顶点的非同构的无向树有3棵,如图21(),(),()c d e 所示。 (a ) (b) (c) (d) (e) 图2 6个顶点的非同构的无向树有6棵,如图3所示。 图3 7个顶点的非同构的无向树有11棵,如图4所示。 所画出的树具有6条边,因而七个顶点的度数之和应为12。由于每个顶点的度数均大于等于1,因而可产生以下七种度数序列127(,,,)d d d L : (1)1111116;(2)1111125;(3)1111134;(4)1111224; (5)1111233;
概率论与数理统计习题 集及答案 Company number:【WTUT-WT88Y-W8BBGB-BWYTT-19998】
《概率论与数理统计》作业集及答 案 第1章概率论的基本概念 §1 .1 随机试验及随机事件 1. (1) 一枚硬币连丢3次,观察正面H﹑反面T 出现的情形. 样本空间是: S= ; (2) 一枚硬币连丢3次,观察出现正面的次数. 样本空间是: S= ; 2.(1) 丢一颗骰子. A:出现奇数点,则A= ;B:数点大于2,则 B= . (2) 一枚硬币连丢2次, A:第一次出现正面,则A= ; B:两次出现同一面,则= ; C:至少有一次出现正面,则 C= . §1 .2 随机事件的运算 1. 设A、B、C为三事件,用A、B、C的运算关系表示下列各事件: (1)A、B、C都不发生表示为: .(2)A与B都发生,而C不发生表示为: . (3)A与B都不发生,而C发生表示为: .(4)A、B、C中最多二个发生表示为: . (5)A、B、C中至少二个发生表示为: .(6)A、B、C中不多于一个发生表示为: . 2. 设}4 =x B = x ≤ ≤ x < S:则 x A x 2: 1: 3 }, { { }, = {≤< 0: 5 ≤
(1)=?B A ,(2)=AB ,(3) =B A , (4)B A ?= ,(5)B A = 。 §1 .3 概率的定义和性质 1. 已知6.0)(,5.0)(,8.0)(===?B P A P B A P ,则 (1) =)(AB P , (2)()(B A P )= , (3))(B A P ?= . 2. 已知, 3.0)(,7.0)(==AB P A P 则)(B A P = . §1 .4 古典概型 1. 某班有30个同学,其中8个女同学, 随机地选10个,求:(1)正好有2个女同学的概率, (2)最多有2个女同学的概率,(3) 至少有2个女同学的概率. 2. 将3个不同的球随机地投入到4个盒子中,求有三个盒子各一球的概率. §1 .5 条件概率与乘法公式 1.丢甲、乙两颗均匀的骰子,已知点数之和为7, 则其中一颗为1的概率是 。 2. 已知,2/1)|(,3/1)|(,4/1)(===B A P A B P A P 则 =?)(B A P 。 §1 .6 全概率公式 1. 有10个签,其中2个“中”,第一人随机地抽一个签,不放回,第二人再随 机地抽一个签,说明两人抽“中‘的概率相同。
·1· 习 题 一 1.写出下列随机试验的样本空间及下列事件中的样本点: (1)掷一颗骰子,记录出现的点数. A =‘出现奇数点’; (2)将一颗骰子掷两次,记录出现点数. A =‘两次点数之和为10’,B =‘第一次的点数,比第二次的点数大2’; (3)一个口袋中有5只外形完全相同的球,编号分别为1,2,3,4,5;从中同时取出3只球,观察其结果,A =‘球的最小号码为1’; (4)将,a b 两个球,随机地放入到甲、乙、丙三个盒子中去,观察放球情况,A =‘甲盒中至少有一球’; (5)记录在一段时间内,通过某桥的汽车流量,A =‘通过汽车不足5台’,B =‘通过的汽车不少于3台’。 解 (1)123456{,,,,,}S e e e e e e =其中i e =‘出现i 点’1,2,,6i = , 135{,,}A e e e =。 (2){(1,1),(1,2),(1,3),(1,4),(1,5),(1,6)S = (2,1),(2,2),(2,3),(2,4),(2,5),(2,6) (3,1),(3,2),(3,3),(3,4),(3,5),(3,6) (4,1),(4,2),(4,3),(4,4),(4,5),(4,6) (5,1),(5,2),(5,3),(5,4),(5,5),(5,6) (6,1),(6,2),(6,3),(6,4),(6,5),(6,6)}; {(4,6),(5,5),(6,4)}A =; {(3,1),(4,2),(5,3),(6,4)}B =。 (3){(1,2,3),(2,3,4),(3,4,5),(1,3,4),(1,4,5),(1,2,4),(1,2,5)S = (2,3,5),(2,4,5),(1,3,5)} {(1,2,3),(1,2,4),(1,2,5),(1,3,4),(1,3,5),(1,4,5)}A = (4){(,,),(,,),(,,),(,,),(,,),(,,),S ab ab ab a b a b b a =--------- (,,),(,,,),(,,)}b a a b b a ---,其中‘-’表示空盒; {(,,),(,,),(,,),(,,),(,,)}A ab a b a b b a b a =------。 (5){0,1,2,},{0,1,2,3,4},{3,4,}S A B === 。 2.设,,A B C 是随机试验E 的三个事件,试用,,A B C 表示下列事件: (1)仅A 发生; (2),,A B C 中至少有两个发生;
姓名: 班级: 学号: 遵 守 考 试 纪 律 注 意 行 为 规 范 哈尔滨工业大学(威海)2014 / 2015学年春季学期 集合论与图论 试题卷(A ) 考试形式(开、闭卷):闭卷 答题时间:105(分钟)本卷面成绩占课程成绩 30 % 试卷说明: [1] 卷面总分100分,取卷面成绩的70%计入总分,平时成绩30%。 [2] 填空题请在答题卡内答题,其它处无效。 [3] 答卷时禁止拆开试卷钉,背面即为草稿纸。 一、填空题(每小题2分,共20分)
(1) 集合的()表示方法可能产生悖论。 (2) 映射f左可逆的充分必要条件是:()。 (3) 设R={(a, b),(c, d),(e, f)}是一个二元关系,则R的逆记为R-1,R-1=()。 (4) n个顶点的完全图的边的个数是( )。 (5) 一个无向图的边数为20,那么所有顶点的度数和为()。 (6) 设G是一个有p个顶点q条边的最大可平面图,则: q=( )。 (7) 一个图是树当且仅当G是连通的且p=()。 (8) G是一个p个顶点q条边的最大平面图,则G的每个面都是( )形。 (9) 若G是偶数个顶点的圈,则G是()色的。 (10) 当顶点数大于2时,树的连通度是()。
二、简答题(每小题5分,共20分) 1.设集合X={a,b,c,d,e},E={a,b,c}是X的子集。写出E的特征函数。 2.R={(1,b),(2,c),(3,a),(4,d)}是集合A={1,2,3,4}到集合B={a,b,c,d}的一个二元关系,画出R的关系矩阵和关系图。 3.举例说明什么是偏序关系?什么是偏序集? 4.简述图的连通度、边连通度、最小度之间的关系。
第一章随机事件及其概率 1. 写出下列随机试验的样本空间: (1)同时掷两颗骰子,记录两颗骰子的点数之和; (2)在单位圆内任意一点,记录它的坐标; (3)10件产品中有三件是次品,每次从其中取一件,取后不放回,直到三件次品都取出为止,记录抽取的次数; (4)测量一汽车通过给定点的速度. 解所求的样本空间如下 (1)S= {2,3,4,5,6,7,8,9,10,11,12} (2)S= {(x, y)| x2+y2<1} (3)S= {3,4,5,6,7,8,9,10} (4)S= {v |v>0} 2. 设A、B、C为三个事件,用A、B、C的运算关系表示下列事件: (1)A发生,B和C不发生; (2)A与B都发生,而C不发生; (3)A、B、C都发生;
(4)A、B、C都不发生; (5)A、B、C不都发生; (6)A、B、C至少有一个发生; (7)A、B、C不多于一个发生; (8)A、B、C至少有两个发生. 解所求的事件表示如下 3.在某小学的学生中任选一名,若事件A表示被选学生是男生,事件B表示该生是三年级学生,事件C表示该学生是运动员,则 (1)事件AB表示什么? (2)在什么条件下ABC=C成立? ?是正确的? (3)在什么条件下关系式C B (4)在什么条件下A B =成立? 解所求的事件表示如下 (1)事件AB表示该生是三年级男生,但不是运动员. (2)当全校运动员都是三年级男生时,ABC=C成立. ?是正确的. (3)当全校运动员都是三年级学生时,关系式C B
(4)当全校女生都在三年级,并且三年级学生都是女生时,A B =成立. 4.设P (A )=,P (A -B )=,试求()P AB 解 由于 A ?B = A – AB , P (A )= 所以 P (A ?B ) = P (A ?AB ) = P (A )??P (AB ) = , 所以 P (AB )=, 故 ()P AB = 1? = . 5. 对事件A 、B 和C ,已知P(A) = P(B)=P(C)=1 4 ,P(AB) = P(CB) = 0, P(AC)= 1 8 求A 、B 、C 中至少有一个发生的概率. 解 由于,()0,?=ABC AB P AB 故P(ABC) = 0 则P(A+B+C) = P(A)+P(B)+P(C) –P(AB) –P(BC) –P(AC)+P(ABC) 6. 设盒中有α只红球和b 只白球,现从中随机地取出两只球,试求下列事件的概率: A ={两球颜色相同}, B ={两球颜色不同}. 解 由题意,基本事件总数为2a b A +,有利于A 的事件数为2 2a b A A +,有利于B 的事件数为111111 2a b b a a b A A A A A A +=, 则 2 2 11 2 22()()a b a b a b a b A A A A P A P B A A +++==
-- 本试卷满分90分 (计算机科学与技术学院09级各专业) 一、填空(本题满分10分,每空各1分) 1.设B A ,为集合,则A B B A = )\(成立的充分必要条件是什么?(A B ?) 2.设}2,1{},,,2,1{==Y n X ,则从X 到Y 的满射的个数为多少?(22-n ) 3.在集合}11,10,9,8,4,3,2{=A 上定义的整除关系“|”是A 上的偏序关系, 则 最大元是什么? ( 无 ) 4.设{,,}A a b c =,给出A 上的一个二元关系,使其同时不满足自反性、反自 反性、对称性、反对称和传递性的二元关系。({(,),(,),(,),(,)}R a a b c c b a c =) 5.设∑为一个有限字母表,∑上所有字(包括空字)之集记为*∑,则*∑是 否是可数集? ( 是 ) 6.含5个顶点、3条边的不同构的无向图个数为多少? ( 4 ) 7.若G 是一个),(p p 连通图,则G 至少有多少个生成树? ( 3 ) 8. 如图所示图G ,回答下列问题: (1)图G 是否是偶图? ( 不是 ) (2)图G 是否是欧拉图? ( 不是 ) (3)图G 的色数为多少? ( 4 ) 二、简答下列各题(本题满分40分) 1.设D C B A ,,,为任意集合,判断下列等式是否成立?若成立给出证明,若不 成立举出反例。(6分) (1))()()()(D B C A D C B A ??=? ; (2)()()()()A B C D A C B D ?=??。 解:(1)不成立。例如}{,a c B D A ====φ即可。 (2)成立。(,)x y ?∈()()A B C D ?,有,x A B y C D ∈∈,即 ,,,x A x B y C y D ∈∈∈∈。所以(,),(,)x y A C x y B D ∈?∈?,因此 (,)()()x y A C B D ∈??,从而()()A B C D ??()()A C B D ??。 反之,(,)x y ?∈()()A C B D ??,有,,,x A x B y C y D ∈∈∈∈。即 (,)x y ∈()()A B C D ?,从而()()A C B D ???()()A B C D ?。
第一章 事件与概率 1.写出下列随机试验的样本空间。 (1)记录一个班级一次概率统计考试的平均分数 (设以百分制记分)。 (2)同时掷三颗骰子,记录三颗骰子点数之和。 (3)生产产品直到有10件正品为止,记录生产产 品的总件数。 (4)对某工厂出厂的产品进行检查,合格的记上 “正品”,不合格的记上“次品”,如连续查出2个次品 就停止检查,或检查4个产品就停止检查,记录检查的 结果。 (5)在单位正方形内任意取一点,记录它的坐标。 (6)实测某种型号灯泡的寿命。 解(1)},100,,1,0{n i n i ==Ω其中n 为班级人数。 (2)}18,,4,3{ =Ω。 (3)},11,10{ =Ω。 (4)=Ω{00,100,0100,0101,0110,1100, 1010,1011,0111,1101,0111,1111},其中 0表示次品,1表示正品。 (5)=Ω{(x,y)| 0 (2)A 与B 都发生,而C 不发生。 (3)A ,B ,C 中至少有一个发生。 (4)A ,B ,C 都发生。 (5)A ,B ,C 都不发生。 (6)A ,B ,C 中不多于一个发生。 (7)A ,B ,C 至少有一个不发生。 (8)A ,B ,C 中至少有两个发生。 解 (1)C B A ,(2)C AB ,(3)C B A ++,(4)ABC , (5)C B A , (6)C B C A B A ++或 C B A C B A C B A C B A +++, (7)C B A ++, (8)BC AC AB ++或 ABC BC A C B A C AB ??? 3.指出下列命题中哪些成立,哪些不成立,并作 图说明。 (1)B B A B A =(2)AB B A = (3)AB B A B =?则若,(4)若 A B B A ??则, (5)C B A C B A = (6)若Φ=AB 且A C ?, 二、应用题 题0:(1996年全国数学联赛) 有n(n≥6)个人聚会,已知每个人至少认识其中的[n/2]个人,而对任意的[n/2]个人,或者其中有两个人相互认识,或者余下的n-[n/2]个人中有两个人相互认识。证明这n个人中必有3个人互相认识。 注:[n/2]表示不超过n/2的最大整数。 证明将n个人用n个顶点表示,如其中的两个人互相认识,就在相应的两个顶点之间连一条边,得图G。由条件可知,G是具有n个顶点的简单图,并且有 (1)对每个顶点x,) N G≥[n/2]; (x (2)对V的任一个子集S,只要S=[n/2],S中有两个顶点相邻或V-S中有 两个顶点相邻。 需要证明G中有三个顶点两两相邻。 反证,若G中不存在三个两两相邻的顶点。在G中取两个相邻的顶点x1和y1,记N G(x1)={y1,y2,……,y t}和N G(y1)={x1,x2,……,x k},则N G(x1)和N G(y1)不相交,并且N G(x1)(N G(y1))中没有相邻的顶点对。 情况一;n=2r:此时[n/2]=r,由(1)和上述假设,t=k=r且N G(y1)=V-N G(x1),但N G(x1)中没有相邻的顶点对,由(2),N G(y1)中有相邻的顶点对,矛盾。 情况二;n=2r+1: 此时[n/2]=r,由于N G(x1)和N G(y1)不相交,t≥r,k≥r,所以r+1≥t,r+1≥k。若t=r+1,则k=r,即N G(y1)=r,N G(x1)=V-N G(y1),由(2),N G(x1)或N G(y1)中有相邻的顶点对,矛盾。故k≠r+1,同理t≠r+1。所以t=r,k=r。记w∈V- N G(x1) ∪N G(y1),由(2),w分别与N G(x1)和N G(y1)中一个顶点相邻,设wx i0∈E, wy j0∈E。若x i0y j0∈E,则w,x i0, y j0两两相邻,矛盾。若x i0y j0?E,则与x i0相邻的顶点只能是(N G(x1)-{y j0})∪{w},与y j0相邻的顶点只能是(N G(y1)-{x j0})∪{w}。但与w相邻的点至少是3,故N G(x1)∪N G(y1)中存在一个不同于x i0和y j0顶点z与w相邻,不妨设z∈N G(x1),则z,w,x i0两两相邻,矛盾。 题1:已知图的结点集V={a,b,c,d}以及图G和图D的边集合分别为: E(G)={(a,a), (a,b), (b,c), (a,c)} E(D)={, , 第六章树及割集 习题课1 课堂例题 例1设T是一棵树,T有3个度为3顶点,1个2度顶点,其余均是1度顶点。则 (1)求T有几个1度顶点? (2)画出满足上述要求的不同构的两棵树。 分析:对于任一棵树T,其顶点数p和边数q的关系是:q P 1且 p deg(vj 2q,根据这些性质容易求解。 i 1 解:(1)设该树T的顶点数为p,边数为q,并设树T中有x个1 度顶点。于是 p deg(v)3312 x 2q 且p 3 1 x,q p 1,得x 5。 i 1 (2)满足上述要求的两棵不同构的无向树,如图1所示。 图1 例2设G是一棵树且(G)k,证明G中至少有k个度为1顶点。证:设T中有p个顶点,s个树叶,则T中其余p s个顶点的度数均大于等于2,且至少有一个顶点的度大于等于k。由握手定理可得: p 2q 2 p 2 deg(v i) 2( p s 1) k s,有s k。 i 1 所以T中至少有k个树叶。 习题 例1若无向图G中有p个顶点,p 1条边,则G为树。这个命题正确吗? 为什么? 解:不正确。心与平凡图构成的非连通图中有四个顶点三条边,显然它不是树。 例2设树T中有2n个度为1的顶点,有3n个度为2的顶点,有n个度为 3的顶点,则这棵树有多少个顶点和多少条边? 解:设T 有p 个顶点,q 条边,则q P 1 2 n 3n n 1 6n 1。由 deg(v) 2q 有:1 2n 2 3n 3 n 2q 2(6n 1) 12n 2,解得:n =2。 v V 故 q 11, p 12。 例3证明恰有两个顶点度数为1的树必为一条通路。 证:设T 是一棵具有两个顶点度数为 1的(p,q)树,则q p 1且 p deg(V i ) 2q 2(p 1)。 i 1 外,其他顶点度均大于等于2,故 p 2 deg(V i ) 2( p 1),即 i 1 p 2 deg(V i ) 2( p 2)。 i 1 因此p 2个分支点的度数都恰为2,即T 为一条通路。 例4画出具有4、5、6、7个顶点的所有非同构的无向树。 解:4个顶点的非同构的无向树有两棵,如图 21(a),(b)所示; 5个顶点的非同构的无向树有3棵,如图21(c),(d),(e)所示。 (a ) (b) (c) (d) (e) 图2 6个顶点的非同构的无向树有6棵,如图3所示 图3 7个顶点的非同构的无向树有11棵,如图4所示。 所画出的树具有6条边,因而七个顶点的度数之和应为 12。由 于每个顶点的度数均大于等于 1,因而可产生以下七种度数序列 (d 1,d 2,L ,d 7): (1)1111116;(2)1111125;(3)1111134 ;(4)1111224 ;(5)1111233 ; (6) 1112223; (7) 1122222。 又T 除两个顶点度数为 p deg(v) i 1图论习题参考答案
哈工大集合论习题课第六章树及割集习题课