Hình "Google doodle" trên đầu trang mạng Google ngày 15 tháng 4, 2013, kỷ niệm 306 năm ngày sinh Euler. Bài toán 7 cây cầu nằm phía dưới chữ O. (Hình: Google.com)
Kỳ trước tôi khắng định, nhờ có Euler mới có gene sequencing nhanh, và nhờ có gene sequencing nhanh mới có được vaccine Covid trong dưới một năm.
Đóng góp của Leonhard Euler (1707-1783) là giải bài toán mà ngày nay mang tên Eulerian circuit hay Eulerian path, tiếng Việt gọi là chu trình hay đường đi Euler. Qua đó, ông sáng lập ra một ngành toán học mới gọi là graph theory - lý thuyết đồ thị - với áp dụng trong thương mại, công nghệ, điện toán, và cả việc làm gene sequencing cho virus.
Bài toán Eulerian path khá quen thuộc với nhiều người dù có thể không biết nó có tên như vậy. Hồi nhỏ tôi với mấy đứa bạn hay chơi trò đưa ra một hình gì đó rồi đó vẽ được hình đó mà không nhấc cây viết ra khỏi tờ giấy và không đồ một cạnh hai lần. Các bạn có chơi trò nay bao giờ chưa?
Thí dụ hình dưới đây nhìn cầu kỳ nhưng làm được.
(Hình: Vũ Quí Hạo Nhiên)
Trong khi đó, hình dưới đây nhìn đơn giản nhưng không làm được.
(Hình: Vũ Quí Hạo Nhiên)
Nếu vẽ được một đường đi hết tất cả các cạnh mà không cần nhấc viết và không đồ một cạnh hai lần, đường đó gọi là đường đi Euler. Nếu đường đi Euler về lại kết thúc tại điểm xuất phát, gọi là chu trình Euler.
Khái niệm này do Euler phát minh ra để giải bài toán mang tên "7 cây cầu Königsberg." Königsberg là một thành phổ của Phổ cũ, có con sông Preger chảy qua, và giữa sông có 2 cù lao lớn. Có 7 cây cầu bắc qua bắc lại nối 2 bờ sông và 2 cù lao. Người dân ở đây đố nhau làm sao đi bộ quanh thành phố, băng qua đủ 7 cây cầu, mà không băng qua cây cầu nào 2 lần.
Bản đồ thành phố Königsberg thời xưa với dòng sông Preger và 7 cây cầu. (Hình: Bogdan Giuşcă/Wikimedia/PD)
Hãy thử vài cách đi bộ qua đủ 7 cây cầu xem có cách nào không băng cầu nào 2 lần:
(Hình: Vũ Quí Hạo Nhiên)
Chẳng bao lâu, người ta thấy bài toán này rất khó, nhưng người ta không biết là đáp số khó tìm ra, hay là bài toán không có đáp số.
Euler xuất hiện. Trước tiên hết, ông nhận ra rằng nếu mình sẽ sơ đồ bài toán, mình chỉ cần 7 cây cầu thôi, còn nguyên 2 cái cù lao, nguyên mảng đất phía bắc sông và mảng phía nam sông, đều có thể thu gọn lại thành một điểm.
(Hình: Wikimedia/Bogdan Giuşcă, Varmin, Booyabazooka/PD, CC-BY-SA-3.0)
Ngày nay, qua nhiều thế kỷ vẽ sơ đồ, mình thấy điều này là đương nhiên. Thí dụ như bản đồ đường xe điện ngầm, hầu hết đều rút gọn, không câu nệ khoảng cách, không cần thiết phải vẽ hành trình đường ray giống hệt như thực tế. Thí dụ như tuyến đi từ trạm A tới trạm B có thể đưỏng hầm chạy vòng vèo nhưng trên bản đồ có thể vẽ một đường thẳng cũng được. Đó là điều mới mẻ đối với thời đó.
Sơ đồ này, ngày nay gọi là graph hay đồ thị. Mọi thứ rườm rà bỏ đi hết, chỉ để lại những điểm đỉnh và cạnh nối chúng với nhau.
Đơn giản hoá bản đồ thành đồ thị, Euler chứng minh được là không có cách nào vẽ đồ thị này mà không nhấc viết lên cũng như không đồ một cạnh hai lần. Vì sao?
Vì nếu vẽ được như vậy, mỗi lần đi vào một đỉnh bằng một cạnh, sẽ phải đi ra bằng cạnh khác. Cho nên số cạnh tại mỗi đỉnh phải là số chắn. Cùng lắm thì có một đỉnh xuất phát chỉ có đi ra chứ không đi vô, và một đỉnh kết thúc chỉ có đi vô chứ không đi ra, là 2 đỉnh có cạnh lẻ. Còn thì phải chẵn hết.
Để có đường qua tất cả các cạnh, khi đi vô một đỉnh bằng một cạnh, sẽ phải đi ra bằng một cạnh khác, nên số cạnh phải là số chẵn. (Hình: Vũ Quí Hạo Nhiên)
Nhìn lại hình đầu ở trên, có đúng 2 đỉnh lẻ là điểm đầu và điểm chót, còn các điểm đỉnh khác đều chẵn. Do đó có đường đi Euler. Còn hình thứ nhì, có 4 điểm lẻ, nên không thể có đường đi Euler.
(Hình: Vũ Quí Hạo Nhiên)
Sơ đồ của 7 cây cầu Königsberg có 4 đỉnh lẻ. Do đó, không thể có cách nào đi qua hết 7 cạnh mà không nhấc viết hoặc đồ một cạnh hai lần.
Từ bài toán này sản sinh ra ngành lý thuyết đồ thị với ứng dụng khắp mọi nơi. Bất cứ cái gì có kết nối với cái gì khác, cũng đều có thể biến thành một sơ đồ và phân tích bằng phương pháp của lý thuyết đồ thị. Ngữ pháp (văn phạm) các thứ tiếng chẳng hạn, có thể vẽ thành sơ đồ, và khi dạy được cho máy điện toán biết cách chuyển sơ đồ của tiếng Anh ra sơ đồ của tiếng Việt, thì cũng có thể dạy cho máy điện toán dịch một đoạn văn tiếng Anh ra tiếng Việt.
Trong sinh vật học, khi người ta muốn làm gene sequencing, tức là viết ra thứ tự các nucleotides trong DNA hoặc RNA, người ta chỉ chụp được từng khúc ngắn của chuỗi nucleotides. Để ghép nhiều (ngàn) khúc ngắn này lại, người ta phải dùng để đường đi Euler. Đó là đóng góp của Euler cho vaccine ngừa Covid, sẽ giải thích trong kỳ tới.
Bài toán 7 cây cầu Königsberg trên tem Hàn Quốc.
(Xem tiếp kỳ 3)