Giải thích đường đi và chu trình Euler

Có những hình vẽ được bằng một nét, không nhấc bút và không đi lại đường nào hai lần, lại có những hình chịu, dù bạn thử bao lâu. Mà cũng chẳng cần thử: hãy đếm số đường ở mỗi góc. Nếu nhiều nhất hai góc có số đường lẻ thì hình ấy vẽ được, và nét phải bắt đầu rồi kết thúc đúng ở những góc đó. Leonhard Euler tìm ra quy tắc này năm 1736, và bằng nó ông khai sinh lý thuyết đồ thị.

Bảy cây cầu Königsberg vẽ thành đồ thị: bốn vùng đất là các đỉnh, cả bốn đều có số cầu lẻ, nằm hai bên một dòng sông
Bảy cây cầu Königsberg vẽ thành đồ thị: bốn vùng đất là các đỉnh, cả bốn đều có số cầu lẻ, nằm hai bên một dòng sông

Bảy cây cầu Königsberg

Thành phố Phổ Königsberg, nay là Kaliningrad, nằm trên hai bờ sông Pregel và trên hai hòn đảo giữa sông là Kneiphof và Lomse. Bảy cây cầu nối bốn phần ấy: hai cầu từ Kneiphof sang mỗi bờ, một cầu giữa hai đảo, và một cầu từ Lomse sang mỗi bờ. Dân thành phố tự hỏi liệu có cuộc dạo chơi nào đi qua mỗi cầu đúng một lần không. Euler trả lời trong một bài trình bày trước viện hàn lâm ở Sankt-Peterburg năm 1735, in năm 1741: không thể. Bước then chốt của ông là gạt bỏ mọi thứ trừ các phần của thành phố và những cây cầu giữa chúng, và đó chính là việc mà đồ thị làm: mỗi vùng đất một đỉnh, mỗi cây cầu một cạnh, hai cạnh ở nơi hai cây cầu nối cùng hai chỗ.

Chân dung Leonhard Euler
Chân dung Leonhard Euler
Portrait of Leonhard Euler
Portrait of Leonhard Euler

Quy tắc bậc

Bậc của một đỉnh là số cạnh tại đỉnh đó. Một nét đi qua một đỉnh thì vào theo một cạnh và ra theo một cạnh khác, nên nó dùng các cạnh của đỉnh ấy theo từng cặp. Chỉ đỉnh đầu và đỉnh cuối của nét mới có thể giữ lại một cạnh không có đôi. Vì vậy đỉnh bậc lẻ bắt buộc phải là đầu hoặc cuối của nét. Kneiphof có năm cầu và ba phần còn lại mỗi phần ba cầu: bốn đỉnh bậc lẻ, dư hai. Nói chung, đồ thị liên thông có chu trình Euler, tức một nét kết thúc ngay chỗ nó bắt đầu, khi mọi bậc đều chẵn, và có đường đi Euler khi đúng hai bậc là lẻ, chạy từ đỉnh này sang đỉnh kia. Số đỉnh bậc lẻ không bao giờ bằng một, hay bất kỳ số lẻ nào khác: mỗi cạnh thêm 2 vào tổng các bậc, nên tổng ấy là số chẵn. Euler cũng nhận ra điều này, và ngày nay nó được gọi là bổ đề bắt tay.

Vì sao quy tắc ấy là đủ

Euler chứng minh hình có hơn hai đỉnh bậc lẻ thì không vẽ được, và khẳng định mà không chứng minh rằng mọi hình liên thông khác đều vẽ được. Chứng minh đến từ Carl Hierholzer, nhà toán học Đức mất sớm năm 1871; bài báo của ông ra năm 1873. Hãy bắt đầu ở một đỉnh bậc lẻ nếu có, nếu không thì ở đâu cũng được, rồi đi theo các cạnh chưa dùng chừng nào còn đi được. Vì mọi đỉnh khác đều bậc chẵn, bạn chỉ có thể tắc ở đỉnh cuối. Nếu còn cạnh, một số trong đó chạm vào chặng đường đã đi, bởi hình là liên thông. Từ một đỉnh như thế hãy đi tiếp đến khi tắc, lần này sẽ tắc ngay tại đỉnh đó, rồi chèn vòng ấy vào hành trình tại chỗ đó. Lặp lại cho đến khi không còn cạnh nào. Chứng minh ấy đồng thời là thuật toán nhanh nhất: mỗi cạnh chỉ được nhìn đến một số lần cố định.

Thuật toán Fleury: đừng đốt cầu của mình

Một nét có thể hỏng ngay cả trên hình vẽ được. Hãy lấy hai tam giác nối nhau bằng một cạnh duy nhất và bắt đầu ở một góc của tam giác thứ nhất: nếu bạn sang tam giác thứ hai trước khi vẽ xong tam giác thứ nhất, bạn sẽ không bao giờ quay lại được. Cạnh nối ấy là một cầu: bỏ nó đi thì hình tách làm đôi. Thuật toán Fleury năm 1883 cho một quy tắc: ở mỗi đỉnh hãy chọn một cạnh không phải là cầu đối với các cạnh còn lại, trừ khi không còn cạnh nào khác. Theo quy tắc ấy, bạn luôn vẽ xong. Việc kiểm tra cầu tốn thời gian nên thuật toán Fleury chậm hơn thuật toán Hierholzer, nhưng đó là thuật toán bạn có thể cầm bút đi theo, và gợi ý trong ứng dụng dùng nó.

Sửa một hình

Hình có k đỉnh bậc lẻ cần k/2 nét. Muốn vẽ bằng một nét, hãy thêm những cạnh ghép các đỉnh bậc lẻ thành từng cặp: mỗi cạnh mới biến hai đỉnh lẻ thành chẵn. Thêm k/2 − 1 cạnh thì còn hai đỉnh bậc lẻ và được một đường đi; thêm k/2 cạnh thì không còn đỉnh lẻ nào và được một chu trình. Ở Königsberg, chỉ cần thêm một cầu giữa hai trong bốn phần là cuộc dạo chơi thành hiện thực, thêm hai cầu thì còn đi được một vòng khép kín. Lịch sử đã làm điều tương tự: hai cây cầu mất trong Thế chiến thứ hai và hai cây bị thay bằng một con đường hiện đại, và năm cây cầu đứng ở các vị trí cũ ngày nay có thể đi qua mỗi cây một lần, từ đảo này sang đảo kia.

Đếm số cách

Ngôi nhà ông già Noel, một hình vuông với cả hai đường chéo và một mái nhà, là phiên bản dành cho trẻ em Đức của câu đố này: „Das ist das Haus vom Ni-ko-laus” có tám âm tiết, mỗi đường một âm. Hai góc dưới của nó là hai đỉnh bậc lẻ duy nhất, và từ mỗi góc có đúng 44 cách vẽ, tổng cộng 88. Với đồ thị có hướng, số chu trình Euler có hẳn một công thức là định lý BEST, đặt theo tên de Bruijn, van Aardenne-Ehrenfest, Smith và Tutte. Với đồ thị thường thì chưa biết công thức nào như vậy, và việc đếm nói chung được coi là khó, nên ứng dụng đếm các hình nhỏ bằng cách thử mọi cách và bỏ qua những bước sẽ chia hình làm đôi.

Đường đi Euler được dùng ở đâu

Xe dọn tuyết, xe quét đường hay người đưa thư đều muốn đi qua mỗi con phố một lần rồi trở về. Nếu mỗi ngã tư có số phố chẵn thì một chu trình Euler là đủ; nếu không, một số phố phải đi hai lần, và chọn những phố tốn kém ít nhất chính là bài toán người đưa thư Trung Hoa, do Quản Mai Cốc nêu ra năm 1962. Máy vẽ bút hay máy cắt laser cũng tiết kiệm thời gian bằng cách vẽ càng nhiều đường càng tốt mà không nhấc đầu vẽ. Trong giải trình tự bộ gen, hàng triệu đoạn ADN ngắn được ghép lại bằng cách tìm một đường đi Euler trong đồ thị de Bruijn, nơi mỗi đoạn là một cạnh. Và cũng chính quy tắc ấy cho biết những hình vẽ nét nào trong cuốn sách đố là đáng thử.

Hãy thử xem

Hãy mở Trình tìm đường đi Euler để tự đồ mười hai hình, từ Königsberg năm 1736 và ngày nay đến các ngôi sao, hình vuông lồng nhau và một khối lập phương, hoặc vẽ hình của riêng bạn với những cạnh song song. Các đỉnh bậc lẻ được tô đặc, mỗi đỉnh hiện bậc của nó, và quy tắc bậc dưới hình cho biết điều gì là khả thi cùng những cạnh nào sẽ sửa được hình. Khi bạn tắc, ứng dụng sẽ nói bạn đã bắt đầu sai đỉnh hay đã qua cầu quá sớm, và ở bước thứ mấy. Gợi ý đưa ra một cạnh an toàn, còn Giải sẽ vẽ hình bằng thuật toán Fleury kèm phép thử cầu, hoặc bằng thuật toán Hierholzer kèm từng lần chèn hành trình con.

Câu hỏi thường gặp

Đường đi Euler có phải là đường đi Hamilton không?

Không. Đường đi Euler dùng mỗi cạnh một lần và có thể qua một đỉnh nhiều lần; đường đi Hamilton qua mỗi đỉnh một lần và không nhất thiết dùng hết các cạnh. Một đồ thị có đường đi Euler hay không thì đếm số đỉnh bậc lẻ là biết ngay, nhưng với đường đi Hamilton thì chưa có phép thử nhanh nào, và tìm ra một đường như vậy là một trong những bài toán khó kinh điển của khoa học máy tính.

Quy tắc bậc có còn đúng khi hai đỉnh được nối bằng nhiều cạnh không?

Còn đúng. Mỗi cạnh đều tính vào bậc của cả hai đầu mút, bất kể có cạnh khác nối đúng hai đỉnh ấy hay không. Königsberg chính là đa đồ thị như vậy, với hai cây cầu từ Kneiphof sang mỗi bờ. Cạnh nối một đỉnh với chính nó, tức khuyên, cộng thêm 2 vào bậc của nó và không bao giờ làm bậc ấy đổi tính chẵn lẻ.

Còn đường một chiều thì sao?

Trong đồ thị có hướng, mỗi cạnh có một chiều, và quy tắc so sánh số cạnh đi vào mỗi đỉnh với số cạnh đi ra. Có chu trình Euler khi mọi đỉnh có số cạnh vào bằng số cạnh ra và các cạnh gắn liền thành một khối; có đường đi Euler khi một đỉnh có số cạnh ra nhiều hơn một, một đỉnh có số cạnh vào nhiều hơn một, còn mọi đỉnh khác đều cân bằng. Khi đó đường đi chạy từ đỉnh thứ nhất sang đỉnh thứ hai.

Có thể có hình với đúng một đỉnh bậc lẻ không?

Không. Tổng bậc của mọi đỉnh bằng hai lần số cạnh, vì mỗi cạnh có hai đầu mút. Tổng ấy là số chẵn, nên số bậc lẻ trong đó cũng phải chẵn: 0, 2, 4 và cứ thế, không bao giờ là 1 hay 3.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Mở Trình tìm đường đi Euler