Bài toán 7 cây cầu của Euler: Bạn hãy thử đi qua mà không lặp lại lần nào?
Lý thuyết đồ thị và topo học là các ngành toán học vô cùng quan trọng, có ứng dụng thực tiễn cao. Tuy nhiên những ngành toán học này lại ra đời khá muộn và xuất phát từ một câu chuyện thực tế vô cùng thú vị.
Câu chuyện 7 cây cầu ở Königsberg
Königsberg là một thành phố nay thuộc nước Nga, ở nơi này có 7 cây cầu. Mỗi cây cầu sẽ nối liền 2 bờ sông, hoặc là một bờ sông với một trong hai cù lao, hoặc nối 2 cù lao với nhau như hình bên dưới:
7 cây cầu (màu đỏ) ở thành phố Königsberg.
Người dân ở Königsberg đã đặt ra một câu đố mà chưa từng có AI giải được: "Liệu có thể đi một lần qua tất cả 7 chiếc cầu mà không phải lặp lại hay không (hay mỗi cây cầu chỉ được đi qua một lần duy nhất)?".
Bài toán 7 cây cầu thú vị khiến nhiều người tới nơi đây và... đi dạo thử để thử sức! Thế nhưng kết quả là họ đều thất bại trong việc tìm một phương án thỏa mãn yêu cầu đưa ra.
Chỉ tới năm 1735, một nhà toán học lỗi lạc tình cờ nghe được câu chuyện này khi tới nơi đây. Người đó chính là thiên tài người Thụy Sĩ Leonhard Euler (1707 - 1783), ông cùng với Newton và Archimedes được xem là 3 nhà toán học vĩ đại nhất thế giới.
Chính ông đã chứng minh được bài toán này không có lời giải hay không thể thực hiện được và việc làm của nhiều người là vô ích khi đâm đầu tìm kiếm một phương án khả thi.
Euler đã giải bài toán này như thế nào?
Thiên tài người Thụy sĩ Leonhard Euler (1707 - 1783).
Thoạt nhìn đây có vẻ là một câu đố bình thường, thế nhưng nó lại ẩn chứa mối liên hệ sâu sắc giữa lý thuyết đồ thị và topo học sau này, chính việc giải bài toán đã giúp Euler mở ra một nhánh mới trong toán học: Lý thuyết đồ thị!
Lời giải của Euler.
Đầu tiên, Euler tìm cách "mô hình hóa" bài toán 7 cây cầu một cách trừu tượng nhất thông qua việc biểu diễn các cù lao hay bờ sông bằng các chấm tròn, còn các cây cầu là đoạn thẳng (có thể là cung). Xem hình dưới.
Cù lao là các điểm A và B, bờ sông là các điểm C và D. Các cây cầu trở thành các đoạn thẳng hay cung nối với các điểm trên.
Như vậy, Euler đã có một mô hình đơn giản nhất của bài toán 7 cây cầu, cách biểu diễn bằng các điểm và đoạn thẳng (hay cung) chính là bước đầu của sự ra đời lý thuyết đồ thị ngày nay.
Trong toán học hay tin học lý thuyết đồ thị giúp chúng ta nghiên cứu và khảo sát các tính chất của đồ thị, trong đó đồ thị là tập hợp các đối tượng được gọi là đỉnh (nút) được nối với nhau qua các cạnh (cung).
Euler đã giải bài toán bằng cách sử dụng bậc của các nút (bậc chính là số cạnh nối với nó). Cụ thể hơn, ở bài toán 7 cây cầu có 3 nút có bậc bằng 3 và một nút có bậc là 5.
Tuy nhiên, Euler lại chứng minh bài toán chỉ có thể giải được khi không có nút bậc lẻ, mà đồ thị bài toán trên lại có tới 4 nút bậc lẻ hay nói cách khác bài toán vô nghiệm.
- Thần số học và ý nghĩa bí ẩn của 12 con số (Thứ tư, 13:40:04 15/07/2020)
- Thiên tài 17 tuổi tìm ra định lý có thể thay đổi Toán học (Thứ Ba, 09:16:03 14/08/2018)
- Chân dung 10 nhà toán học vĩ đại nhất trong lịch sử (Thứ sáu, 13:00:05 03/08/2018)
- Video: Lịch sử phát hiện và ứng dụng của số pi trong toán... (Thứ sáu, 11:59:02 03/08/2018)
- Bài toán về cọc tiền của nhà toán học Italy (Thứ bảy, 21:47:04 02/06/2018)
- Ai cũng giật mình khi biết cách loài chim này cất cái lưỡi dài... (Thứ sáu, 08:59:03 18/05/2018)
- Chứng minh loài người không đơn độc trong vũ trụ bằng toán... (Thứ Ba, 16:10:04 06/03/2018)
- Chỉ 3% giải được bài toán đang gây tranh cãi trên Quora này! (Thứ năm, 09:00:08 08/06/2017)
- "Bí mật" về khối kilogram chuẩn của Mỹ được bảo... (Thứ tư, 09:00:02 31/05/2017)
- Biểu hiện của tỷ lệ vàng trong tự nhiên từ thiên hà cho... (Thứ sáu, 10:00:08 26/05/2017)
- Điều gì sẽ xảy ra nếu bạn ngưng gội đầu trong vòng một năm?
- 7 thảm họa thiên nhiên có thể sắp xảy ra
- Sự thật về chế độ máy bay và 20 bí mật về điện thoại của bạn
- 7 bí ẩn trên Trái đất đã khiến khoa học đau đầu cả nghìn năm qua mà vẫn chưa có lời giải
- Các nhà thiên văn học bó tay trước sự tồn tại của hành tinh này
-
Cơ hội hiếm hoi quan sát hành tinh màu xanh da trời vài ngày tới
Thứ tư, 20:00:06 20/01/2021
-
EU cho hay: "Sâu bột an toàn, người có thể ăn được"
Thứ Ba, 23:30:01 19/10/2021
-
Hệ sao kỳ quái chưa từng thấy cách Trái đất 1.800 năm ánh sáng
Thứ Ba, 22:50:01 19/01/2021
-
Loài người có thể đơn độc trong vũ trụ
Thứ Ba, 22:35:09 19/01/2021
-
Chuyện về con nhện đi săn nhện: Thạo binh pháp như "Gia Cát Lượng", đầy mưu hèn kế bẩn để săn mồi bằng mọi giá
Thứ Ba, 21:27:02 19/01/2021
-
Bức thư tiết lộ những năm cuối đời đầy đau đớn của Napoléon
Thứ năm, 21:35:06 14/01/2021
-
Tàu chở hàng SpaceX lần đầu tự động tách khỏi trạm ISS
Thứ năm, 21:16:09 14/01/2021
-
Phát hiện chuẩn tinh cách Trái đất hơn 13 tỷ năm ánh sáng
Thứ năm, 20:45:00 14/01/2021