Từ năm 2010 · Hơn 2 triệu lượt chạy công cụ mỗi tháng
Từ năm 2010
Thêm vào Chrome

Hộp Công Cụ Của Tôi

Chế Độ Tự Động

Chưa có công cụ nào được lưu.

Nâng Cấp Lên Phiên Bản Cao Cấp
Công cụ liên quan
Trình Kiểm Tra Đồ Thị PhẳngMáy tính Đường đi Ngắn nhất DijkstraDự đoán rụng trứng
Trang chủ > Toán học > Phép toán toán học nâng cao
 

Công cụ Kiểm tra Đường đi Hamilton

Kiểm tra xem một đồ thị có chứa đường đi hoặc chu trình Hamilton hay không. Chạy backtracking với cắt tỉa Warnsdorff, kiểm tra liên thông và bậc đỉnh, kiểm tra điều kiện Dirac và Ore, hiển thị đường đi minh chứng trên sơ đồ SVG.

Sử dụng miễn phíKhông cần đăng kýKết quả tức thì
Công cụ Kiểm tra Đường đi HamiltonDùng thử ngay — miễn phí ▼
Ví dụ nhanh:
K4 trừ một cạnh Chu trình 5 Đường đi tuyến tính Đồ thị Petersen Chu trình có hướng Ma trận 4×4
Chấp nhận A-B, A->B, A B, A,B, hoặc các hàng ma trận như 0 1 1 0. Sử dụng chữ cái, chữ số hoặc dấu gạch dưới cho nhãn.
Nhãn phân tách bằng dấu phẩy hoặc khoảng trắng, mỗi nhãn cho một hàng. Mặc định là A, B, C… nếu bỏ trống.

Embed Công cụ Kiểm tra Đường đi Hamilton Widget

Giới thiệu về Công cụ Kiểm tra Đường đi Hamilton

Công cụ kiểm tra Đường đi Hamilton xác định xem một đồ thị có chứa đường đi Hamilton — một trình tự đi qua mọi đỉnh đúng một lần — hay chu trình Hamilton, trình tự này bổ sung thêm việc quay lại đỉnh bắt đầu. Công cụ kết hợp các bước kiểm tra trước về cấu trúc nhanh (tính liên thông, các điều kiện tiên quyết về bậc, định lý Dirac, định lý Ore) với tìm kiếm quay lui được điều chỉnh bằng thuật toán Warnsdorff, và trực quan hóa đường đi chứng thực bằng ảnh động từng bước.

Đường đi Hamilton là gì?

Cho một đồ thị G = (V, E) với n đỉnh, một đường đi Hamilton là một trình tự có thứ tự v1, v2, …, vn của tất cả các đỉnh sao cho mỗi cặp liên tiếp (vi, vi+1) là một cạnh của G, và mọi đỉnh xuất hiện đúng một lần. Nếu thêm vào đó (vn, v1) là một cạnh, thì trình tự đó là một chu trình Hamilton.

Đường đi Hamilton: v1 — v2 — v3 — … — vn (tất cả khác biệt, mỗi cặp liên tiếp là một cạnh) Chu trình Hamilton: v1 — v2 — v3 — … — vn — v1 (khép kín trở lại điểm bắt đầu)

Bài toán này được đặt theo tên của William Rowan Hamilton, người vào năm 1857 đã phát minh ra trò chơi Icosian — một câu đố yêu cầu người giải tìm một chu trình đi qua mọi đỉnh của một hình thập nhị diện đều đúng một lần.

Tại sao bài toán này khó: NP-Đầy đủ

Cả bài toán quyết định đường đi Hamilton và bài toán quyết định chu trình Hamilton đều là các bài toán NP-đầy đủ (Karp, 1972). Trừ khi P = NP, không tồn tại thuật toán thời gian đa thức nào giải được mọi trường hợp. Trong trường hợp xấu nhất, quay lui phải khám phá một cây tìm kiếm có kích thước lên tới (n−1)! cho một chu trình. Đây là lý do tại sao máy tính giới hạn đầu vào ở mức 20 đỉnh — một sự gia tăng đa thức nhỏ trong n sẽ tạo ra sự gia tăng bùng nổ về thời gian chạy.

Trong thực tế, thuật toán Warnsdorff (ban đầu được Heinrich Warnsdorff nghĩ ra vào năm 1823 cho bài toán mã đi tuần) giúp quá trình tìm kiếm nhanh hơn đáng kể trên các đồ thị có cấu trúc: ở mỗi bước, thuật toán mở rộng đường đi hiện tại sang đỉnh hàng xóm chưa thăm có số lượng hàng xóm chưa thăm ít nhất. Quy tắc tham lam này giúp quá trình tìm kiếm không tự đưa mình vào ngõ cụt và thường tìm thấy hành trình Hamilton mà không cần quay lui chút nào trên các đồ thị có tính chất tốt.

Điều kiện cần — Loại bỏ nhanh

Trước khi chạy một tìm kiếm tốn kém, máy tính sẽ loại bỏ các đồ thị chắc chắn không thể chứa đường đi Hamilton:

Các quy tắc này loại bỏ nhiều đầu vào vô vọng trong thời gian tuyến tính, tránh lãng phí nỗ lực quay lui.

Điều kiện đủ — Định lý cổ điển

Một số định lý cổ điển đưa ra các điều kiện đủ (nhưng không phải là điều kiện cần) đảm bảo một chu trình Hamilton trong các đồ thị đơn vô hướng. Nếu bất kỳ định lý nào trong số này áp dụng được, máy tính sẽ đánh dấu kết quả là "ĐẢM BẢO" mà không cần chạy tìm kiếm — mặc dù nó vẫn hiển thị một chu trình chứng thực.

Định lý Dirac (1952)

Nếu G là một đồ thị vô hướng đơn có n ≥ 3 đỉnh và mọi đỉnh có bậc ít nhất n / 2, thì G có một chu trình Hamilton.

δ(G) ≥ n / 2 ⟹ G có tính chất Hamilton

Định lý Ore (1960)

Nếu đối với mỗi cặp đỉnh không kề nhau u và v, chúng ta có deg(u) + deg(v) ≥ n, thì G có một chu trình Hamilton. Điều kiện của Ore yếu hơn của Dirac một cách chặt chẽ, vì vậy Ore bao hàm cả Dirac.

∀ u, v không kề nhau: deg(u) + deg(v) ≥ n ⟹ G có tính chất Hamilton

Việc không thỏa mãn điều kiện Dirac hoặc Ore không có nghĩa là đồ thị thiếu chu trình Hamilton — nhiều đồ thị không thỏa mãn cả hai nhưng vẫn chứa một chu trình (ví dụ: một chu trình n đơn giản có bậc tối thiểu là 2, thấp hơn nhiều so với n/2 đối với n lớn).

Thuật toán tìm kiếm bên trong

Khi các bước kiểm tra trước không giải quyết được vấn đề, máy tính sẽ chạy tìm kiếm quay lui trên biểu diễn kề của đồ thị. Các chiến thuật chính:

  1. Bitmask cho tập hợp đã thăm. Các đỉnh đã thăm được lưu trữ dưới dạng bitmask (kiểm tra thành viên O(1) nhanh chóng cho tối đa 20 đỉnh).
  2. Thuật toán Warnsdorff. Tại mỗi lần mở rộng, các đỉnh hàng xóm được thử theo thứ tự bậc chưa thăm còn lại của chúng (nhỏ nhất trước), mô phỏng thứ tự "ít nhánh" nhất.
  3. Lựa chọn gốc. Đối với chu trình Hamilton, chỉ cần một đỉnh bắt đầu (chu trình có tính bất biến quay). Đối với đường đi Hamilton, các điểm bắt đầu được thử theo thứ tự tăng dần của bán bậc ra — các vị trí hiếm nhất trước.
  4. Ngân sách bước. Một giới hạn cứng giúp ngăn các trường hợp bệnh lý chạy vô tận; giao diện người dùng sẽ báo cáo kết quả là "quá thời gian" nếu ngân sách bị cạn kiệt.

Hamilton so với Euler

Rất dễ nhầm lẫn giữa các bài toán Hamilton và Euler — chúng nghe có vẻ giống nhau nhưng về cơ bản là khác nhau:

Thuộc tính Đường đi / Chu trình Hamilton Đường đi / Chu trình Euler
Đi qua mỗi… Đỉnh đúng một lần Cạnh đúng một lần
Độ phức tạp NP-đầy đủ Đa thức (O(n+m))
Điều kiện Không có đặc điểm đơn giản Liên thông + tất cả bậc chẵn (cho chu trình); tối đa 2 bậc lẻ cho đường đi
Đặt tên theo W. R. Hamilton (1857) L. Euler (1736, những cây cầu ở Königsberg)
Ví dụ kinh điển Người bán hàng rong, trò chơi Icosian Kiểm tra tuyến đường, bài toán người đưa thư

Các định dạng đầu vào được hỗ trợ

Danh sách cạnh

Mỗi cạnh trên một dòng, hoặc phân tách bằng dấu phẩy. Các dấu phân cách được hỗ trợ: A-B, A B, A,B, A--B, A->B, A<-B. Sử dụng -> để ép buộc hiểu theo hướng có hướng.

A-B, B-C, C-D, D-A, A-C (đồ thị vô hướng với 5 cạnh) A->B, B->C, C->D, D->A (chu trình 4 có hướng)

Ma trận kề

Ma trận vuông chứa các giá trị 0/1, mỗi hàng trên một dòng, phân tách bằng khoảng trắng hoặc dấu phẩy. Cung cấp nhãn tùy chọn trong trường Nhãn ma trận; nếu không, A, B, C… sẽ được sử dụng tự động.

0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0

Cách sử dụng trình kiểm tra này

  1. Chọn định dạng đầu vào — Danh sách cạnh cho các đồ thị nhỏ tự viết, Ma trận kề cho việc dán từ mã nguồn hoặc sách giáo khoa.
  2. Dán đồ thị của bạn vào vùng văn bản. Đối với đầu vào ma trận, tùy chọn cung cấp nhãn đỉnh.
  3. Chọn nội dung cần kiểm tra: Chỉ đường đi, Chỉ chu trình, hoặc Cả hai trong một lần chạy.
  4. Chọn loại đồ thị — Tự động phát hiện sẽ suy luận tính chất có hướng từ kiểu mũi tên (->) hoặc tính đối xứng của ma trận.
  5. Nhấp vào Kiểm tra Hamilton. Trang kết quả hiển thị tiêu đề kết luận, kiểm tra trước điều kiện cần, các bài kiểm tra điều kiện đủ Dirac / Ore, đường đi chứng thực (nếu có) và trực quan hóa tương tác.
  6. Phát lại chứng thực bằng các nút điều khiển Phát / Từng bước. Xem đường đi sáng lên từng cạnh trên đồ thị.

Ví dụ thực tế — Đồ thị Petersen

Đồ thị Petersen nổi tiếng (10 đỉnh, 15 cạnh, bậc 3 đều) là một ví dụ kinh điển trong sách giáo khoa về một đồ thị có đường đi Hamilton nhưng không có chu trình Hamilton. Dán nội dung này vào trường danh sách cạnh và nhấp Kiểm tra:

1-2, 2-3, 3-4, 4-5, 5-1, 6-8, 8-10, 10-7, 7-9, 9-6, 1-6, 2-7, 3-8, 4-9, 5-10

Trình kiểm tra xác nhận: Tìm thấy đường đi Hamilton (ví dụ: 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3), nhưng tìm kiếm toàn diện không tìm thấy cách nào để đóng vòng lặp trở lại — một kết quả được chứng minh lần đầu tiên vào những năm 1890.

Các ứng dụng phổ biến

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

Đường đi Hamilton là gì?

Đường đi Hamilton là một đường đi trong đồ thị đi qua mỗi đỉnh đúng một lần. Nó được đặt theo tên của William Rowan Hamilton, người đã nghiên cứu vấn đề này trên đồ thị thập nhị diện vào năm 1857. Việc quyết định xem một đường đi như vậy có tồn tại hay không là một bài toán NP-đầy đủ, vì vậy không có thuật toán nào được biết đến có thể giải nó trong thời gian đa thức cho mọi đồ thị.

Chu trình Hamilton khác với đường đi Hamilton như thế nào?

Chu trình Hamilton là một đường đi Hamilton quay trở lại đỉnh bắt đầu của nó, tạo thành một vòng khép kín đi qua mỗi đỉnh đúng một lần. Mọi chu trình Hamilton đều chứa một đường đi Hamilton (chỉ cần bỏ cạnh đóng), nhưng điều ngược lại thì không đúng: nhiều đồ thị có đường đi Hamilton nhưng không có chu trình Hamilton.

Định lý Dirac nói gì?

Định lý Dirac (1952) phát biểu rằng bất kỳ đồ thị vô hướng đơn nào có n ≥ 3 đỉnh, trong đó mỗi đỉnh có bậc ít nhất n/2, đều chứa một chu trình Hamilton. Đó là một điều kiện đủ nhưng không phải là điều kiện cần: nhiều đồ thị không đạt ngưỡng Dirac vẫn có chu trình Hamilton.

Định lý Ore nói gì?

Định lý Ore (1960) phát biểu rằng nếu, đối với mọi cặp đỉnh không kề nhau u và v trong một đồ thị đơn có n ≥ 3 đỉnh, tổng các bậc của chúng ít nhất là n, thì đồ thị đó có một chu trình Hamilton. Điều kiện của Ore yếu hơn của Dirac, vì vậy định lý Ore áp dụng được bất cứ khi nào định lý Dirac áp dụng được.

Tại sao việc tìm kiếm bị giới hạn ở 20 đỉnh?

Các bài toán quyết định đường đi và chu trình Hamilton là NP-đầy đủ. Thời gian chạy trong trường hợp xấu nhất tăng theo cấp số nhân với số đỉnh. Với việc cắt tỉa và thuật toán Warnsdorff, máy tính xử lý nhanh chóng nhiều đồ thị nhỏ lên đến 20 đỉnh, nhưng các trường hợp khó hơn có thể bị quá thời gian. Ngoài 20 đỉnh, bạn nên sử dụng các trình giải chuyên dụng như Concorde hoặc các công thức lập trình nguyên.

Thuật toán Warnsdorff là gì?

Quy tắc Warnsdorff, được đề xuất vào năm 1823 cho bài toán mã đi tuần, nói rằng ở mỗi bước bạn nên thăm đỉnh tiếp theo có ít hàng xóm chưa thăm nhất. Quy tắc có vẻ tham lam này thực tế giúp cắt tỉa đáng kể cây quay lui và thường tìm thấy đường đi Hamilton mà không cần quay lui chút nào trên các đồ thị chính quy.

Công cụ này có tìm thấy tất cả các đường đi Hamilton không?

Không — nó tìm thấy một đường đi hoặc chu trình chứng thực duy nhất khi có tồn tại. Việc đếm tổng số đường đi Hamilton bản thân nó là một bài toán #P-đầy đủ và khó hơn nhiều so với bài toán quyết định. Để liệt kê, các công cụ chuyên dụng hoặc trình giải lập trình nguyên sẽ phù hợp hơn.

Đọc thêm

Tham khảo nội dung, trang hoặc công cụ này như sau:

"Công cụ Kiểm tra Đường đi Hamilton" tại https://MiniWebtool.com/vi/cong-cu-kiem-tra-uong-i-hamilton/ từ MiniWebtool, https://MiniWebtool.com/

bởi đội ngũ miniwebtool. Cập nhật: 21 tháng 4, 2026

Bạn cũng có thể thử AI Giải Toán GPT của chúng tôi để giải quyết các vấn đề toán học của bạn thông qua câu hỏi và trả lời bằng ngôn ngữ tự nhiên.

Phép toán toán học nâng cao:

Công cụ phổ biến và mới cập nhật:

Kiểm tra Số FibonacciKiểm tra Số Thân ThiếtKiểm tra hàm chẵn lẻXem tất cả →
Trang chủ > Toán học > Phép toán toán học nâng cao > Công cụ Kiểm tra Đường đi Hamilton