Dây chuyền

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 là dây chuyền không có đỉnh lặp lạ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 lý thuyết đồ thị Đồ thị có hướng Đồ thị vô hướng Thuật ngữ lý thuyết đồ thị Dây chuyền sản xuất