Bài toán đi 1 lần qua 7 chiếc cầu của cư dân Königsberg tại Nga

Königsberg là một thành phố cổ thuộc Vương quốc Phổ và nước Đức cho đến 1945. Sau Đại chiến Thế giới II, nó thuộc Liên Xô (cũ) rồi Nga, và được gọi là Kaliningrad. Chỉ có rất ít dấu tích của Königsberg còn sót lại ngày nay ở Kaliningrad.

Ở thành phố Königsberg, có 7 chiếc 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:

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

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. Tuy nhiên, giai thoại kể rằng, nhiều năm sau đó, vào các ngày chủ nhật, những người dân giàu có và học thức của thành phố đã đi dạo quanh để tìm cách giải bài này.

Euler đã giải bài toán đi 1 lần qua 7 chiếc cầu cho cư dân Königsberg tại Nga như thế nào?

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 cũng là người đã 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. Cụ thể, ông phân tích như sau:

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

Đầu tiên, Euler tìm cách "mô hình hóa" bài toán 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). 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.

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.