Bài viết đã được chỉnh sửa nội dung bởi HUYVAN: 17-05-2007 - 11:17
Bài 2
Bắt đầu bởi HUYVAN, 17-05-2007 - 11:14
#1
Đã gửi 17-05-2007 - 11:14
Đồ 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.
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh