ÑAÏI HOÏC QUOÁC GIA TP HOÀ CHÍ MINH
TRÖÔØNG ÑAÏI HOÏC KHOA HOÏC TÖÏ NHIEÂN
------------------------
Baøi taäp
TOAÙN RÔØI RAÏC
Naâng cao
LÖU HAØNH NOÄI BOÄ
Naêm hoïc 2007-2008
Chöông 1. ÑAÏI CÖÔNG VEÀ ÑOÀ THÒ
Baøi 1.1 Trong moät böõa tieäc, moïi ngöôøi baét tay nhau. Chöùng minh raèng
soá ngöôøi baét tay vôùi 1 soá leû ngöôøi khaùc laø soá chaün.
Baøi 1.2 Trong 1 giaûi ñaáu côø theo theå ñaáu voøng troøn 1 löôït, chöùng minh
raèng taïi moïi thôøi ñieåm cuûa giaûi, luoân luoân coù 2 ñaáu thuû coù soá vaùn ñaõ thi
ñaáu baèng nhau.
Baøi 1.3 Moät böõa tieäc coù 6 ngöôøi tham döï. Chöùng minh raèng coù 3 ngöôøi
quen nhau hoaëc coù 3 ngöôøi khoâng quen nhau.
Baøi 1.4 Chöùng minh 2 ñoà thò trong Hình 1.17a vaø 1.17b ñaúng caáu.
dc
eb
a
ih
jg
f
Hình 1.17a
a
b
c
d
e
f
gh
i
j
Hình 1.17b
Baøi 1.5 Chöùng minh 2 ñoà thò trong Hình 1.18a vaø 1.18b ñaúng caáu.
Baøi 1.6 Hai ñoà thò trong Hình 1.19a vaø 1.19b coù ñaúng caáu khoâng? Giaûi
thích.
Baøi 1.7 Xeùt tính ñaúng caáu cuûa hai ñoà thò trong Hình 1.20a vaø 1.20b.
3
✬
✫
✩
✪
•❛❛❛
❛
✦
✦
✦
✦✄
✄
✄
✄
✄
✄
✄
✄
❉❉❉❉❉❉❉❉
•
✆
✆
✆
✆
❡❡❡❡❡❡
❍❍❍❍❍❍❍
❍
•
❊❊❊❊
✟
✟
✟
✟
✟
✟
✟
✟
✪
✪
✪
✪
✪
✪
•
❡❡
❡
•
✪
✪
✪
••
(a)
•❛❛❛
❛
✦
✦
✦
✦✪
✪
✪
✪
✪
❙❙❙❙❙
•
✆
✆
✆
✆
❈❈❈❈❈❈
❈
•
❊❊❊❊
✄
✄
✄
✄
✄
✄
✄
•
❡❡
❡
❛❛❛❛❛
❛
•
✪
✪
✪
•
✦✦✦✦✦
✦
•
(b)
Hình 1.18
✬
✫
✩
✪
•
❅❅❅
•
••
••
• •
❅
❅❅
(a)
•
❅❅❅
•

••
••
• •
(b)
Hình 1.19
✬
✫
✩
✪
•
❚❚❚❚❚❚❚
✇
✔
✔
✔
✔
✔
✔
✔
✴❄
•
❩❩❩❩❩
⑥
✚
✚
✚
✚✚
❂
•✲•
(a)
•
❚❚❚❚❚❚❚
✇
✔
✔
✔
✔
✔
✔
✔
✴✻
•
❩❩❩❩❩
⑥
✚
✚
✚
✚✚
❂
•✲•
(b)
Hình 1.20
4
Baøi 1.8 Moät ñôn ñoà thò Gñöôïc goïi laø töï buø neáu G≃G.
a) Chöùng minh raèng neáu Gtöï buø thì soá ñænh cuûa Glaø 4khay 4k+1,
vôùi knguyeân döông.
b) Tìm taát caû caùc ñoà thò töï buø coù 4 ñænh vaø 5 ñænh.
Baøi 1.9 Giaûi baøi toaùn instant insanity trong Hình 1.21.
✬
✫
✩
✪
R
Y
W
Y
BR R
W
W
R
BW
R
Y
Y
W
RB R
Y
W
B
RY
(1) (2)
(3) (4)
Hình 1.21
Baøi 1.10 Cho Glaø ñoà thò ñôn, khoâng höôùng. Ñoà thò ñöôøng cuûa G, kyù
hieäu L(G), ñöôïc xaùc ñònh nhö sau: Moãi caïnh cuûa Glaø 1 ñænh cuûa L(G),
hai ñænh cuûa L(G)keà nhau khi vaø chæ khi hai caïnh töông öùng trong G
keà nhau.
a) Chöùng minh K3vaø K1,3coù cuøng ñoà thò ñöôøng.
b) Tìm soá caïnh cuûa L(G)theo baäc cuûa caùc ñænh trong G.
5