Lý Thuyết Phủ Đỉnh Và Ghép Cặp Trong Đồ Thị Hai Phía
Mối quan hệ giữa phủ đỉnh cực tiểu và ghép cặp cực đại là một nền tảng quan trọng. Theo định lý Konig, trong đồ thị hai phía, số lượng đỉnh cần để phủ tất cả các cạnh bằng đúng số lượng cạnh lớn nhất có thể chọn sao cho không có hai cạnh nào chung đỉnh.
Để tìm tập hợp đỉnh cụ thể cho bài toán phủ cực tiểu, ta có thể mô hình hóa bài toán thành luồng cực đại. Sau khi chạy thuật toán tìm luồng, thực hiện duyệt trên đồ thị dư. Các đỉnh thuộc tập phủ sẽ được xác định dựa trên khả năng tiếp cận từ nguồn trong đồ thị dư này.
Tập Độc Lập Cực Đại
Số lượng đỉnh lớn nhất trong một tập độc lập của đồ thị hai phía có thể tính bằng tổng số đỉnh trừ đi số cạnh của ghép cặp cực đại. Đối với phiên bản có trọng số, ta gán khả năng thông qua của các cạnh nối từ nguồn và tới đích bằng trọng số của đỉnh tương ứng. Luồng cực đại tìm được sẽ tương ứng với phủ đỉnh cực tiểu có trọng số.
Phủ Đường Đi Trên DAG
Bài toán tìm số đường đi ít nhất để phủ tất cả các đỉnh trong đồ thị có hướng không chu trình (DAG) có thể quy về bài toán ghép cặp trên đồ thị hai phía. Ta tách mỗi đỉnh v thành hai đỉnh v_in và v_out. Nếu có cạnh u -> v trong DAG, ta nối u_out tới v_in.
Công thức tính số đường đi tối thiểu là:
Số đường đi = Tổng số đỉnh - Luồng cực đại tìm đượcTrường hợp các đường đi được phép giao nhau (dùng lại đỉnh), ta cần thực hiện bao đóng bắc cầu (transitive closure) trên DAG trước khi xây dựng mô hình luồng. Thuật toán Floyd-Warshall có thể được sử dụng để xác định tất cả các cặp đỉnh có thể đến được nhau.
Định lý Dilworth Và Phản Dây
Trong một DAG, độ dài của phản dây dài nhất (tập hợp các đỉnh không có đường đi giữa chúng) bằng số lượng đường đi ít nhất cần để phủ các đỉnh (có thể giao nhau). Việc xây dựng tập phản dây này có thể thực hiện thông qua việc tìm tập độc lập cực đại trên đồ thị hai phía đã được chuyển đổi.
Lý Thuyết Về Vết Cắt Cực Tiểu (Min-Cut)
Định lý luồng cực đại - vết cắt cực tiểu khẳng định giá trị luồng cực đại luôn bằng khả năng thông qua nhỏ nhất của một vết cắt ngăn cách nguồn và đích. Để xác định các cạnh thuộc vết cắt cực tiểu, ta duyệt từ nguồn trên đồ thị dư sau khi đã tìm được luồng cực đại. Các cạnh nối từ một đỉnh đã duyệt tới một đỉnh chưa duyệt và có luồng đầy chính là các cạnh của vết cắt.
Để tìm các cạnh bắt buộc phải thuộc mọi vết cắt cực tiểu, ta cần kiểm tra xem cạnh đó có đầy luồng hay không và hai đầu mút của nó có thuộc cùng một thành phần liên thông mạnh trong đồ thị dư hay không.
Kỹ Thuật Tách Đỉnh Và Cạnh
Trong nhiều bài toán luồng phức tạp, việc giới hạn khả năng thông qua tại đỉnh hoặc chi phí sử dụng cạnh cần được mô hình hóa cẩn thận:
- Tách đỉnh: Biến một đỉnh thành hai đỉnh (vào và ra) nối bởi một cạnh có khả năng thông qua bằng giới hạn của đỉnh đó. Kỹ thuật này thường dùng để kiểm soát số lần một trạng thái được ghé thăm.
- Tách cạnh: Khi chi phí hoặc khả năng thông qua phụ thuộc vào số lần sử dụng, ta có thể tạo nhiều cạnh song song với các thông số khác nhau để mô phỏng hàm chi phí lồi hoặc các ràng buộc phức tạp.
Cài Đặt Thuật Toán Luồng
Dưới đây là các mẫu cài đặt tối ưu cho bài toán luồng cực đại và luồng cực đại chi phí cực tiểu. Các biến và cấu trúc đã được điều chỉnh để đảm bảo tính rõ ràng và hiệu suất.
Thuật Toán Dinic
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 5005;
const int INF = 1e9;
struct Edge {
int to, cap, flow, next;
};
Edge edges[MAXN * 10];
int head[MAXN], level[MAXN], cur[MAXN];
int edgeCount, source, sink, nodeCount;
void initGraph(int n, int s, int t) {
nodeCount = n;
source = s;
sink = t;
edgeCount = 0;
memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int capacity) {
edges[edgeCount] = {v, capacity, 0, head[u]};
head[u] = edgeCount++;
edges[edgeCount] = {u, 0, 0, head[v]};
head[v] = edgeCount++;
}
bool bfs() {
fill(level, level + nodeCount + 1, -1);
vector<int> q;
q.reserve(nodeCount);
level[source] = 0;
q.push_back(source);
int headIdx = 0;
while(headIdx < q.size()) {
int u = q[headIdx++];
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].to;
if (level[v] == -1 && edges[i].cap - edges[i].flow > 0) {
level[v] = level[u] + 1;
q.push_back(v);
}
}
}
return level[sink] != -1;
}
int dfs(int u, int pushed) {
if (pushed == 0 || u == sink) return pushed;
for (int &i = cur[u]; i != -1; i = edges[i].next) {
int v = edges[i].to;
if (level[v] != level[u] + 1 || edges[i].cap - edges[i].flow == 0) continue;
int tr = dfs(v, min(pushed, edges[i].cap - edges[i].flow));
if (tr == 0) continue;
edges[i].flow += tr;
edges[i ^ 1].flow -= tr;
return tr;
}
return 0;
}
int maxFlow() {
int flow = 0;
while (bfs()) {
memcpy(cur, head, sizeof(head));
while (int pushed = dfs(source, INF)) {
flow += pushed;
}
}
return flow;
}
Luồng Cực Đại Chi Phí Cực Tiểu (MCMF)
const int MAXM = 50005;
struct CostEdge {
int to, cap, cost, next;
};
CostEdge costEdges[MAXM];
int dist[MAXN], parentEdge[MAXN], parentNode[MAXN];
bool inQueue[MAXN];
int mcmfEdgeCount;
void initMCMF() {
mcmfEdgeCount = 0;
memset(head, -1, sizeof(head));
}
void addCostEdge(int u, int v, int cap, int cost) {
costEdges[mcmfEdgeCount] = {v, cap, cost, head[u]};
head[u] = mcmfEdgeCount++;
costEdges[mcmfEdgeCount] = {u, 0, -cost, head[v]};
head[v] = mcmfEdgeCount++;
}
bool spfa() {
fill(dist, dist + nodeCount + 1, INF);
fill(inQueue, inQueue + nodeCount + 1, false);
vector<int> q;
dist[source] = 0;
q.push_back(source);
inQueue[source] = true;
int idx = 0;
while(idx < q.size()) {
int u = q[idx++];
inQueue[u] = false;
for (int i = head[u]; i != -1; i = costEdges[i].next) {
int v = costEdges[i].to;
if (costEdges[i].cap > 0 && dist[v] > dist[u] + costEdges[i].cost) {
dist[v] = dist[u] + costEdges[i].cost;
parentNode[v] = u;
parentEdge[v] = i;
if (!inQueue[v]) {
q.push_back(v);
inQueue[v] = true;
}
}
}
}
return dist[sink] != INF;
}
pair<int, int> minCostMaxFlow() {
int totalFlow = 0;
int totalCost = 0;
while (spfa()) {
int push = INF;
int curr = sink;
while (curr != source) {
int idx = parentEdge[curr];
push = min(push, costEdges[idx].cap);
curr = parentNode[curr];
}
totalFlow += push;
totalCost += push * dist[sink];
curr = sink;
while (curr != source) {
int idx = parentEdge[curr];
costEdges[idx].cap -= push;
costEdges[idx ^ 1].cap += push;
curr = parentNode[curr];
}
}
return {totalFlow, totalCost};
}
Một Số Lưu Ý Khi Implement
- Khởi tạo mảng khoảng cách hoặc mức độ bằng giá trị vô cùng lớn, tránh dùng giá trị 0 để ngăn lỗi logic.
- Chỉ số cạnh thường bắt đầu từ 0 hoặc 1, cần đồng bộ khi sử dụng phép toán XOR để tìm cạnh ngược.
- Đối với bài toán chi phí, cần chú ý kích thước hàng đợi trong thuật toán SPFA để tránh tràn bộ nhớ trong các trường hợp đồ thị dày đặc.
- Khi xây dựng mô hình, hãy cẩn thận với hướng của cạnh, đặc biệt là các cạnh nối từ nguồn hoặc tới đích.
Ứng Dụng Trên Đồ Thị Lưới
Khi làm việc với đồ thị dạng lưới, kỹ thuật tô màu đen trắng để chuyển về đồ thị hai phía là một phương pháp phổ biến. Ngoài ra, việc chuyển đổi sang đồ thị đối ngẫu (dual graph) có thể giúp giải quyết các bài toán tìm đường đi ngắn nhất hoặc cắt cực tiểu trên mặt phẳng hiệu quả hơn.
Định Lý Hall
Trong đồ thị hai phía đều nhau, điều kiện cần và đủ để tồn tại ghép cặp hoàn hảo là với mọi tập con các đỉnh thuộc tập trái, số lượng đỉnh kề của chúng phải lớn hơn hoặc bằng kích thước tập con đó. Điều này thường được sử dụng để chứng minh sự tồn tại của lời giải trong các bài toán ghép cặp có ràng buộc đặc biệt.