Bồi dưỡng kiến thức cho học sinh giỏi Toán tổ hợp - Rời rạc: Phần 2

Nối tiếp nội dung phần 1 tài liệu Bồi dưỡng học sinh giỏi Toán tổ hợp - Rời rạc, phần 2 giới thiệu tới người đọc các kiến thức: Tô màu đồ thị, các bài toán rời rạc, tổng hợp và toán thi, nguyên lý Dirichlet - Định lý Ramsey. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bồi dưỡng kiến thức cho học sinh giỏi Toán tổ hợp - Rời rạc: Phần 2 Cty TNHHMiV DVVH Khang VietBoi duang hoc sinh gioi Todn to hap - roi rac, Nguyen Van Thongqua sai khong? L i l u a n cua hp c6 thuc su la m o t c h u n g m i n h hay k h o n g , neuno p h u thuoc vao t h o n g t i n tir m p t may t i n h k h o n g d a n g t i n cay? Lam Bai toan b o n m a u ap d u n g chi cho cac d o t h i phang. Cac d o t h i k h o n ^p h a n g CO the c6 somau Ian t u y y n h u se c h u n g m i n h t r o n g v i d u 2. Nau Can p h a i l a m hai dieu k h i c h u n g m i n h so mau cua d o t h i la n . T r u o c tien,c h u n g ta phai c h u n g to rang do t h i c6 the dugc to bang n m a u . D i e u nay c6 t h e Luc f Lam Luc /Lamthuc hien b a n g each to m a u d o thj do. Sau do c h i i n g ta p h a i c h u n g to rang G Hk h o n g the to m a u d o t h j v o i so m a u it h a n . Cac v i d u sau day m i n h hoa each H i n h 4. To m a u do thj G va H . . ;• t i m somau. Vi du. 2: Tim so mau cua do thj Kn. S,- ^ Vi du 1: So mau cua do thi GvdH tren htnh 3 bang bao nhieu? L a i giai L o i giai Co the xay d u n g each to m a u d o thj K n v o i n m a u khac n h a u . Co each to Somau cua G i t nhat la 3, v i cac d i n h a, b va c p h a i d u p e gan cac m a u khnr mau nao d i i n g i t m a u h o n khong? Cau tra l o i la k h o n g . K h o n g c6 hai d i n h naon h a u . De thay G c6 the to bang ba m a u ta gan m a u d o cho a, m a u l a m cho b va CO the gan c i i n g m a u v i m p i cap d i n h ciia d o thj nay deu lien ke. V i the so maum a u luc cho c. k h i d o d c6 the (va phai) to m a u d o v i no lien ke v o i b va c. Tiep ciia K n bang n . ( N h o lai rang K n la k h o n g phang neu n > 5, v i theket qua naytheo e CO the (va phai) to m a u luc v i no lien ke v a i cac d i n h m a u d o va m a u luc. khong m a u t h u a n v o i d j n h ly bon mau). Cach to m a u K5 bang 5 d u p e the hienCuoi c i i n g , g c6 the (va phai) to m a u d o v i no lien ke v o i cac d i n h m a u l a m va tren h i n h 5.m a u luc. V a y la ta da to m a u d o t h j G bang d i i n g ba m a u . H i n h 4 the hien eachto m a u n h u the. D o t h i H d u p e tao nen tLi* d o t h i G bang each t h e m vao m p t canh n o i a v o i g.m p i y d i n h to H bang ba m a u can phai tuan theo l i l u a n da d u n g k h i to mau G,t r u giai doan cuoi cung, k h i cac d i n h khac g da d u p e to m a u . V i g lien ke (tron;;H ) v o i cac d i n h m a u do, m a u l a m va m a u luc nen ta ta bupc phai d u n g mau naut h u t u , chSng han m a u nau. V i the H c6 so m a u bang 4. Cach to m a u U theh i ^ n tren h i n h 4. ^ lam ...