Bài tập học về môn Toán rời rạc

Toán học rời rạc (tiếng Anh: discrete mathematics) là tên chung của nhiều ngành toán học có đối tượng nghiên cứu là các tập hợp rời rạc, các ngành này được tập hợp lại từ khi xuất hiện khoa học máy tính làm thành cơ sở toán học của khoa học máy tính.
Nội dung trích xuất từ tài liệu:
Bài tập học về môn Toán rời rạc ÑAÏI HOÏC QUOÁC GIA TP HOÀ CHÍ MINHTRÖÔØ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-2008Chöô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èngsoá 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 minhraè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öôøiquen 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. a f a f g h e j g b e j b i h i d c d c Hình 1.17a Hình 1.17bBaø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ûithí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 !•a !!! D aa a !!! % S aa a H •e • H D %•E C % S • E H D e H % E H C% S E e D%H E %C S E •e e% D H H•E % •a C ! SE !• %e D % e aCa % e % eD % e C !a !a!!% e• a % •% e• • (a) (b)& % Hình 1.18 $•@ • •@ • @• • @• • • •@ • •• @• • • (a) (b)& % Hình 1.19 $ T • T • T T ?T 6T / • wT / • wT ZZ T ZZ T = }ZT = ZT }• - ZT• • - ZT• (a) (b)& % Hình 1.20 4Baø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 G töï buø thì soá ñænh cuûa G laø 4k hay 4k + 1,vôùi k nguyeâ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. $ Y W R W B R R W B W Y R (1) (2) Y Y R Y R B R W R Y W B (3) (4) & % ...