Đường đi (lý thuyết đồ thị)

Một đường đi trong G là một dãy luân phiên các đỉnhcạnh: ( là đỉnh và là cạnh). Trong đồ thị thỏa mãn điều kiện liên kết với cặp đỉnh , nghĩa là:

  • liên kết với nếu đồ thị có hướng.
  • liên kết với nếu đồ thị vô hướng.

Khi đó ta gọi đỉnh đầu và đỉnh cuối của đường đi.

Ví dụSửa đổi

  • Xét đồ thị G (7 đỉnh) vô hướng sau:
 
Đồ thị G
  • Dãy các đỉnh: 1 e2 4 e10 5 là một đường đi
    • Đỉnh đầu: 1
    • Đỉnh cuối: 5
  • Dãy các đỉnh: 4 e10 5 e9 3 e12 7 là một đường đi
    • Đỉnh đầu: 4
    • Đỉnh cuối: 7

Chú thíchSửa đổi

Tham khảoSửa đổi

  • Trần Đan Thư - Dương Anh Đức, Giáo trình lý thuyết đồ thị, Đại học Khoa học Tự nhiên Thành phố Hồ Chí Minh - Nhà xuất bản. ĐHQG Thành phố Hồ Chí Minh