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:

1. x₁ u₁ x₂ u₂... x_m-1 u_m-11 x_m (x_i là đỉnh và u_i là cạnh)

Trong đồ thị thỏa mãn điều kiện u_i liên kết với cặp đỉnh x_i, x_i+1 không phân biệt thứ tự, nghĩa là:

1. u_i=(x_i, x_i+1) hay u_i=(x_i+1, x_i) nếu đồ thị có hướng,
2. u_i={x_i, x_i+1} nếu đồ thị vô hướng.

• Khi đó ta gọi x₁ là đỉnh đầu và x_m là đỉnh cuối của dây chuyền.

Dây chuyền sơ cấp

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

Chu trình

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

Đọc thêm

• 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