Bài toán bảy cây cầu ở Königsberg

Vào thế kỉ 18, người dân thành phố Königsberg suốt một thời gian dài loay hoay với một câu đố: sông Pregel chảy qua thành phố và tạo thành hai hòn đảo. Có tất cả 7 cây cầu bắc qua sông để lên các đảo. Liệu có thể trong một buổi dạo chơi ngày Chủ nhật đi qua tất cả các cây cầu, mỗi cây cầu đúng một lần không? Hãy xem các cây cầu được bắc qua sông như thế nào:

Liệu có thể bắt đầu cuộc dạo chơi ở một chỗ nào đó và đi qua mỗi cây cầu đúng một lần không? Ta thử xem: bắt đầu ở góc dưới bên trái, đi lên rồi lần lượt sang phải, như sau:

Ta thấy mình đã đi qua 6 trong 7 cây cầu, còn một cây cầu bị bỏ sót. Ta có thể thử một đường đi khác…

Lại chỉ đi qua được 6 trong 7 cây cầu của Königsberg. Có vẻ như không thể đi một lần mà qua mỗi cây cầu đúng một lần. Một ngày nọ, nhà toán học nổi tiếng Leonhard Euler biết đến bài toán này. Mà nói “nổi tiếng” vẫn còn ít – Euler là một huyền thoại thực sự của toán học, thậm chí số e còn được gọi là số Euler. Euler quyết định giải câu đố này. Ông bắt đầu bằng cách đặt tên cho từng hòn đảo hay từng phần của thành phố mà các cây cầu nối tới:

Sau đó Euler lập luận như sau: nếu một hòn đảo có số chẵn cây cầu nối tới thì ta có thể đi qua các cây cầu này trong một lần dạo chơi, bất kể ta bắt đầu từ đâu. Đơn giản là ta đến đảo bằng một cây cầu và rời đảo bằng một cây cầu khác – số cây cầu còn phải đi qua giảm đi 2. Muốn đến đảo bằng một cây cầu và rời đi bằng một cây cầu khác, ta cần 2 cây cầu. Nếu có 6 cây cầu nối tới một hòn đảo thì ta sẽ ghé đảo đó 3 lần. Chẳng hạn, giả sử có 4 cây cầu nối tới đảo B như sau:

Khi đó ta có thể đi qua tất cả các cây cầu trong một buổi dạo chơi Chủ nhật, bất kể bắt đầu từ đâu. Hãy thử xem! Trên hình, tôi đã vẽ một đường đi. Nhưng giả sử còn có thêm một cây cầu nối đảo B với đảo D:

Ta thấy đường đi đã chọn không cho phép đi qua mỗi cây cầu đúng một lần. Ta sẽ phải đi qua một cây cầu nào đó lần nữa để quay lại đảo B rồi mới sang được đảo D. Nhưng ta có thể chọn đường đi khác. Nếu bắt đầu cuộc dạo chơi ở đảo B, ta có thể đi qua mỗi cây cầu đúng một lần:

Ta bắt đầu ở đảo B, đi lên vùng A, rồi qua cầu trở lại B, sang vùng C, quay lại đảo B và cuối cùng sang đảo D. Như vậy, nếu bắt đầu ở hòn đảo có số lẻ cây cầu, ta có thể đi qua mỗi cây cầu của nó đúng một lần. Hoặc có thể đi theo chiều hoàn toàn ngược lại – bắt đầu ở đảo D và kết thúc ở đảo B.

Từ đó Euler nhận thấy rằng muốn đi qua mỗi cây cầu đúng một lần thì hoặc mọi hòn đảo đều có số chẵn cây cầu, hoặc có đúng hai hòn đảo có số lẻ cây cầu – ta bắt đầu ở một đảo có số lẻ cây cầu và kết thúc ở đảo kia. Mọi hòn đảo còn lại phải có số chẵn cây cầu. Nếu nhìn vào 7 cây cầu ban đầu ở Königsberg:

thì ta thấy mỗi hòn đảo đều có số lẻ cây cầu! Đảo A có 3, B có 5, C có 3 và D cũng có 3. Vì vậy câu đố không có lời giải – không thể đi qua cả 7 cây cầu, mỗi cây cầu đúng một lần, trong một buổi dạo chơi Chủ nhật. Nếu phá bỏ một cây cầu bất kì, câu đố bỗng nhiên sẽ có lời giải. Chẳng hạn, ta phá một trong các cây cầu nối đảo B và đảo C:

Ta thấy ngay đảo B có 4 cây cầu, còn đảo C có 2 cây cầu. Số cây cầu của đảo A và đảo D không đổi. Bây giờ có hai đảo với số chẵn cây cầu và hai đảo với số lẻ cây cầu. Nếu bắt đầu cuộc dạo chơi ở một trong hai đảo có số lẻ cây cầu, ta có thể đi qua mỗi cây cầu đúng một lần. Trên hình, ta bắt đầu ở đảo A và kết thúc ở đảo D.

Như vậy, Leonhard Euler đã giải thêm một bài toán nổi tiếng nữa và gần như đã đặt nền móng cho ngành mà ngày nay ta gọi là lí thuyết đồ thị. Để vinh danh ông, trong lí thuyết đồ thị, đồ thị có thể đi qua mọi cạnh, mỗi cạnh đúng một lần, được gọi là đồ thị Euler.