Chưa có bài trả lời

[HUYVAN]

Đồ thị đầy đủ $n$ đỉnh là một tập hợp gồm $n$ đỉnh và các đỉnh đó được nối với nhau đôi một bởi các cạnh. Giả sử đồ thị có $n$ đỉnh $A_1, A_2, ..., A_n$, chu trình là một tập hợp các cạnh có dạng $A_i_{1} A_i_{2}, A_i_{2}A_i_{3}, ..., A_i_{m}A_i_{1}$, với $i_1, i_2, ..., i_m\in \{1, 2, ..., n}$ đôi một khác nhau. Ta gọi $m$ là độ dài của chu trình này. Tìm số nguyên dương $n$ nhỏ nhất sao cho với mọi cách tô màu tất cả các cạnh của một đồ thị đầy đủ $n$ đỉnh, mỗi cạnh được tô bởi một trong ba màu khác nhau thì luôn tồn tại một chu trình có độ dài chẵn cùng màu.

Bài viết đã được chỉnh sửa nội dung bởi HUYVAN: 17-05-2007 - 11:17