¶ Tổng quan về lý thuyết đồ thị
- Tác giả: Võ Đức Đoàn - THPT Chuyên Nguyễn Tất Thành - Kon Tum
- Reviewer: Nguyễn Minh Hiển - Trường Đại học Công nghệ, ĐHQGHN
¶ Giới thiệu
Trước khi đến với lí thuyết đồ thị, ta có một câu hỏi nhỏ như sau:
Thành phố Königsberg thuộc Phổ, nay là Kaliningrad thuộc Nga, là một thành phố nằm ở 2 bên sông Pregel và có 2 hòn đảo lớn Kneiphof và Lomse. Trước kia, 2 hòn đảo được kết nối với nhau và với 2 bên bờ sông bằng 7 cây cầu.
Bài toán đặt ra ở đây là: Hãy tìm một con đường đi qua 7 cây cầu ít nhất một lần và chỉ một lần duy nhất.
Bài toán này - bài toán 7 cầu ở Königsberg, đã được giải bởi nhà toán học Leonhard Euler vào thế kỉ XVIII và đã cho ra đời định lý đầu tiên về lý thuyết đồ thị.
Trong bài viết này, ta sẽ tìm hiểu về lý thuyết đồ thị: định nghĩa, các dạng của đồ thị, một số khái niệm, tính chất liên quan, cách lưu trữ đồ thị trong chương trình và một số thuật toán liên quan đến đồ thị.
¶ Định nghĩa
Hình ảnh dưới đây là một ví dụ về một đồ thị:
Những vòng tròn được gọi là các đỉnh (vertices) hoặc các nút (nodes), và những đường thẳng nối những vòng tròn được gọi là các cạnh (edges).
Về cơ bản: Đồ thị là một tập hợp hữu hạn gồm các đỉnh và được nối với nhau bởi các cạnh.
Một đồ thị sẽ được kí hiệu:
Với là tập hợp chứa các đỉnh, và là tập hợp chứa các cạnh, mỗi cạnh có dạng một cặp giá trị (có thể được viết thành ). Ví dụ:
chính là đồ thị ở hình ví dụ trên.
Tập hợp đỉnh của đồ thị được kí hiệu , tập hợp cạnh được kí hiệu .
¶ Các dạng đồ thị
Các dạng đồ thị được nói đến dưới đây là một số dạng đồ thị phổ biến trong lập trình thi đấu.
¶ Đơn đồ thị
Một đồ thị không có khuyên, không có các cạnh song song, vô hướng và không có trọng số được gọi là đơn đồ thị (hay chỉ đơn giản là đồ thị).
Note:
- Khuyên là các cạnh có dạng .
- Hai hoặc nhiều cạnh song song với nhau khi các cạnh có chung hai điểm đầu mút.
¶ Đa đồ thị
Một đồ thị tồn tại các cạnh song song được gọi là đa đồ thị.
Đơn đồ thị là một dạng đặc biệt của đa đồ thị.
¶ Đồ thị vô hướng
Một đồ thị là vô hướng (undirected) khi cạnh không được chỉ định hướng. Nếu đồ thị tồn tại một cạnh , ta có thể đi theo hướng và hướng . Khi này, việc viết 2 cạnh và là như nhau và ta chỉ cần viết 1 trong 2 cạnh.
¶ Đồ thị có hướng
Một đồ thị là có hướng (directed) khi cạnh được chỉ định hướng. Điều này có nghĩa rằng nếu đồ thị tồn tại một cạnh , ta chỉ có thể đi theo hướng . Khi này, 2 cạnh và phân biệt.
¶ Đồ thị có trọng số
Một đồ thị có trọng số (weighted) là một đồ thị có các cạnh được gán một giá trị. Các giá trị có thể tượng trưng cho khoảng cách, chi phí di chuyển,...
¶ Đồ thị không có trọng số
Một đồ thị không có trọng số (unweighted) là một đồ thị các cạnh không được gán giá trị. Trong một số bài toán, có thể xem đồ thị không trọng số là một đồ thị có trọng số với các cạnh được gán giá trị bằng nhau (Ví dụ như có trọng số bằng 1).
¶ Đồ thị con
Một đồ thị là đồ thị con (subgraph) của một đồ thị khi tập đỉnh và tập cạnh của là tập con của các tập hợp tương ứng của , hay và thỏa mãn.
¶ Các dạng đồ thị đặc biệt
Một số dạng đồ thị đặc biệt ta cần biết.
¶ Đồ thị đầy đủ
Một đồ thị là đầy đủ khi tất cả các cặp đỉnh của đồ thị được nối với nhau bởi một cạnh.
Nếu một đồ thị có đỉnh vô hướng và đầy đủ, số cạnh của sẽ là .
¶ Đồ thị hai phía
Một đồ thị là hai phía (bipartite) khi tập đỉnh của nó có thể chia làm hai tập và rời nhau sao cho mỗi cạnh trong đồ thị phải nối một đỉnh trong tập với một đỉnh trong tập , và không cặp đỉnh nào liên thông nhau với mỗi tập.
¶ Directed acyclic graph (DAG)
DAG là một đồ thị có hướng không có chu trình . Một đồ thị có hướng được gọi là một DAG khi và chỉ khi đồ thị tồn tại thứ tự tô pô.
¶ Cây
Một đồ thị được gọi là một cây khi nó là một đồ thị vô hướng, liên thông và không có chu trình.
¶ Các khái niệm, tính chất
Ta cùng điểm qua một số khái niệm, tính chất liên quan đến đồ thị.
¶ Đỉnh kề, cạnh liền thuộc, đỉnh
Cho một đồ thị :
Hai đỉnh và của kề nhau (adjacent) khi , hay là một cạnh của . Khi này, ta nói cạnh là cạnh liên thuộc (incident) với hai đỉnh và , đồng thời , là hai đỉnh đầu mút (endpoints) của cạnh .
Cho đỉnh , các đỉnh hàng xóm (neighbours) với đỉnh là tất cả các đỉnh thỏa mãn , hay tất cả các đỉnh kề với .
Cho đỉnh , bậc (degree) của đỉnh chính là số lượng hàng xóm của đỉnh . Kí hiệu: . Ta có một số bổ đề về bậc như bổ đề bắt tay:
Nếu là một đồ thị có hướng, ta định nghĩa:
- Bán bậc ra (out-degree) của đỉnh , kí hiệu , là số lượng cạnh xuất phát từ đỉnh , hay giá trị của .
- Bán bậc vào (in-degree) của đỉnh kí hiệu , là số lượng cạnh kết thúc tại đỉnh , hay giá trị của .
Trong đồ thị có hướng, tổng bán bậc vào của tất cả các đỉnh luôn bằng tổng bán bậc ra của tất cả các đỉnh (vì mỗi cạnh có một đỉnh bắt đầu và một đỉnh kết thúc).
¶ Đường đi, chu trình
Cho một đồ thị :
Một đường đi (walk) (trong ) là một dãy các đỉnh thuộc và các cạnh là các cạnh thuộc đồ thị.
Một trail là một đường đi trong đó tất cả các cạnh trên đường đi đôi một phân biệt.
Một path là một đường đi trong đó tất cả các đỉnh trên đường đi đôi một phân biệt (suy ra các cạnh trên đường đi cũng đôi một phân biệt).
Với là một đường đi trong , ta có:
- là các đỉnh của .
- là các cạnh của .
- Độ dài (khoảng cách) của đường đi là một số nguyên không âm ( tương đương với số cạnh trên đường đi, và tương đương với số đỉnh). Nếu có trọng số, độ dài của đường đi là tổng trọng số của các cạnh trên đường đi.
- được gọi là đỉnh đầu (starting point) của , ta nói bắt đầu tại tại đỉnh .
- được gọi là đỉnh cuối (ending point) của , ta nói kết thúc tại tại đỉnh .
- Cho hai đỉnh và thuộc , ta nói đường đi từ đến là đường đi bắt đầu từ đỉnh và kết thúc tại đỉnh .
Một đường đi khép kín (closed walk) của một đường đi mà đỉnh cuối trùng với đỉnh đầu. Hay nói cách khác, là một dãy các đỉnh với .
Một chu trình (cycle) của là một đường đi khép kín với và các đỉnh đôi một phân biệt.
Một số trường hợp đặc biệt:
- Nếu là một đồ thị có hướng hoặc là một đa đồ thị, tồn tại chu trình có 2 đỉnh khi trong đồ thị tồn tại hai đỉnh và được nối với nhau bởi 2 cạnh song song. Ví dụ:
- tồn tại chu trình có 1 đỉnh nếu trong đồ thị tồn tại cạnh khuyên. Ví dụ:
Một đường đi (chu trình) là sơ cấp nếu nó không đi qua đỉnh nào hai lần trở lên. Một đường đi (chu trình) là đơn giản nếu nó không đi qua cạnh nào hai lần trở lên.
¶ Tính liên thông, khớp, cầu
Cho một đồ thị :
Hai đỉnh và của liên thông nếu tồn tại ít nhất 1 đường đi từ đến .
liên thông (connected) khi mọi cặp đỉnh của tồn tại đường đi.
song liên thông (biconnected) nếu nó liên thông và không có đỉnh khớp, nghĩa là nếu xóa một đỉnh bất kì thì đồ thị vẫn liên thông.Đối với một đồ thị có hướng:
- Một đồ thị có hướng được gọi là liên thông mạnh (strongly connected) nếu mọi cặp đỉnh của tồn tại đường đi.
- Một đồ thị có hướng được gọi là liên thông yếu (weakly connected) nếu khi ta xem đồ thị là một đồ thị vô hướng thì liên thông.
Đỉnh thuộc được gọi là khớp (articulation point) nếu khi ta xóa bỏ đỉnh khỏi đồ thị thì không còn liên thông.
Cạnh thuộc được gọi là cầu (bridge) nếu khi ta xóa bỏ cạnh khỏi đồ thị thì không còn liên thông.
Nếu không liên thông, sẽ tồn tại nhiều đồ thị con liên thông, rời nhau. Mỗi đồ thị con đó được gọi là một thành phần liên thông (TPLT) (connected component) của .
¶ Cây
Đối với các đồ thị cây, ta có thêm một số định nghĩa và tính chất:
Cho một đồ thị :
là cây khi nó thỏa mãn ít nhất 2 điều kiện dưới đây:
- không có chu trình
- liên thông
- Số cạnh bằng số đỉnh trừ 1 hay
là một rừng cây (forest) khi có nhiều hơn 1 TPLT, mỗi TPLT là một cây.
Chỉ tồn tại một đường đi độc nhất nối 2 đỉnh bất kì trên .
Thêm một cạnh bất kì chưa có trong sẽ xuất hiện một chu trình.
Đồng thời, việc xóa một cạnh bất kì trong sẽ làm tăng số TPLT của cây tất cả các cạnh trên đều là cạnh cầu.
¶ Gốc, lá, quan hệ giữa các đỉnh trong cây
Cho một đồ thị cây :
Gốc (root) của là một đỉnh thuộc được lựa chọn làm gốc. Thông thường, các bài toán đều chọn đỉnh 1 làm gốc của cây, nếu bài toán không chỉ rõ gốc của cây là đỉnh nào, hãy giả sử nó là đỉnh 1. Một số cây có thể không có gốc.
Đỉnh lá (leaf) của là các đỉnh có bậc bằng 1.
Nếu có gốc, các đỉnh thuộc sẽ hình thành quan hệ cha/con (parent/child).
Cụ thể:
- Với mỗi cặp cạnh bất kì: nếu khoảng cách tới gốc của ngắn hơn hơn khoảng cách tới gốc của , đỉnh sẽ là cha (parent) của đỉnh . Nếu khoảng cách tới gốc của dài hơn thì đỉnh sẽ là con (child) của đỉnh .
- Một đỉnh có thể có nhiều con, nhưng chỉ có một cha.
- Đỉnh gốc không có cha, đỉnh lá không có con.
- Đỉnh có khoảng cách tới gốc ngắn hơn sẽ là tổ tiên (ancestor) của đỉnh có khoảng cách tới gốc xa hơn. Ngược lại, đỉnh xa hơn sẽ là hậu duệ (descendant) của đỉnh gần hơn.
- Tổ tiên thứ k (Kth-ancestor) của một đỉnh là một đỉnh có hậu duệ là đỉnh và khoảng cách của 2 đỉnh đúng bằng k.
Khoảng cách từ gốc đến một đỉnh được gọi là chiều cao (height) hoặc chiều sâu (depth) của đỉnh. Chiều cao của cây là giá trị của đỉnh có chiều cao lớn nhất.
Đường kính (diameter) của cây là khoảng cách lớn nhất giữa hai đỉnh trong cây.
¶ Tổ chức dữ liệu
Có 3 cách phổ biến để biểu diễn đồ thị trong chương trình: ma trận kề, danh sách kề và danh sách cạnh. Tùy theo đề bài mà ta sẽ áp dụng các cách lưu trữ khác nhau.
Ta giả sử dữ liệu nhập của một đồ thị là một danh sách cạnh.
Đồ thị ví dụ:
¶ Ma trận kề (Adjacency matrix)
Ma trận kề là một cấu trúc đơn giản được dùng để lưu một đồ thị bất kì.
Để biểu diễn đồ thị trong ma trận kề, ta xây dựng ma trận vuông với:
- nếu
- nếu
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 2 | 1 | 0 | 1 | 0 | 1 | 0 |
| 3 | 0 | 1 | 0 | 1 | 0 | 0 |
| 4 | 0 | 0 | 1 | 0 | 1 | 1 |
| 5 | 1 | 1 | 0 | 1 | 0 | 0 |
| 6 | 0 | 0 | 0 | 1 | 0 | 0 |
Ngoài ra:
- Nếu đồ thị có trọng số, ta thay 1 bằng trọng số của cạnh tương ứng.
- Nếu đồ thị vô hướng, ta đánh dấu cả và , còn nếu có hướng thì chỉ đánh dấu .
const int N = 1010;
int n, m;
int adj[N][N];
int main() {
cin >> n >> m;
for(int i = 0; i < m; ++i){
int a, b; cin >> a >> b;
adj[a][b] = 1; // Nếu đồ thị có trọng số thì đổi 1 thành w
adj[b][a] = 1; // Nếu đồ thị có hướng thì không cần viết dòng này
}
return 0;
}
¶ Danh sách kề (Adjacency list)
Danh sách kề là cách lưu trữ đồ thị phổ biến trong lập trình thi đấu. Để biểu diễn đồ thị bằng danh sách kề, ta tạo mảng giá trị, mảng giá trị thứ lưu danh sách các đỉnh kề với đỉnh .
| Mảng danh sách kề | Các đỉnh kề |
|---|---|
adj[1] |
2, 5 |
adj[2] |
1, 3, 5 |
adj[3] |
2, 4 |
adj[4] |
3, 5, 6 |
adj[5] |
1, 2, 5 |
adj[6] |
4 |
const int N = 1e5 + 10;
int n, m;
vector<int> adj[N];
int main() {
cin >> n >> m;
for(int i = 0; i < m; ++i){
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a); // Nếu đồ thị có hướng thì không cần viết dòng này
}
return 0;
}
Nếu đồ thị có trọng số thì với mỗi cạnh (a, b) có trọng số w, ta lưu cặp giá trị (b, w) trong adj[a]. Có thể lưu cặp giá trị (b, w) bằng kiểu dữ liệu pair.
vector<pair<int, int>> adj[N];
adj[1].push_back({2, 3}); // lưu cạnh (1, 2) có trọng số 3
¶ Danh sách cạnh (Edge list)
Danh sách cạnh được dùng để lưu các cạnh trong đồ thị.
Ta có thể lưu các cạnh của đồ thị bằng pair hoặc tạo một cấu trúc struct tùy ý để lưu cặp giá trị có trong cạnh của đồ thị.
struct Edge{
int a, b, w; // w được dùng cho đồ thị có trọng số
Edge(int u, int v, int weight): a(u), b(v), w(weight){}
bool operator<(const Edge &e) const{
return w < e.w; // Sắp xếp theo trọng số các cạnh
}
};
int main() {
int n, m; cin >> n >> m;
vector<Edge> edges;
for(int i = 0; i < m; ++i){
int a, b, w; cin >> a >> b >> w;
edges.push_back(Edge(a, b, w));
}
return 0;
}
¶ Một số thuật toán liên quan đến đồ thị
¶ Duyệt đồ thị
Khi giải quyết các bài toán lí thuyết đồ thị, ta cần phải duyệt các đỉnh có trong đồ thị. Vì vậy việc biết các thuật toán duyệt đồ thị là việc vô cùng quan trọng.
Hai thuật toán duyệt đồ thị phổ biến là thuật toán duyệt theo chiều sâu (Depth-First Search - DFS) và duyệt theo chiều rộng (Breadth-First Search - BFS).
¶ Sắp xếp Tô-pô
Để xác định và tìm thứ tự tô-pô của một đồ thị có hướng, ta sử dụng thuật toán sắp xếp tô-pô.
¶ Tìm đường đi ngắn nhất
Bài toán tìm đường đi ngắn nhất trên đồ thị là loại bài toán đa dạng, có nhiều ứng dụng thực tế. Các dạng bài toán này xuất hiện thường xuyên trong lập trình thi đấu.
Ta có một số thuật toán tìm đường đi ngắn nhất như:
Nếu đồ thị là DAG, ta có thể tìm được đi ngắn nhất một cách tối ưu bằng cách áp dụng DFS + sắp xếp Tô-pô - Shortest Path DAG.
Ngoài ra, BFS có thể được dùng để tìm đường đi ngắn nhất trên đồ thị không có trọng số hoặc đồ thị có hướng với các cạnh có trọng số bằng 0 hoặc 1 - BFS 0 -1.
¶ Bài toán 2-SAT
Bài toán 2-SAT được phát biểu như sau:
Cho biến logic: và 1 biểu thức logic có dạng:
Trong đó và được thay bằng biển logic hoặc nào đó. .
Ta sẽ gán các với một trong hai giá trị sao cho biểu thức hợp lệ, hoặc thông báo rằng không thể có cách gán hợp lệ.
Ví dụ với biểu thức:
nếu ta gán , , , thì biểu thức trên hợp lệ.
Bài toán này có thể được giải bằng cách xét duyệt trâu, hoặc giải quyết một cách tối ưu bằng lý thuyết đồ thị: bài viết.
¶ Luồng cực đại/lát cắt cực tiểu
Thông tin về luồng cực đại/lát cắt cực tiểu sẽ được cập nhật sau.
¶ Đường đi Euler trên cây
Đường đi Euler trên cây (Euler tour on tree) là một phương pháp xử lí các bài toán có đồ thị cây bằng cách trải phẳng cây, từ đó các thao tác trên cây có thể được chuyển thành các thao tác trên mảng 1 chiều.
¶ Tổ tiên chung gần nhất
Lowest Common Ancestor (LCA) hay tổ tiên chung gần nhất của hai hay nhiều đỉnh là đỉnh sâu nhất là tổ tiên của tất cả các đỉnh.
Bạn có thể đọc thêm một số phương pháp giải LCA qua bài viết sau.
¶ Heavy-Light Decomposition (HLD)
Heavy-Light Decomposition (HLD) là kĩ thuật phân tách một cây thành tập hợp các chuỗi đường đi.
Đây là kĩ thuật có ý tưởng khá tự nhiên và có tính dụng cao trong nhiều bài toán. Bạn có thể đọc thêm tại bài viết này.
¶ Thuật toán phân tách trọng tâm
Thuật toán phân tách trọng tâm có thể hiểu là thuật toán "chia để trị" trên cây. Thuật toán này hoạt động bằng cách liên tục chia nhỏ cây và xử lý trên mỗi cây được chia.
Bạn có thể đọc thêm về thuật toán qua bài viết sau.
¶ Tham khảo
Bài viết này tham khảo thông tin về định nghĩa, các tính chất từ: An introduction to graph theory bởi Darij Grinberg.