Bài toán bảy cây cầu Königsberg hỏi: có cách nào đi dạo qua cả bảy cây cầu của thành phố, mỗi cầu đúng một lần, không? Năm 1735, Leonhard Euler chứng minh là không thể, vì cả bốn vùng đất nối bởi các cây cầu đều có số cầu lẻ. Lời giải ấy ngắn gọn, nhưng nó mở ra một ngành toán học mới — lý thuyết đồ thị — ngành đứng sau bản đồ dẫn đường, mạng điện và mạng xã hội hôm nay.
Thành phố trên sông Pregel
Königsberg là một thành phố cảng của nước Phổ, nằm hai bên sông Pregel. Giữa sông có hai hòn đảo; đảo lớn tên Kneiphof. Bảy cây cầu nối hai bờ với các đảo và nối hai đảo với nhau. Đây cũng là thành phố quê hương của triết gia Immanuel Kant.
Dân thành phố có một thắc mắc truyền miệng trong những buổi đi dạo Chủ nhật: liệu có thể đi một vòng, qua mỗi cầu đúng một lần? Không ai tìm ra cách, nhưng cũng không ai chứng minh được là không có cách. Ngày nay thành phố mang tên Kaliningrad, thuộc Nga, và hệ thống cầu đã thay đổi nhiều so với thế kỷ 18.
Bố cục bảy cây cầu
Hãy gọi bốn vùng đất là:
- A: đảo Kneiphof ở giữa.
- B: bờ bắc.
- C: bờ nam.
- D: đảo thứ hai ở phía đông.
| Vùng đất | Số cầu nối vào | Chẵn hay lẻ |
|---|---|---|
| A – đảo Kneiphof | 5 | Lẻ |
| B – bờ bắc | 3 | Lẻ |
| C – bờ nam | 3 | Lẻ |
| D – đảo phía đông | 3 | Lẻ |
Hai cây cầu nối A với B, hai cây nối A với C, một cây nối A với D, một cây nối B với D, một cây nối C với D. Cộng lại: 5 + 3 + 3 + 3 = 14, đúng bằng 2 × 7 cầu, vì mỗi cầu có hai đầu.
Euler đã nghĩ thế nào
Leonhard Euler, nhà toán học người Thuỵ Sĩ làm việc ở Viện Hàn lâm Khoa học Saint Petersburg, nghe về bài toán qua thư từ. Ông trình bày lời giải trước Viện năm 1735; bài viết bằng tiếng Latin được in năm 1741, với tiêu đề có thể dịch là "Lời giải một bài toán liên quan đến hình học vị trí".
Ý tưởng thiên tài của Euler là bỏ hết những gì không quan trọng. Hình dáng hòn đảo, chiều dài cây cầu, khoảng cách giữa các bờ — tất cả không ảnh hưởng đến câu trả lời. Chỉ có hai thứ quan trọng: có bao nhiêu vùng đất, và vùng nào nối với vùng nào bằng bao nhiêu cây cầu.
Rồi ông lý luận: khi bạn đi vào một vùng đất bằng một cây cầu và rời đi bằng một cây cầu khác, bạn dùng hết hai cây cầu của vùng đó. Vậy một vùng mà bạn chỉ đi ngang qua (không phải điểm xuất phát, không phải điểm kết thúc) phải có số cầu chẵn. Chỉ điểm xuất phát và điểm kết thúc được phép có số cầu lẻ — tức là tối đa hai vùng lẻ.
Königsberg có bốn vùng lẻ. Kết luận: không thể.
Euler có vẽ "đồ thị" không?
Một điều thú vị: trong bài viết gốc, Euler không vẽ hình chấm và đường như sách giáo khoa ngày nay. Ông dùng chữ cái để đặt tên các vùng và lập luận bằng cách đếm chữ trong chuỗi đường đi. Hình vẽ bốn chấm nối bằng bảy đường — thứ mà ai học toán rời rạc cũng thấy — là cách trình bày của những người đi sau, vào thế kỷ 19 và 20. Từ "đồ thị" (graph) theo nghĩa này cũng chỉ xuất hiện năm 1878, do nhà toán học James Joseph Sylvester dùng.
Vì sao bài toán nhỏ lại quan trọng
Bài toán bảy cây cầu không khó; trẻ con thử vài lần cũng đoán được là không làm được. Cái quan trọng là cách Euler chứng minh. Đó là lần đầu tiên người ta giải một bài toán chỉ dựa trên quan hệ nối giữa các vật, không cần đo đạc gì cả. Euler gọi đó là "hình học vị trí". Ngày nay ta gọi là lý thuyết đồ thị, và họ hàng gần của nó là tô-pô học.
Cùng một kiểu suy nghĩ ấy, người ta trả lời được:
- Xe rác có thể đi qua mọi con phố đúng một lần không?
- Thanh tra có thể kiểm mọi đoạn đường ống mà không phải đi lại không?
- Một hình vẽ có thể vẽ bằng một nét không nhấc bút không?
Thêm một cây cầu thì sao
Thử tưởng tượng thành phố xây thêm một cây cầu thứ tám nối bờ bắc B với bờ nam C. Lúc đó B có 4 cầu, C có 4 cầu (chẵn), còn A và D vẫn lẻ. Chỉ còn hai vùng lẻ → có đường đi! Bắt đầu ở đảo A, kết thúc ở đảo D (hoặc ngược lại).
Thêm hai cầu nữa sao cho mọi vùng đều chẵn thì còn tốt hơn: có thể đi một vòng và quay về đúng chỗ xuất phát. Bài tập vui: thêm ít cầu nhất ở đâu để Königsberg có một vòng dạo khép kín? (Đáp án: hai cây cầu — ví dụ nối A với B và C với D.)
Góc nhìn hôm nay: thử với thành phố của bạn
Hội An, Huế, Cần Thơ, thành phố nào có sông và cầu cũng có thể làm "bài toán Königsberg" riêng. Lấy bản đồ, chọn một vùng nhỏ có vài cây cầu, đặt tên các vùng đất, đếm cầu nối vào mỗi vùng. Có tối đa hai vùng lẻ là có đường dạo qua mỗi cầu một lần. Đây là một bài tập hay cho học sinh: vừa đọc bản đồ, vừa làm toán, vừa có lý do để đi bộ cuối tuần.
Sách nên đọc: các sách phổ thông về lịch sử toán học thường dành một chương cho Euler; cuốn Euler's Gem của David Richeson kể kỹ về Euler và các ý tưởng hình học vị trí.
Câu hỏi thường gặp
Bài toán bảy cây cầu Königsberg là gì?
Là câu hỏi có thể đi dạo qua cả bảy cây cầu của thành phố Königsberg, mỗi cầu đúng một lần, hay không. Euler chứng minh năm 1735 rằng không thể.
Vì sao không đi được qua bảy cây cầu?
Vì cả bốn vùng đất đều có số cầu lẻ. Một đường đi qua mỗi cầu một lần chỉ cho phép tối đa hai vùng lẻ, là điểm xuất phát và điểm kết thúc.
Königsberg bây giờ ở đâu?
Königsberg nay là thành phố Kaliningrad thuộc Nga, nằm bên bờ biển Baltic. Hệ thống cầu ngày nay đã khác nhiều so với thời Euler.
Euler giải bài toán bảy cây cầu năm nào?
Euler trình bày lời giải trước Viện Hàn lâm Saint Petersburg năm 1735, và bài viết được in năm 1741.
Bài toán bảy cây cầu liên quan gì đến lý thuyết đồ thị?
Lời giải của Euler là lần đầu bài toán được giải chỉ dựa trên quan hệ nối giữa các vùng, không cần đo đạc. Đó được coi là khởi đầu của lý thuyết đồ thị.