Đường đi (lý thuyết đồ thị)
Bài viết hoặc đoạn này cần người am hiểu về chủ đề này trợ giúp biên tập mở rộng hoặc cải thiện. |
Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. |
Một đường đi trong G là một dãy luân phiên các đỉnh và cạ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.
Ví dụSửa đổi
- Xét đồ thị G (7 đỉnh) vô hướng sau:
- 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