Dây chuyền
Bước tới điều hướng
Bước tới tìm kiếm
![]() | Bài hay đoạn này cần người am hiểu về chủ đề này trợ giúp biên tập để cải thiện bài viết. Bạn có thể giúp chỉnh sửa bài hoặc nhờ một ai đó. Xem trang thảo luận để biết thêm chi tiết. |
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