Dây chuyền
![]() | Bài viết hoặc đoạn này cần người am hiểu về chủ đề này trợ giúp biên tập mở rộng hoặc cải thiện. |
Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. |
- 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:
- 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à:
- ui=(xi, xi+1) hay ui=(xi+1, xi) nếu đồ thị có hướng,
- 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ấp[sửa | sửa mã nguồn]
Dây chuyền sơ cấp là dây chuyền không có đỉnh lặp lại.
Chu trình[sửa | sửa mã nguồn]
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