Một nét
Đỉnh bậc lẻ
Cạnh đã vẽ
Số cách vẽ

    • 0 đỉnh bậc lẻ: một chu trình, từ đỉnh bất kỳ trở về chính nó
    • 2 đỉnh bậc lẻ: một đường đi từ đỉnh này sang đỉnh kia
    • 4 trở lên: không thể vẽ bằng một nét

    Phương pháp

    Tìm hiểu thêm về đường đi và chu trình Euler

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

    Bạn có vẽ được ngôi nhà ông già Noel mà không nhấc bút và không đi lại đường nào hai lần không? Có, nhưng chỉ khi bắt đầu từ một trong hai góc dưới, và từ mỗi góc có 44 cách. Lý do nằm ở bậc của một đỉnh, tức số đường gặp nhau tại đó: mỗi lần cây bút đi qua một đỉnh, nó dùng hết hai đường của đỉnh ấy. Leonhard Euler tìm ra quy tắc này năm 1736 với bảy cây cầu Königsberg. Hãy tự đồ một hình, xem bạn tắc ở đâu và vì sao, xin một gợi ý, hoặc xem thuật toán vẽ nó. Chọn một hình rồi đồ lại: chạm vào một đỉnh để bắt đầu, sau đó chạm lần lượt các cạnh hoặc các đỉnh kế tiếp, hoặc kéo từ đỉnh này sang đỉnh khác. Mỗi cạnh chỉ được đi một lần. Lùi bỏ một bước, Gợi ý chỉ ra cạnh an toàn tiếp theo, còn Giải chạy từng bước thuật toán Fleury hoặc Hierholzer. Các đỉnh bậc lẻ được tô đặc, và huy hiệu ở mỗi đỉnh là bậc của nó. Ở chế độ Vẽ, chạm vào chỗ trống để thêm một đỉnh, chạm hai đỉnh để nối chúng, chạm thêm lần nữa để có cạnh thứ hai; kéo một đỉnh để dời nó. Xóa bỏ đỉnh và cạnh. Khi có hơn hai đỉnh bậc lẻ, Thêm sẽ đặt vào những cạnh giúp hình vẽ được bằng một nét.

    Cách nó hoạt động

    1. Hãy chọn một hình, chẳng hạn bảy cây cầu Königsberg, ngôi nhà ông già Noel hay một ngôi sao, hoặc tự vẽ hình của bạn ở chế độ Vẽ, với bao nhiêu cạnh giữa hai đỉnh tùy ý.
    2. Chạm vào một đỉnh để bắt đầu, rồi chạm lần lượt các cạnh hoặc các đỉnh, hoặc kéo từ đỉnh này sang đỉnh khác. Nếu tắc, dòng trạng thái sẽ nói vì sao; Lùi bỏ một bước và Gợi ý chỉ ra một cạnh an toàn.
    3. Hãy đọc quy tắc bậc dưới hình, thêm vào hình không vẽ được những cạnh mà ứng dụng đề nghị, hoặc nhấn Giải để xem thuật toán Fleury hay Hierholzer vẽ nó theo từng bước.

    Vì sao các đỉnh bậc lẻ quyết định

    Một nét đi qua một đỉnh thì vào theo một đường và ra theo một đường khác, nên nó dùng các đường tại đỉnh ấy theo từng cặp. Chỉ ở nơi nét bắt đầu hoặc kết thúc mới có thể còn một đường lẻ không có đôi. Vì vậy, đỉnh có số đường lẻ bắt buộc phải là điểm đầu hoặc điểm cuối. Không có đỉnh bậc lẻ thì nét kết thúc ngay chỗ nó bắt đầu: đó là chu trình Euler. Có hai đỉnh thì nét đi từ đỉnh này sang đỉnh kia: đó là đường đi Euler. Có bốn trở lên thì số đầu mút quá nhiều cho một nét, và k đỉnh bậc lẻ cần k/2 nét. Königsberg có bốn vùng đất với năm, ba, ba và ba cây cầu: cả bốn đều lẻ, nên không cuộc dạo chơi nào qua được mỗi cầu một lần. Chỉ cần thêm một cây cầu giữa hai vùng trong số đó là cuộc dạo chơi thành hiện thực.

    Thuật toán Fleury và Hierholzer

    Biết một hình vẽ được không giống với vẽ được nó: một nét bất cẩn có thể tự cắt mình khỏi những đường còn cần đến. Thuật toán Fleury năm 1883 tránh điều đó bằng một quy tắc: đừng bao giờ qua cầu, tức một đường mà nếu bỏ đi sẽ chia các đường còn lại thành hai mảnh, trừ khi không còn đường nào khác. Thuật toán Hierholzer, trong một bài báo công bố năm 1873, nhanh hơn: cứ đi bất kỳ đâu cho đến khi tắc, điều chỉ có thể xảy ra ở điểm xuất phát, rồi từ một đỉnh trên hành trình vẫn còn đường trống, đi thêm một vòng khép kín nữa và chèn nó vào hành trình. Thời gian tăng tỉ lệ với số cạnh, và máy tính tìm đường đi Euler theo cách đó.

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

    Đường đi Euler và chu trình Euler khác nhau thế nào?

    Cả hai đều dùng mỗi cạnh của đồ thị đúng một lần. Chu trình Euler kết thúc ngay chỗ nó bắt đầu; đường đi Euler kết thúc ở chỗ khác. Đồ thị liên thông có chu trình khi mọi đỉnh đều bậc chẵn, và có đường đi khi đúng hai đỉnh bậc lẻ; khi đó đường đi chạy từ đỉnh này sang đỉnh kia.

    Vì sao không thể đi qua mỗi cây trong bảy cầu Königsberg đúng một lần?

    Hãy vẽ mỗi vùng đất thành một đỉnh và mỗi cây cầu thành một cạnh. Đảo Kneiphof có năm cầu, ba vùng còn lại mỗi vùng ba cầu, nên cả bốn đỉnh đều lẻ. Một cuộc dạo chơi chỉ có thể bắt đầu hoặc kết thúc ở đỉnh bậc lẻ, mà bốn thì quá nhiều. Thêm một cầu giữa hai đỉnh trong số đó sẽ còn lại hai đỉnh bậc lẻ, và cuộc dạo chơi trở nên khả thi.

    Ngôi nhà ông già Noel có bao nhiêu cách vẽ?

    44 cách từ mỗi góc dưới, tổng cộng 88, nếu coi thứ tự hoặc chiều khác nhau là cách khác nhau. Từ bất kỳ đỉnh nào khác đều không vẽ được, vì chỉ hai góc dưới mới có số đường lẻ. Ứng dụng đếm số cách cho các hình nhỏ theo cách này.

    Cầu trong đồ thị là gì?

    Là một cạnh mà bỏ nó đi thì đồ thị liên thông tách thành hai mảnh. Thuật toán Fleury không bao giờ qua một cầu trong số các cạnh còn lại khi vẫn còn lựa chọn khác, vì làm vậy sẽ bỏ lại một phần của hình. Trong ứng dụng này, nét vẽ bị tắc sau khi qua cầu quá sớm sẽ được cho biết đó là bước thứ mấy.

    Giữa hai đỉnh có thể có nhiều hơn một cạnh không?

    Có. Đồ thị có các cạnh song song gọi là đa đồ thị, và Königsberg cần đến nó: hai cây cầu nối Kneiphof với mỗi bờ. Ở chế độ Vẽ, hãy chạm lại vào hai đỉnh để thêm một cạnh nữa giữa chúng, tối đa bốn cạnh. Quy tắc bậc vẫn áp dụng y như vậy và đếm từng cạnh.

    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.

    Tới trình chỉnh sửa