Bài toán kết nối facebook


Hôm nay, xin kể với các bạn về "bài toán kết nối facebook"!

Bài toán này nói rằng nếu bạn chọn bất kỳ 6 người nào trên facebook, thì trong 6 người này, bạn có thể chọn ra được 3 người mà, hoặc là, cả 3 người này đều là friend của nhau, hoặc là, trong 3 người này không có ai là friend của ai cả.

Ví dụ, như hình dưới đây, ở phía bên trái chúng ta có 6 bạn: An, Bảo, Cường, Chi, Dũng và Đạt. Nếu như hai bạn là friend của nhau trên facebook thì chúng ta kết nối họ lại bằng một đường màu tím, còn nếu họ không là friend thì chúng ta nối lại bằng đường màu xanh.

Chúng ta thấy rằng trong 6 bạn này, chúng ta có thể chọn ra 3 bạn là An, Dũng và Chi, cả 3 bạn này đều là friend của nhau bởi vì họ được nối bởi các đường màu tím. Trường hợp 3 bạn Đạt, Bảo và Cường cũng vậy.
Còn trong ví dụ phía bên phải, chúng ta có 6 bạn: Kim, Lan, Mai, Nam, Nga và Nhi. Chúng ta có thể chọn ra được 3 bạn là Nga, Mai và Nam, trong 3 bạn này không có ai là friend của ai cả bởi vì các bạn này được nối bởi các đường màu xanh. Ba bạn Nhi, Nam và Mai cũng vậy.




Qua bài toán này chúng ta làm quen với một loại toán gọi là toán đồ thị. Một đồ thị bao gồm các đỉnh và các cạnh. Cạnh dùng để nối hai đỉnh lại với nhau. Đồ thị trong bài toán của chúng ta có 6 đỉnh tượng trưng cho 6 người, giữa hai đỉnh bất kỳ được nối bằng một cạnh, và các cạnh này được tô bằng hai màu là xanh và tím. Sau đây là một vài ví dụ về đồ thị.


Có lẽ bài toán đầu tiên về lý thuyết đồ thị là bài toán về 7 cây cầu ở Königsberg của Euler. Thành phố Königsberg bây giờ có tên là Kaliningrad ở Nga. Nếu các bạn dùng Google Map để tìm kiếm thì sẽ thấy bây giờ các cây cầu ở Kaliningrad đã khác xa so với thời của Euler.
Thành phố Kaliningrad hiện nay

Vào thời của Euler, 1736, thành phố Königsberg có 7 cây cầu như hình sau đây
7 cây cầu ở Königsberg vào thời Euler (tô bằng màu tím)

Bài toán mà Euler đặt ra là liệu có cách nào để đi một vòng quanh thành phố làm sao để mỗi cây cầu được đi qua đúng một lần hay không. Euler đã dùng đồ thị để chứng minh rằng câu trả lời là không thể.

Để chứng minh điều này, Euler tạo ra một đồ thị gồm 4 đỉnh A, B, C, D tượng trưng cho 4 vùng đất như hình dưới đây. Bốn vùng đất này ngăn cách nhau bởi một dòng sông và muốn đi từ vùng đất này sang vùng đất kia chúng ta phải đi qua cầu. Euler dùng cạnh của đồ thị để tượng trưng cho các cây cầu nối liền các vùng đất này. Ví dụ như giữa vùng A và B có hai cây cầu, nên trong đồ thị sẽ có hai cạnh nối liền hai đỉnh A và B.




Như vậy, bài toán đặt ra là liệu có thể đi qua tất cả các cạnh của đồ thị mà mỗi cạnh được đi qua đúng duy nhất một lần hay không. Một đường đi như vậy gọi là một đường đi Euler.

Để biết được đồ thị có đường đi Euler hay không chúng ta phải đếm xem đồ thị có bao nhiêu đỉnh bậc lẻ và bao nhiêu đỉnh bậc chẳn. Ở đây, bậc của một đỉnh có nghĩa là số cạnh của đỉnh đó. Chúng ta thấy ở đồ thị trên thì đỉnh A có bậc 5 (lẻ), đỉnh B có bậc 3 (lẻ), đỉnh C có bậc 3 (lẻ) và đỉnh D có bậc 3 (lẻ). Như vậy đồ thị có 4 đỉnh bậc lẻ.

Với một đồ thị mà các đỉnh liên thông với nhau, đường đi Euler chỉ tồn tại khi và chỉ khi đồ thị không có đỉnh bậc lẻ nào, hoặc là đồ thị có đúng hai đỉnh bậc lẻ. Vì đồ thị trên có 4 đỉnh bậc lẻ, nên đường đi Euler sẽ không tồn tại.


Hai đồ thị dưới đây có tồn tại đường đi Euler bởi vì đồ thị bên trái thì có 2 đỉnh có bậc lẻ, còn đồ thị bên phải thì không có đỉnh bậc lẻ nào. Điều này có nghĩa là bạn có thể dùng bút và vẽ được đồ thị này trên giấy bằng một nét mà không cần phải nhấc bút lên khỏi tờ giấy.



Bây giờ quay trở lại với bài toán về 6 người kết nối facebook của chúng ta. Nếu phát biểu theo ngôn ngữ đồ thị thì bài toán của chúng ta sẽ như sau.


Bài toán: Cho một đồ thị gồm 6 đỉnh mà hai đỉnh bất kỳ được nối bằng một cạnh có màu xanh hoặc màu tím. Chứng minh rằng tồn tại một tam giác có các cạnh đều là màu tím hoặc đều là màu xanh.



Chúng ta sẽ dùng nguyên lý Dirichlet để chứng minh bài toán trên. Nguyên lý Dirichlet phát biểu một cách nôm na là nếu chúng ta nhốt 5 con chim bồ câu vào hai cái chuồng thì sẽ có một chuồng có ít nhất là 3 con bồ câu.


nguyên lý Dirichlet: nhốt 5 con chim vào hai cái chuồng thì sẽ có ít nhất 3 con chim ở trong cùng một chuồng


Quay lại với đồ thị facebook, chúng ta chọn một đỉnh bất kỳ, chẳng hạn như đỉnh "An". Từ đỉnh "An" chúng ta có 5 cạnh. Chúng ta xem 5 cạnh này như 5 con chim bồ câu, nếu cạnh màu tím thì nhốt vào chuồng màu tím, còn cạnh màu xanh thì nhốt vào chuồng màu xanh.


Theo nguyên lý Dirichlet thì sẽ có một chuồng có ít nhất là 3 con chim bồ câu. Chúng ta giả sử đó là chuồng màu tím. Có nghĩa là chúng ta có ít nhất 3 cạnh màu tím.

Giả sử như cạnh An-Dũng, cạnh An-Chi và cạnh An-Cường là màu tím như hình vẽ trên.



Bây giờ chúng ta xem xét tam giác Dũng-Chi-Cường. Nếu một cạnh của tam giác này là màu tím, chẳng hạn như cạnh Dũng-Chi màu tím như hình vẽ phía bên trái dưới đây, thì chúng ta sẽ có một tam giác màu tím là An-Dũng-Chi. Trường hợp ngược lại, nếu tam giác Dũng-Chi-Cường không có cạnh nào màu tím như hình vẽ phía bên phải, thì chúng ta sẽ có một tam giác màu xanh Dũng-Chi-Cường.


Tóm lại, trong mọi trường hợp, thì chúng ta luôn tìm được một tam giác có ba cạnh màu tím hoặc cả ba cạnh màu xanh, và như vậy bài toán đã được chứng minh xong.


Hôm nay chúng ta đã dùng đồ thị để chứng minh được một kết quả thú vị sau đây

Chọn bất kỳ 6 người nào trên facebook, thì trong 6 người này, bạn có thể chọn ra được 3 người mà, hoặc là, cả 3 người này đều là friend của nhau, hoặc là, trong 3 người này không có ai là friend của ai cả.


Con số 6 người là con số tối ưu bởi vì nếu chúng ta chỉ chọn ra 5 người thì tính chất này không còn đúng nữa như hình vẽ sau đây.
trong đồ thị 5 đỉnh này, không tồn tại tam giác có ba cạnh cùng màu

Bài toán này thực ra là một trường hợp nhỏ của một bài toán rất phức tạp, đó là bài toán Ramsey. Có cả một nhánh riêng của toán học phát triển để nghiên cứu về bài toán này, gọi là lý thuyết Ramsey. Có dịp thuận tiện chúng ta sẽ quay trở lại với bài toán này.



Nhân tiện nói về kết nối facebook, bạn có biết rằng blog Vườn Toán vừa mới mở ra một trang facebook. Xin mời các bạn kết nối với blog Vườn Toán qua link dưới đây. Và nếu các bạn thích những gì đã đọc được trên blog này thì xin hãy "Like" và "Share" với các bạn của mình.




Xin hẹn gặp lại các bạn ở kỳ sau.