Diễn Đàn MathScope - Clb viện toán - đồ thị

14h - 17h30 30/03/2012

Mọi người cùng trao đổi về buổi học này nhé.

A. LÝ THUYẾT

- định nghĩa đồ thị
- đỉnh, cạnh, đỉnh kề, cạnh kề, bậc (deg), đường đi, độ dài đồ thị
- dãy "đồ thị" (thuật toán chứng minh 1 dãy có là dãy đồ thị hay không)
- đồ thị liên thông, chu trình, đồ thị bù, cây, cây bao trùm
- phân hoạch đồ thị
...

B. BÀI TẬP

Bài tập 1. Tồn tại hay không một nhóm:
a. 5 người mà số các người bạn của mỗi bạn (trong nhóm bạn đó) lần lượt là 5, 3, 2, 2, 1?
b. 5 người mà số các người bạn của mỗi bạn (trong nhóm bạn đó) lần lượt là 2, 4, 4, 4?
c. 9 người mà số các người bạn của mỗi bạn (trong nhóm bạn đó) lần lượt là 6, 5, 4, 3, 3, 3, 2, 2, 2?
d. 8 người mà số các người bạn của mỗi bạn (trong nhóm bạn đó) lần lượt là 6, 6, 6, 6, 4, 3, 3, 0?

Bài tập 2. Có 32 đội bóng tham gia một giải đấu bóng đá. Ngày đầu tiên, mỗi đội chơi đúng một trận. Ngày thứ hai, mỗi đội chơi thêm đúng một trận nữa. Chứng minh rằng sau ngày thi đấu thứ hai có thể chọn ra 16 đội bóng sao cho hai đội bóng bất kì trong số đó chưa từng thi đấu với nhau.

Bài tập 3. Hai thành phố bất kì của một quốc gia nọ được kết nối trực tiếp với nhau bởi đúng một trong hai phương tiện: đường bộ hoặc hàng không. Chứng minh rằng có thể đóng tất cả các đường bộ hoặc tất cả các đường bay sao cho bằng phương tiện giao thông còn lại, người ta luôn đi được từ một thành phố bất kì đến một thành phố bất kì khác và không đi qua quá 2 thành phố trung gian khác.

Bài tập 4. Có n > 2 hòn đảo và n cây cầu kết nối chúng. Biết rằng có thể đi từ một hòn đảo bất kì đến một hòn đảo bất kì bằng cách sử dụng các cây cầu đó. Chứng minh rằng có thể tìm được một cây cầu sao cho nếu ta bỏ cây cầu đó đi, ta vẫn có thể đi từ một hòn đảo đến một hòn đảo bất kì khác.

Bài tập 5. Trong một quốc gia nọ có >= 101 thành phố và các đường bay (hai chiều) nối một số các thành phố. Biết rằng thủ đô có đường bay trực tiếp tới 100 thành phố khác và một thành phố bất kì, không phải là thủ đô, có đường bay trực tiếp đến đúng 10 thành phố khác, ngoài ra hai thành phố bất kì được nối với nhau bằng một đường bay trực tiếp hay gián tiếp. Chứng minh rằng có thể đóng một nửa số đường bay phục vụ thủ đô sao cho vẫn có thể bay từ một thành phố bất kì đến một thành phố bất kì khác.

Bài tập 6. Người ta viết các chữ số 0, 1, ..., 9, mỗi số đúng 10 lần, vào các ô vuông của một bảng 10x10. Chứng minh rằng có thể tìm được một hàng hay một cột chứa ít nhất 4 chữ số phân biệt.

Bài tập 7 (Bài giảng buồn tẻ). Cô giáo Hà Dương phát hiện ra năm bạn học sinh ngủ gật trong bài giảng của mình, hơn nữa, mỗi bạn đó ngủ gật đúng hai lần. Cô Hà Dương còn nhật thấy rằng với hai bạn bất kì, có một thời điểm mà họ cùng ngủ gật. Chứng minh rằng có ít nhất 3 bạn cùng ngủ gật ở một thời điểm nào đó.

[Only registered and activated users can see links. Click Here To Register...]

Thầy Nguyễn Chu Gia Vượng
1993. HCV IMO, 30/42
1994. HCB IMO, 31/42