NGuyên lý chuồng và thỏ ppsx

Nguyên lý chuồng và thỏ (hay còn ñược gọi là nguyên lý Dirichlet) khẳng ñịnh một sự

kiện “hiển nhiên” rằng n+1 con thỏ không thể ñược xếp vào n chuồng sao cho mỗi con

thỏ ñều ở riêng một chuồng. Một cách tổng quát hơn, nguyên lý chuồng và thỏ khẳng

ñịnh rằng:

Nếu một tập hợp gồm nhiều hơn kn ñối tượng ñược chia thành n nhóm, thì có một nhóm

nào ñó có nhiều hơn k ñối tượng.

Chân lý này rất dễ kiểm tra: nếu nhóm nào cũng có nhiều nhất k ñối tượng thì tổng cộng

chỉ có nhiều nhất kn ñối tượng ñược chia ra.

Đây là một trong những nguyên lý không xây dựng (non-constructive) lâu ñời nhất: nó

chỉ nói ñến sự tồn tại của một chuồng trong ñó có nhiều hơn k vật mà không nói gì ñến

cách tìm ra chuồng này. Ngày nay chúng ta ñã có những tổng quát hóa rất mạnh của

nguyên lý này (các ñịnh lý kiểu Ramsey, phương pháp xác suất…).

Mặc dù nguyên lý chuồng và thỏ ñược phát biểu rất ñơn giản, nó có hàng loạt các ứng

dụng không tầm thường. Cái khó của việc ứng dụng nguyên lý này là xác ñịnh ñược xem

thỏ là gì và chuồng là gì. Chúng ta sẽ minh họa ñiều này bằng một số ví dụ.

1. Một số ví dụ mở ñầu

Để khởi ñộng, chúng ta sẽ bắt ñầu bằng những ứng dụng ñơn giản nhất. Bậc của một ñỉnh

trong ñồ thị G là số d(x) các cạnh của G kề với x.

Mệnh ñề 1. Trong mọi ñồ thị tồn tại hai ñỉnh có cùng bậc.

Chứng minh. Giả sử ta có ñồ thị G có n ñỉnh. Ta tạo ra n cái chuồng ñược ñánh số từ 0

ñến n-1 và xếp ñỉnh x vào chuồng thứ k khi và chỉ khi d(x) = k. Nếu như trong một

chuồng nào ñó có nhiều hơn 1 ñỉnh thì ta có ñpcm. Vì thế ta có thể giả sử rằng không có

chuồng nào chứa hơn 1 ñỉnh. Có tất cả n ñỉnh ñược chia vào n cái chuồng, nhưng vậy mỗi

một chuồng có ñúng 1 ñỉnh. Gọi x và y là các ñỉnh nằm trong các chuồng ñánh số 0 và n￾1 tương ứng. Đỉnh x có bậc 0 vì vậy nó không ñược nối với các ñỉnh khác, trong ñó có y.

Nhưng y có bậc n-1 nên nó lại ñược nối với tất cả các ñỉnh, trong ñó có x, mâu thuẫn.

Nếu G là một ñồ thị hữu hạn, chỉ số ñộc lập (independent number) α(G) là số lớn nhất

các ñỉnh ñôi một không kề nhau của G. Sắc số (chromatic number) χ(G) của G là số nhỏ

nhất các màu cần dùng ñể tô các màu của G sao cho không có hai ñỉnh kề nhau ñược tô

cùng màu.

www.laisac.page.tl

NG UYÊ N L Ý CH UỒ NG VÀ T H Ỏ 

TS. Trần Nam Dũng