Định lý Euler về chu trình Euler
Phát biểu
Một đa đồ thị hữu hạn liên thông có chu trình Euler — một đường đi khép kín đi qua mỗi cạnh đúng một lần — khi và chỉ khi mọi đỉnh đều có bậc chẵn.
Vì sao đúng?
Mỗi khi một đường đi bước vào một đỉnh qua một cạnh chưa dùng, nó phải rời đi qua một cạnh chưa dùng khác, ghép các cạnh kề với đỉnh đó thành từng cặp. Nếu mọi đỉnh đều có số cạnh chẵn, bạn không bao giờ bị mắc kẹt giữa chừng ngoại trừ ở chính đỉnh xuất phát, và mọi vòng còn sót lại đều có thể ghép nối vào hành trình chính.
Phác thảo chứng minh
Điều kiện cần là hiển nhiên vì mỗi lần đi qua một đỉnh dùng hai cạnh kề (một vào, một ra). Với điều kiện đủ, xuất phát từ một đỉnh bất kỳ và đi theo các cạnh chưa dùng cho tới khi bị kẹt; bậc chẵn bảo đảm chỉ có thể bị kẹt tại chính đỉnh xuất phát, tạo thành một chu trình. Nếu vẫn còn cạnh chưa dùng, do tính liên thông nên có một đỉnh trên chu trình vẫn còn cạnh kề chưa dùng; xuất phát một chu trình khác từ đó trong đồ thị phần dư (vẫn có mọi bậc đều chẵn) rồi ghép nó vào, lặp lại cho tới khi dùng hết mọi cạnh.
Người phát biểu
Chủ đề chứa định lý này
Định lý liên quan
Chứng minh từng bước
Chưa có chứng minh từng bước cho định lý này.
Tài liệu tham khảo
- Leonhard Euler (1741). Solutio problematis ad geometriam situs pertinentis · DOI:10.1090/spec/098/33