Tất cả các đồ thị Hamilton là hai đường nối, nhưng một đồ thị hai đường nối không cần phải là Hamilton (ví dụ: xem đồ thị Petersen). Đồ thị Eulerian G (một đồ thị liên thông trong đó mọi đỉnh đều có bậc chẵn) nhất thiết phải có một chuyến tham quan Euler, một cuộc đi bộ khép kín đi qua mỗi cạnh của G đúng một lần.
Đồ thị có thể là Hamilton nhưng không phải là Eulerian không?
Một đồ thị liên thông G là Hamilton nếu có một chu trình bao gồm mọi đỉnh của G; một chu trình như vậy được gọi là chu trình Hamilton. … Biểu đồ này là CẢ HAI Eulerian và Hamilton. Đồ thị này là Eulerian, nhưng KHÔNG phải là Hamilton. Biểu đồ này làHamiltionian, nhưng KHÔNG PHẢI là Eulerian.
Có phải mọi đồ thị Hamilton đều là Eulerian không?
Không. Một đường đi Hamilton thăm mỗi đỉnh chính xác một lần nhưng có thể lặp lại các cạnh. Một mạch Eulerianđi qua mọi cạnh trong biểu đồ đúng một lần nhưng có thể lặp lại các đỉnh.
Eulerian không phải là Hamilton là gì?
Đồ thị lưỡng bội hoàn chỉnhK2, 4có một mạch Eulerian, nhưng không phải là Hamilton (trên thực tế, nó thậm chí không chứa một đường Hamilton). Bất kỳ đường đi Hamilton nào cũng sẽ có các màu xen kẽ (và không có đủ các đỉnh màu xanh lam).
Có phải tất cả các đồ thị hoàn chỉnh là Eulerian không?
Một đồ thị làEulerian nếu và chỉ khitung độ của mỗi đỉnh là chẵn. Do đó, Kn là Eulerian nếu n lẻ. (ii) Đồ thị hoàn chỉnh bán Eulerian duy nhất là K2. … Biểu đồ được kết nối và có chính xáchai đỉnh có bậc lẻ.
