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

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

• $u_{\text{i}}$ liên kết với $(x_{\text{i}},x_{\text{i+1}})$ nếu đồ thị có hướng.
• $u_{\text{i}}$ liên kết với $(x_{\text{i}},x_{\text{i+1}})$ nếu đồ thị vô hướng.

Khi đó ta gọi $x_{\text{1}}$ là đỉnh đầu và $x_{\text{m}}$ là đỉnh cuối của đường đi.

Ví dụ

• 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

Tham khảo

• 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