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.