• Cho đồ thị G=(X, U).
  • Một dây chuyền trong G là một dãy luân phiên các đỉnh và cạnh:
  1. x1 u1 x2 u2... xm-1 um-11 xm (xi là đỉnh và ui là cạnh)
Trong đồ thị thỏa mãn điều kiện ui liên kết với cặp đỉnh xi, xi+1 không phân biệt thứ tự, nghĩa là:
  1. ui=(xi, xi+1) hay ui=(xi+1, xi) nếu đồ thị có hướng,
  2. ui={xi, xi+1} nếu đồ thị vô hướng.
  • Khi đó ta gọi x1 là đỉnh đầu và xm là đỉnh cuối của dây chuyền.

Dây chuyền sơ cấpSửa đổi

Dây chuyền sơ cấp là dây chuyền không có đỉnh lặp lại.

Chu trìnhSửa đổi

Chu trình là một dây chuyền x1 u1 x2 u2... xm-1 um-1 xm um x1 sao cho các đỉnh x1, x2,..., xm đôi một khác nhau

Ví dụSửa đổi

Đọc thêmSửa đổi

Chú thíchSửa đổi

Tham khảoSửa đổi