BÀI TOÁN BẢY CÂY CẦU

 Bài toán bảy cây cầu Euler, còn gọi là Bảy cây cầu ở Königsberg là bài toán nảy sinh từ thành phố Königsberg nằm trên sông Pregel, bao gồm hai hòn đảo lớn nối với nhau. Bài toán đặt ra là tìm một tuyến đường mà đi qua mỗi cây cầu một lần và chỉ đúng một lần rồi quay về nơi xuất phát.

Bản đồ Königsberg thời Euler, mô tả vị trí thực của bay cây cầu và sông Pregel

(Nguồn: Bài toán bảy cây cầu Euler - Wikiwand)

Năm 1736, Leonhard Euler đã chứng minh rằng bài toán này là không có lời giải. Kết quả này là cơ sở phát triển của lý thuyết đồ thị.

Leonhard Euler (15/4/1707 – 18/9/1783)

(Nguồn: Leonhard Euler - Wikiwand)

Sau đây là lời giải cho bài toán trên của Euler. Để chứng minh kết quả, Euler đã phát biểu bài toán bằng các thuật ngữ của lý thuyết đồ thị. Ông loại bỏ tất cả các chi tiết ngoại trừ các vùng đất và các cây cầu, sau đó thay thế mỗi vùng đất bằng một điểm, gọi là đỉnh, và thay mỗi cây cầu bằng một đoạn nối, gọi là cạnh. Cấu trúc toán học thu được được gọi là một đồ thị.

Đồ thị minh họa cho bài toán

Bài toán tương đương có một chu trình nào đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần không. Euler đã chứng minh được để tồn tại chu trình như thế trong đồ thị liên thông thì tất cả các đỉnh đều có bậc chẵn. Với đồ thị này, các đỉnh đều có bậc lẻ nên không tồn tại chu trình đó. Vậy câu trả lời cho bài toán bảy cây cầu là không thể có đường đi đi qua tất cả các cây cầu, mỗi cây đúng một lần rồi quay về nơi xuất phát.

Nhiều tài liệu cũng ghi lại bài toán này dưới dạng đường đi qua tất cả các cây cầu, mỗi cây một lần nhưng không cần về lại nơi xuất phát. Euler chứng minh được để tồn tại đường đi như thế thì điều kiện cần và đủ là trong đồ thị phải có đúng hai đỉnh bậc lẻ, đồ thị này lại không thỏa mãn giả thiết đó nên cũng không thể có đường đi như vậy.

Đường đi và chu trình nói trên sau này được đặt theo tên của Euler và trở thành một trong nhưng vấn đề trung tâm của Lý thuyết đồ thị. Lời giải của Euler cho bài toán bảy cây cầu ở Königsberg được coi là định lý đầu tiên của lý thuyết đồ thị, ngành nghiên cứu mà nay được coi là một nhánh của toán học tổ hợp, tuy các bài toán tổ hợp đã được quan tâm đến từ sớm hơn rất nhiều.

Ngoài ra, theo Euler thông tin quan trọng là số cây cầu và danh sách các vùng đất ở đầu cầu (chứ không phải vị trí chính xác của chúng) đã là dấu hiệu cho sự phát triển của ngành tôpô học. Sự khác biệt giữa sơ đồ thực và sơ đồ đồ thị là một ví dụ tốt cho thấy rằng tôpô học không quan tâm đến hình thù cứng nhắc của các đối tượng.