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?

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 Đây không chỉ là một câu đố mà bài toán kinh điển về 7 cây cầu này còn có rất nhiều ứng dụng trong cuộc sống.

Lý thuyết đồ thị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.

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.

Tư duy đúng tạo nên khoảng cách giữa người có mức lương năm là 1 tỷ đồng và 100 triệu đồng: 5 lối tư duy giúp bạn “đánh đâu thắng đó”
Cách tiêu tiền của tỷ phú Warren Buffett
Các nước đang dùng ứng dụng gì để chống lại Covid-19?

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).

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ị!

Đến tận hôm nay tôi mới hiểu, tại sao bạn mình làm sếp còn tôi thì cứ mãi ở vị trí nhân viên
Người tính toán để 14 lần trúng xổ số độc đắc
Tại sao Tần Thủy Hoàng là vị vua duy nhất mặc áo long bào đen?

Lời giải của Euler.

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.

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).

Hé lộ sự thật về nơi chôn cất Tư Mã Ý: Không thể che giấu dù tìm đủ mọi kế tung hỏa mù
Lí giải tại sao chữ "x" được dùng để ký hiệu ẩn số trong toán học
Phát hiện đột phá tại 'địa ngục' sâu 3.000 km của Trái Đất: Thứ quyết định sự tồn vong chính là đây!

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.

Làm Mới
Bài viết cùng chuyên mục