Làm thế nào để đi qua cả 7 cây cầu mà không lặp lại 1 cái nào?

Hoa Hướng Dương |

Làm thế nào để đi qua cả 7 cây cầu mà không lặp lại 1 cái nào?
Làm thế nào để đi qua cả 7 cây cầu mà không lặp lại 1 cái nào?
Hình minh họa

Không chỉ dừng lại là 1 câu đố, đây là bài toán kinh điển mở ra rất nhiều ứng dụng trong cuộc sống như: Lý thuyết đồ thị và cả topo học.

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ầuKö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:

Làm thế nào để đi qua cả 7 cây cầu mà không lặp lại 1 cái nào? - Ảnh 1.

7 cây cầu (màu đỏ) ở thành phố Königsberg. Ảnh Internet.

Làm thế nào để đi qua cả 7 cây cầu mà không lặp lại 1 cái nào? - Ảnh 2.

Mô hình đơn giản của bài toán. Ảnh Internet.

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.

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?

Làm thế nào để đi qua cả 7 cây cầu mà không lặp lại 1 cái nào? - Ảnh 3.

Thiên tài người Thụy sĩ Leonhard Euler (1707 - 1783). Ảnh Internet.

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àm thế nào để đi qua cả 7 cây cầu mà không lặp lại 1 cái nào? - Ảnh 4.

Lời giải của Euler. Ảnh Internet.

Đầ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). Xem hình dưới.

Làm thế nào để đi qua cả 7 cây cầu mà không lặp lại 1 cái nào? - Ảnh 5.

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 minh họa.

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.

theo Trí Thức Trẻ

Đọc thêm về:

    Bạn đọc có thể báo tin, gửi bài viết, clip, ảnh về email khampha@ttvn.vn để nhận nhuận bút cao trong vòng 24h. Đường dây nóng: 0943 113 999

    Soha
    Trí Thức Trẻ

    TIN NỔI BẬT SOHA

      Công ty Cổ phần VCCorp

      © Copyright 2010 - 2019 – Công ty Cổ phần VCCorp

      Tầng 17,19,20,21 Toà nhà Center Building - Hapulico Complex,
      Số 1 Nguyễn Huy Tưởng, Thanh Xuân, Hà Nội.
      Email: btv@soha.vn
      Giấy phép số 2411/GP-TTĐT do Sở Thông tin và Truyền thông Hà Nội cấp ngày 31 tháng 07 năm 2015.
      Chịu trách nhiệm nội dung: Ông Nguyễn Thế Tân

      Liên hệ quảng cáo:
      Hotline: 0942.86.11.33
      Email: giaitrixahoi@admicro.vn
      Hỗ trợ & CSKH:
      Tầng 20, tòa nhà Center Building, Hapulico Complex,
      số 1 Nguyễn Huy Tưởng, phường Thanh Xuân Trung, quận Thanh Xuân, Hà Nội.
      Tel: (84 24) 7307 7979
      Fax: (84 24) 7307 7980