Chu trình (lý thuyết đồ thị)

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Một đồ thị đơn có chu trình.

Trong lý thuyết đồ thị, chu trình trong đồ thị là một đường đi đóng.

Đồ thị chỉ gồm một chu trình với n đỉnh được gọi là đồ thị vòng, ký hiệu Cn,

Các loại chu trình:

  • Chu trình chẵn: là chu trình có độ dài chẵn.
  • Chu trình lẻ: là chu trình có độ dài lẻ.
  • Chu trình có hướng: là một chu trình đơn mà mọi cung trong đó đều cùng hướng, nghĩa là mọi đỉnh đều có bậc trong và bậc ngoài bằng 1. Có thể gọi đơn giản là chu trình khi ngữ cảnh rõ ràng.
  • Chu trình đơn: là chu trình đi qua mỗi đỉnh không quá một lần. Trong đồ thị ở hình trên, (1, 5, 2, 1) là một chu trình đơn. Nếu không chỉ rõ, chu trình thường được hiểu là một chu trình đơn.
  • Chu trình Euler: là chu trình qua tất cả các cạnh, mỗi cạnh đúng một lần.
  • Chu trình bao trùm: là cách gọi khác của chu trình Hamilton.