Đườ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

Dây chuyền

• Cho đồ thị G=(X, U).
• Một dây chuyền trong đồ thị (G) là một dãy luân phiên các đỉnh và cạnh:

1. x₁ u₁ x₂ u₂... x_m-1 u_m-11 x_m (x_i là đỉnh và u_i 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. u_i =(x_i, x_i+1) hay u_i = (x_i+1, x_i) nếu đồ thị có hướng,
2. u_i = {x_i, (x_i+1)} nếu đồ thị vô hướng.

• Khi đó ta gọi x₁ là đỉnh đầu và x_m là đỉnh cuối của dây chuyền.

Tính chất "đơn" và "sơ cấp" của đường đi và dây chuyền trong đồ thị

• Tính chất "đơn" của dây chuyền hay đường đi yêu cầu không có cạnh nào xuất hiện hai lần trong dây chuyền hay đường đi đó.
• Tính chất "sơ cấp" (hay cũng gọi là "thứ cấp") yêu cầu không có đỉnh nào xuất hiện hai lần.

Chu trình và Mạch

• Một chu trình trong đồ thị là một dây chuyền đơn mà có đỉnh đầu trùng đỉnh cuối, tức la dây chuyền có dạng: x₁ u₁ x₂ u₂… x_m-1 u_m-1 x_m u_m x₁

sao cho các cạnh u₁, u₂,…,u_m đôi một khác nhau.

• Một mạch trong đồ thị là một đường đi đơn mà có đỉnh đầu trùng đỉnh cuối, tức là đường đi có dạng: x₁ u₁ x₂ u₂… x_m-1 u_m-1 x_m u_m x₁

sao cho các cạnh u₁, u₂,…,u_m đôi một khác nhau. Từ các định nghĩa trên, ta có các khái niệm sau đây thường được dùng trong lý thuyết đồ thị:

Dây chuyền sơ cấp

• Dây chuyền sơ cấp là dây chuyền không có đỉnh lập lại.

Đường đi sơ cấp

• Đường đi sơ cấp là đường đi không có đỉnh lập lại.

Chu trình sơ cấp

• Chu trình sơ cấp là đường đi không có đỉnh lập lại (ngoại trừ đỉnh đầu và đỉnh cuối).

Mạch sơ cấp

• Mạch sơ cấp là mạch không có đỉnh lập lại (ngoại trừ đỉnh đầu và đỉnh cuối).

Ghi Chú

Trong trường hợp đồ thị vô hướng thì:

• Hai khái niệm dây chuyền và đường đi là như nhau,
• Hai khái niệm chu trình và mạch là như nhau.
• Do đó chúng ta cũng dùng thuật ngữ đường đi cho đồ thị vô hướng. đôi khi một mạch trong đồ thị có hướng cũng được gọi là một " chu trình có hướng ", hay một đường đi trong đồ thị có hướng cũng được gọi là " đường đi có hướng" để nhấn mạnh.

Khi các cạnh hoàn toàn được hiểu rõ (chẳng hạn như trong một đồ thị vô hướng không có cạnh song song) thì:

• Một dây chuyền x₁ u₁ x₂ u₂…x_n-1 u_n-1 x_n có thể viết gọn là x₁ x₂…x_n-1 x_n.
• Một chu trình x₁ u₁ x₂ u₂…x_n-1 u_n-1 x_n có thể viết gọn là x₁ x₂…x_n-1 x_n.

Đọc thêm

• lý thuyết đồ thị
• Đồ thị có hướng
• Đồ thị vô hướng
• Thuật ngữ lý thuyết đồ thị
• Dây chuyền

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

Liên kết ngoài

• Sách trực tuyến về Lý thuyết đồ thị
• Hướng dẫn về lý thuyết đồ thị Lưu trữ 2012-01-16 tại Wayback Machine
• Bài giảng của một môn học về các thuật toán đồ thị Lưu trữ 2005-08-31 tại Wayback Machine
• Minh họa hoạt hình về các thuật toán đồ thị
  • Lần bước thuật toán để tìm hiểu.
• Tóm tắt các trang minh họa thuật toán Lưu trữ 2008-06-01 tại Wayback Machine
• Dữ liệu test chuẩn cho các bài toán đồ thị con đầy đủ lớn nhất (Maximum Clique), tập con độc lập lớn nhất (Maximum Independent Set), phủ đỉnh nhỏ nhất (Minimum Vertex Cover) và tô màu đỉnh (Vertex Coloring) Lưu trữ 2013-05-29 tại Wayback Machine
• Sưu tập ảnh số 1: một số mạng lưới thực
• Sưu tập ảnh số 1: một số mạng lưới thực Lưu trữ 2012-02-23 tại Wayback Machine
• Sưu tập các liên kết về đồ thị
• Các tạp chí lý thuyết đồ thị Lưu trữ 2013-07-04 tại Wayback Machine
• Sách về lý thuyết đồ thị Lưu trữ 2012-09-11 tại Wayback Machine