Bảy cây cầu ở Königsberg và trò vẽ hình một nét
Câu đố của thành phố Königsberg
Phần tiêu đề “Câu đố của thành phố Königsberg”Thế kỷ 18, thành phố Königsberg (nay là Kaliningrad, nước Nga) có một con sông chảy qua, chia thành phố thành 4 vùng đất: bờ Bắc, bờ Nam, một hòn đảo và vùng phía Đông. Bảy cây cầu nối các vùng với nhau.
Người dân hay đố nhau: có cách nào đi dạo qua cả 7 cây cầu, mỗi cầu đúng một lần không? Không ai tìm ra cách, nhưng cũng không ai chắc là không có.
Euler trả lời bằng cách đếm
Phần tiêu đề “Euler trả lời bằng cách đếm”Năm 1736, nhà toán học Thụy Sĩ Leonhard Euler giải quyết câu đố mà không cần đi thử.
Bước 1. Euler nhận ra hình dạng các vùng, độ dài các cầu đều không quan trọng. Chỉ cần biết vùng nào nối với vùng nào, bằng mấy cây cầu.
Bước 2. Xét một vùng mà ta chỉ đi ngang qua (không phải nơi bắt đầu, không phải nơi kết thúc). Mỗi lần đi vào bằng một cầu thì phải đi ra bằng một cầu khác. Cầu được dùng theo từng cặp vào - ra, nên vùng đó phải có số cầu chẵn.
Bước 3. Chỉ nơi bắt đầu và nơi kết thúc mới được có số cầu lẻ. Vậy muốn đi được thì có nhiều nhất 2 vùng có số cầu lẻ.
Bước 4. Königsberg có đảo 5 cầu, ba vùng còn lại mỗi vùng 3 cầu. Cả 4 vùng đều lẻ, nhiều hơn 2.
Bước 5. Vậy không thể đi qua 7 cây cầu, mỗi cầu đúng một lần.
Trò vẽ hình một nét
Phần tiêu đề “Trò vẽ hình một nét”Chắc các bạn đã chơi trò vẽ một hình mà không nhấc bút, không tô lại nét nào. Quy tắc của Euler cho biết ngay hình nào vẽ được:
Bước 1. Ở mỗi điểm giao, đếm xem có bao nhiêu nét đi ra.
Bước 2. Đếm số điểm có số nét lẻ:
| Số điểm lẻ | Kết luận |
|---|---|
| 0 | Vẽ được. Bắt đầu ở đâu cũng được, và kết thúc đúng chỗ bắt đầu. |
| 2 | Vẽ được, nhưng phải bắt đầu ở một điểm lẻ, kết thúc ở điểm lẻ kia. |
| Nhiều hơn 2 | Không vẽ được. |
Hình ngôi nhà ở trên có đúng 2 điểm lẻ ở hai góc dưới (mỗi điểm 3 nét). Các bạn thử bắt đầu từ một góc dưới, sẽ vẽ được cả ngôi nhà bằng một nét. Bắt đầu ở mái nhà thì sẽ bị kẹt!
Khởi đầu của lý thuyết đồ thị
Phần tiêu đề “Khởi đầu của lý thuyết đồ thị”Cách Euler vẽ mỗi vùng thành một chấm, mỗi cây cầu thành một đường nối chính là khởi đầu của lý thuyết đồ thị. Ngày nay, đồ thị có mặt ở khắp nơi:
- Ứng dụng bản đồ tìm đường đi ngắn nhất: mỗi ngã tư là một chấm, mỗi con đường là một đường nối.
- Mạng xã hội: mỗi người là một chấm, hai người là bạn bè thì có đường nối.
- Xe quét đường, xe thu gom rác cần đi qua mọi con phố mà ít phải đi lại nhất, chính là bài toán Königsberg trong đời thực.
Muốn học cách máy tính giải các bài toán đồ thị, các bạn xem mục Lập trình thi đấu.