Dây chuyền

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
  • 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ấ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

Ví dụ[sửa | sửa mã nguồn]

Đọc thêm[sửa | sửa mã nguồn]

Chú thích[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]