1. Khái niệm cơ bản và phương pháp chung
Lý thuyết đồ thị nói chung, đặc biệt là đồ thị tô màu được vận dụng để giải các bài toán không mẫu mực rất hiệu quả.
Để giải toán thông qua đồ thị cần thực hiện theo hai bước:
- Đầu tiên xây dựng đồ thị để mô tả các quan hệ, điều kiện được phát biểu trong bài toán.
- Sau đó căn cứ vào các khẳng định của lý thuyết đồ thị để suy ra đáp án.
Định nghĩa:
- Đồ thị được gọi là đầy đủ nếu mỗi cặp đỉnh của nó đều được nối bằng một cạnh. Đồ thị đầy đủ gồm có đỉnh thường ký hiệu là \(K_n\).
- Đồ thị đầy đủ gồm 3 đỉnh (4 đỉnh) với các cạnh được tô màu bằng cùng một màu được gọi là tam giác cùng màu (hoặc tứ giác cùng màu).
2. Bài toán thực tế mở đầu
Bài toán 1 (Đề thi Olympic Toán Quốc tế): Mười bảy nhà bác học viết thư cho nhau. Mỗi người đều viết thư cho tất cả người khác. Các thư chỉ trao đổi về 3 đề tài. Từng cặp nhà bác học chỉ viết thư trao đổi về cùng một đề tài. Chứng minh rằng có ít nhất 3 nhà bác học viết thư cho nhau trao đổi về cùng một vấn đề.
Bài toán 2: Trong một cuộc gặp gỡ quốc tế có 17 nhà ngoại giao tham gia. Mỗi cặp nhà ngoại giao chỉ trao đổi trực tiếp với nhau bằng một trong ba ngôn ngữ: Anh, Pháp, Đức. Chứng minh rằng luôn tìm được ba nhà ngoại giao, mà họ có thể trao đổi trực tiếp được bằng một trong ba ngôn ngữ kể trên.
Bài toán 3: Mỗi cặp đối tượng cho trước chỉ có một trong ba quan hệ: \(t_1, t_2, t_3\). Chứng minh rằng luôn luôn tìm được ba đối tượng, mà mỗi cặp trong bộ ba này cùng có quan hệ \(t_i\) (\(1 \le i \le 3\)) đã cho.
3. Khẳng định tổng quát (Sự tồn tại tam giác cùng màu)
Xét lớp đồ thị có chứa tam giác cùng màu với các dãy số nguyên dương:
- Dãy số \((a_n)\): \[a_1 = 2,\; a_2 = 3,\; \ldots,\; a_{n+1} = (n + 1) \cdot a_n + 1 \quad (1)\]
- Dãy số \((b_n)\): \[b_2 = 3,\; b_3 = 6,\; \ldots,\; b_{n+1} = (b_n - 1) \cdot n + 2 \quad (2)\]
Khẳng định 1:
a) Đồ thị đầy đủ có \(a_n + 1\) đỉnh với \(n\) màu cạnh luôn luôn có đồ thị con đầy đủ \(K_3\) với cạnh cùng màu (tam giác cùng màu).
b) Đồ thị đầy đủ có \(b_{n+1}\) đỉnh với \(n\) màu cạnh luôn luôn có đồ thị con đầy đủ \(K_3\) với cạnh cùng màu.
Chứng minh khẳng định a) bằng quy nạp theo chỉ số \(n\):
1) Cơ sở quy nạp: Với \(n = 1\). Đồ thị đầy đủ tương ứng gồm \(a_1 + 1 = 2 + 1 = 3\) đỉnh lập thành một chu trình tam giác. Các cạnh của đồ thị này được tô bằng một màu, nên chu trình tam giác lập nên \(G_1\) cùng màu.
2) Quy nạp: Giả sử khẳng định đã đúng với \(n = k\), nghĩa là đồ thị đầy đủ bất kỳ \(G_k\) gồm \(a_k + 1\) đỉnh với các cạnh được tô bằng \(k\) màu đã có chu trình tam giác cùng màu. Cần chứng tỏ khẳng định đúng với \(n = k + 1\).
Xét đồ thị đầy đủ tùy ý \(G_{k+1}\) với \(a_{k+1} + 1\) đỉnh và các cạnh được tô bằng \(k + 1\) màu.
Giả sử \(P\) là một đỉnh tùy ý của \(G_{k+1}\). Khi đó \(P\) được nối với \(a_{k+1} = (k+1)a_k + 1\) đỉnh bởi các cạnh được tô bằng không quá \(k + 1\) màu, nên theo nguyên lý Dirichlet, xuất phát từ \(P\) phải có ít nhất \(a_k + 1\) cạnh được tô bằng cùng một màu. Giả sử màu này là màu đỏ và các cạnh đó là \(PA_1, PA_2, \ldots, PA_{a_k+1}\).
Có hai khả năng xảy ra:
\(1^\circ\)) Nếu một trong các cạnh nối giữa các đỉnh \(A_i, A_j\) (\(1 \le i, j \le a_k + 1\)) được tô màu đỏ, chẳng hạn cạnh \((A_1, A_2)\) màu đỏ. Khi đó chu trình tam giác \(A_1PA_2\) có cả 3 cạnh đều màu đỏ, tức là đồ thị \(G_{k+1}\) có chu trình tam giác màu đỏ.
\(2^\circ\)) Ngược lại, không có cạnh nào trong các cạnh \((A_i, A_j)\) (\(1 \le i, j \le a_k + 1\)) được tô màu đỏ. Khi đó đồ thị con đầy đủ \(G'_k\) với tập đỉnh \(\{A_1, A_2, \ldots, A_{a_k}, A_{a_k+1}\}\) có các cạnh được tô bằng không quá \(k\) màu. Do đó, theo giả thiết quy nạp, \(G'_k\) có chu trình tam giác cùng màu. Bởi vậy \(G_{k+1}\) có chu trình tam giác cùng màu.
Khẳng định a) được chứng minh xong.
Khẳng định b) được chứng minh tương tự.
4. Hướng dẫn xây dựng mô hình đồ thị cho các bài toán
Xây dựng đồ thị mô tả quan hệ:
Các đồ thị tương ứng với ba bài toán đã cho được xây dựng như sau:
- Đối với Bài toán 1: Biểu diễn 17 nhà bác học tương ứng với 17 đỉnh của đồ thị đầy đủ \(K_{17}\). Hai đỉnh bất kỳ được nối bằng một cạnh mang một trong 3 màu (tương ứng với 3 đề tài trao đổi).
- Đối với Bài toán 2: Biểu diễn 17 nhà ngoại giao bằng 17 đỉnh của đồ thị. Mỗi cạnh nối hai nhà ngoại giao được tô màu bởi 1 trong 3 màu (tương ứng 3 ngôn ngữ: Anh, Pháp, Đức).
- Đối với Bài toán 3: Biểu diễn các đối tượng bằng các đỉnh, quan hệ \(t_1, t_2, t_3\) được mã hóa bằng 3 màu của các cạnh.
Từ công thức (1), với \(n = 3\) màu, ta tính được: \[a_1 = 2 \implies a_2 = 2 \cdot 2 + 1 = 5 \implies a_3 = 3 \cdot a_2 + 1 = 3 \cdot 5 + 1 = 16\] Do đó số đỉnh cần thiết là \(a_3 + 1 = 16 + 1 = 17\) đỉnh. Theo Khẳng định 1a, đồ thị luôn chứa ít nhất một tam giác \(K_3\) cùng màu, tức là luôn tìm được bộ ba thỏa mãn yêu cầu đề bài.