Đồ thị phẳng và đồ thị đối ngẫu
Công thức Euler V - E + F = 1 + C để đếm miền, đồ thị đối ngẫu nối các mặt, và hệ quả quan trọng nhất: lát cắt nhỏ nhất trên đồ thị phẳng bằng đường đi ngắn nhất trên đồ thị đối ngẫu.
Một đồ thị là phẳng (planar) nếu vẽ được trên mặt phẳng sao cho các cạnh chỉ gặp nhau tại đầu mút. Khi đã có một cách vẽ, các cạnh chia mặt phẳng thành các mặt (face): các vùng bị chặn và đúng một vùng vô hạn bên ngoài. Trong đề thi, đồ thị phẳng xuất hiện tự nhiên dưới dạng lưới ô vuông, lưới lục giác, bản đồ các bức tường, hàng rào, hay đồ thị cho kèm toạ độ các đỉnh và cạnh là đoạn thẳng không cắt nhau.
Hai công cụ biến bài toán khó trên đồ thị phẳng thành bài dễ:
- Công thức Euler (với là số thành phần liên thông): đếm số miền mà không cần dựng hình, chỉ cần đếm đỉnh, cạnh và thành phần.
- Đồ thị đối ngẫu : mỗi mặt là một đỉnh, mỗi cạnh của cho một cạnh nối hai mặt hai bên . Dưới phép đối ngẫu, lát cắt của trở thành chu trình của . Hệ quả hay dùng nhất: lát cắt nhỏ nhất giữa hai đỉnh trên biên ngoài bằng đường đi ngắn nhất trên , chạy Dijkstra thay vì luồng cực đại.
Với lưới ô, luồng cực đại là quá chậm, còn Dijkstra hay 0-1 BFS trên đồ thị đối ngẫu chạy trong tích tắc.
Ý tưởng / Trực giác
Công thức Euler. Với đồ thị phẳng liên thông: (đếm cả mặt ngoài). Chứng minh quy nạp theo số cạnh:
- Nếu đồ thị là cây: và chỉ có một mặt (mặt ngoài), nên .
- Nếu có chu trình: bỏ một cạnh trên chu trình. Đồ thị vẫn liên thông, giảm , và hai mặt ở hai bên cạnh đó (khác nhau, vì cạnh nằm trên chu trình, theo định lý đường cong Jordan) nhập làm một, nên giảm . Biểu thức không đổi.
Với thành phần, áp dụng cho từng thành phần rồi trừ đi lần mặt ngoài bị đếm thừa: . Hệ quả: một đồ thị phẳng đơn với có (mỗi mặt có ít nhất cạnh, mỗi cạnh giáp tối đa mặt, nên ). Vì vậy đồ thị phẳng luôn thưa: , và luôn có đỉnh bậc .
Đồ thị đối ngẫu. Với phẳng liên thông đã vẽ, có một đỉnh cho mỗi mặt; mỗi cạnh ngăn cách hai mặt cho cạnh nối và (nếu hai bên là cùng một mặt thì là khuyên; điều này xảy ra đúng khi là cầu). cũng phẳng, và .
Lát cắt chu trình. Một tập cạnh là lát cắt tối tiểu (xoá đi thì mất liên thông, bớt bất kỳ cạnh nào thì không) của khi và chỉ khi là một chu trình của . Trực giác: một chu trình trong là một đường cong khép kín đi qua các mặt, cắt đúng các cạnh của ; theo Jordan, nó chia mặt phẳng làm hai, các đỉnh của bên trong và bên ngoài bị tách rời. Đối ngẫu lại: chu trình của ứng với lát cắt tối tiểu của , và cây khung của có phần bù đối ngẫu là cây khung của .
Lát cắt - nhỏ nhất bằng đường đi ngắn nhất. Giả sử và cùng nằm trên biên của mặt ngoài. Thêm (trong tưởng tượng) một cạnh - đi vòng ngoài: nó chia mặt ngoài thành hai mặt và . Một lát cắt tách khỏi của , cộng thêm cạnh tưởng tượng, là một chu trình trong đối ngẫu đi qua cạnh ; bỏ cạnh đó đi còn một đường đi từ tới . Ngược lại mọi đường đi tới là một đường cong cắt ngang từ biên này sang biên kia, tách khỏi . Gán trọng số bằng sức chứa của :
Trên lưới, là phần biên ngoài "phía trên và bên phải", là "phía dưới và bên trái" (hai cung biên giữa ở góc trái trên và ở góc phải dưới). Đây chính là hình ảnh "dựng một bức tường rẻ nhất nối hai cung biên".
Mẹo 8 hướng. Khi chặn ô (đỉnh) thay vì cạnh trên lưới ô, bức tường chặn được là một dãy ô bị chặn kề nhau theo 8 hướng nối hai cung biên: hai ô kề góc đã đủ chặn vì kẻ địch chỉ đi theo 4 hướng.
Ví dụ chạy tay
Công thức Euler. Hình chữ "田" gồm ô vuông đơn vị có điểm lưới, đoạn đơn vị, , nên : bốn ô bên trong và miền ngoài.
Lát cắt nhỏ nhất qua đối ngẫu. Lưới đỉnh, , , số trên cạnh là sức chứa. Bốn ô vuông là bốn đỉnh đối ngẫu ; mặt ngoài tách thành (phía trên và bên phải) và (phía dưới và bên trái):
S* (trên, phải)
s ---7--- . ---1--- .
| | |
6 c00 6 c01 1
| | | S*
. ---2--- . ---4--- .
| | |
T* 4 c10 1 c11 9
| | |
. ---5--- . ---8--- t
T* (dưới, trái)
Mỗi cạnh của lưới nối hai mặt ở hai bên nó. Ví dụ cạnh ngang trên cùng bên phải (sức chứa ) nối với ; cạnh dọc trái dưới (sức chứa ) nối với . Danh sách kề của đối ngẫu:
| đỉnh đối ngẫu | kề (trọng số) |
|---|---|
| (7), (1), (1), (9) | |
| (7), (6), (2), (6) | |
| (1), (1), (6), (4) | |
| (2), (1), (5), (4) | |
| (9), (4), (1), (8) |
Dijkstra từ cho khoảng cách , , , , . Đường đi ngắn nhất
cắt bốn cạnh có sức chứa : cạnh -, -, -, -. Xoá chúng thì bốn đỉnh góc trái trên tách khỏi phần còn lại, lát cắt nhỏ nhất bằng (luồng cực đại Dinic trên lưới gốc cũng cho ).
Cài đặt
Lát cắt nhỏ nhất giữa hai góc lưới bằng Dijkstra trên đối ngẫu
Đầu vào: (), sau đó dòng mỗi dòng sức chứa cạnh ngang h[i][j] (nối với ), rồi dòng mỗi dòng sức chứa cạnh dọc v[i][j] (nối với ).
#include <bits/stdc++.h>
using namespace std;
// Lát cắt nhỏ nhất giữa góc (0,0) và góc (R-1,C-1) của đồ thị lưới R x C có trọng số cạnh,
// tính bằng đường đi ngắn nhất trên đồ thị đối ngẫu (mỗi ô vuông là một đỉnh đối ngẫu).
// h[i][j]: cạnh nối (i,j)-(i,j+1); v[i][j]: cạnh nối (i,j)-(i+1,j).
long long planar_min_cut(int R, int C, const vector<vector<long long>>& h,
const vector<vector<long long>>& v) {
int K = (R - 1) * (C - 1);
int S = K, T = K + 1; // S: mặt ngoài phía trên/phải, T: phía dưới/trái
auto cell = [&](int i, int j) { return i * (C - 1) + j; };
vector<vector<pair<int, long long>>> adj(K + 2);
auto add = [&](int a, int b, long long w) {
adj[a].push_back({b, w});
adj[b].push_back({a, w});
};
for (int i = 0; i < R; i++)
for (int j = 0; j + 1 < C; j++) { // cạnh ngang ngăn ô trên và ô dưới
int up = (i == 0) ? S : cell(i - 1, j);
int down = (i == R - 1) ? T : cell(i, j);
add(up, down, h[i][j]);
}
for (int i = 0; i + 1 < R; i++)
for (int j = 0; j < C; j++) { // cạnh dọc ngăn ô trái và ô phải
int left = (j == 0) ? T : cell(i, j - 1);
int right = (j == C - 1) ? S : cell(i, j);
add(left, right, v[i][j]);
}
// Dijkstra từ S tới T
vector<long long> dist(K + 2, LLONG_MAX);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
dist[S] = 0;
pq.push({0, S});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
if (u == T) return d;
for (auto [w, c] : adj[u])
if (d + c < dist[w]) {
dist[w] = d + c;
pq.push({dist[w], w});
}
}
return dist[T];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int R, C; // R * C >= 2
cin >> R >> C;
vector<vector<long long>> h(R, vector<long long>(max(C - 1, 0)));
vector<vector<long long>> v(max(R - 1, 0), vector<long long>(C));
for (auto& row : h)
for (auto& x : row) cin >> x;
for (auto& row : v)
for (auto& x : row) cin >> x;
cout << planar_min_cut(R, C, h, v) << '\n';
}
import sys
import heapq
# Lát cắt nhỏ nhất giữa góc (0,0) và góc (R-1,C-1) của đồ thị lưới R x C có trọng số cạnh,
# tính bằng đường đi ngắn nhất trên đồ thị đối ngẫu (mỗi ô vuông là một đỉnh đối ngẫu).
# h[i][j]: cạnh nối (i,j)-(i,j+1); v[i][j]: cạnh nối (i,j)-(i+1,j).
def planar_min_cut(R, C, h, v):
K = (R - 1) * (C - 1)
S, T = K, K + 1 # S: mặt ngoài phía trên/phải, T: phía dưới/trái
adj = [[] for _ in range(K + 2)]
def add(a, b, w):
adj[a].append((b, w))
adj[b].append((a, w))
for i in range(R):
for j in range(C - 1): # cạnh ngang ngăn ô trên và ô dưới
up = S if i == 0 else (i - 1) * (C - 1) + j
down = T if i == R - 1 else i * (C - 1) + j
add(up, down, h[i][j])
for i in range(R - 1):
for j in range(C): # cạnh dọc ngăn ô trái và ô phải
left = T if j == 0 else i * (C - 1) + j - 1
right = S if j == C - 1 else i * (C - 1) + j
add(left, right, v[i][j])
# Dijkstra từ S tới T
INF = float("inf")
dist = [INF] * (K + 2)
dist[S] = 0
pq = [(0, S)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
if u == T:
return d
for w, c in adj[u]:
if d + c < dist[w]:
dist[w] = d + c
heapq.heappush(pq, (dist[w], w))
return dist[T]
def main():
data = sys.stdin.read().split()
R, C = int(data[0]), int(data[1]) # R * C >= 2
p = 2
h = []
for _ in range(R):
h.append([int(x) for x in data[p : p + C - 1]])
p += C - 1
v = []
for _ in range(R - 1):
v.append([int(x) for x in data[p : p + C]])
p += C
print(planar_min_cut(R, C, h, v))
main()
Đếm số miền bằng công thức Euler
Đầu vào: , rồi đoạn thẳng đơn vị (nằm ngang hoặc dọc) x1 y1 x2 y2, có thể trùng nhau. In số miền mà các đoạn chia mặt phẳng ra, kể cả miền vô hạn. Đỉnh và cạnh phải được đếm phân biệt; số thành phần đếm bằng DSU.
#include <bits/stdc++.h>
using namespace std;
// Đếm số miền (kể cả miền vô hạn bên ngoài) mà một tập đoạn thẳng đơn vị trên lưới
// chia mặt phẳng ra, theo công thức Euler: V - E + F = 1 + C.
struct DSU {
vector<int> p;
DSU(int n) : p(n) { iota(p.begin(), p.end(), 0); }
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a), b = find(b);
if (a == b) return false;
p[a] = b;
return true;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
map<pair<int, int>, int> id; // đỉnh phân biệt
set<pair<int, int>> edges; // cạnh phân biệt (cặp id, nhỏ trước)
auto get = [&](int x, int y) {
auto it = id.find({x, y});
if (it != id.end()) return it->second;
int k = id.size();
id[{x, y}] = k;
return k;
};
for (int i = 0; i < n; i++) {
int x1, y1, x2, y2; // đoạn đơn vị nằm ngang hoặc dọc
cin >> x1 >> y1 >> x2 >> y2;
int a = get(x1, y1), b = get(x2, y2);
edges.insert({min(a, b), max(a, b)});
}
long long V = id.size(), E = edges.size(), C = V;
DSU dsu(V);
for (auto [a, b] : edges)
if (dsu.unite(a, b)) C--; // mỗi lần hợp nhất bớt một thành phần
cout << E - V + 1 + C << '\n'; // F = E - V + 1 + C
}
import sys
# Đếm số miền (kể cả miền vô hạn bên ngoài) mà một tập đoạn thẳng đơn vị trên lưới
# chia mặt phẳng ra, theo công thức Euler: V - E + F = 1 + C.
def main():
data = sys.stdin.read().split()
n = int(data[0])
ident = {} # đỉnh phân biệt
edges = set() # cạnh phân biệt (cặp id, nhỏ trước)
def get(x, y):
if (x, y) not in ident:
ident[(x, y)] = len(ident)
return ident[(x, y)]
for i in range(n):
x1, y1, x2, y2 = map(int, data[1 + 4 * i : 5 + 4 * i]) # đoạn đơn vị ngang hoặc dọc
a, b = get(x1, y1), get(x2, y2)
edges.add((min(a, b), max(a, b)))
V, E = len(ident), len(edges)
parent = list(range(V))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
C = V
for a, b in edges:
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
C -= 1 # mỗi lần hợp nhất bớt một thành phần
print(E - V + 1 + C) # F = E - V + 1 + C
main()
Với đồ thị tổng quát cho bằng toạ độ (cạnh là đoạn thẳng bất kỳ), các mặt được dựng bằng duyệt nửa cạnh: ở mỗi đỉnh sắp xếp các cạnh kề theo góc; từ nửa cạnh , nửa cạnh tiếp theo trên cùng mặt là với là láng giềng liền trước theo thứ tự góc quanh . Mỗi chu trình nửa cạnh là một mặt, diện tích có hướng âm (hoặc bằng ) là mặt ngoài.
Độ phức tạp
| Thao tác | Thời gian | Bộ nhớ |
|---|---|---|
| Đếm miền bằng Euler (DSU) | với map/set, nếu đánh số đỉnh trực tiếp |
|
| Dựng đối ngẫu của lưới | ||
| Lát cắt nhỏ nhất qua đối ngẫu (Dijkstra) | ||
| Như trên, trọng số (0-1 BFS) | ||
| Dựng mặt bằng duyệt nửa cạnh | (sắp xếp theo góc) |
Vì sao nhanh hơn luồng? Luồng cực đại trên lưới đỉnh cần nhiều pha tăng luồng, mỗi pha hoặc hơn. Đối ngẫu chỉ cần một lần tìm đường đi ngắn nhất, và đồ thị đối ngẫu có số đỉnh bằng số mặt theo công thức Euler, số cạnh bằng đúng .
⚠️ Lỗi thường gặp
- Đếm trùng đỉnh hoặc cạnh trong công thức Euler: khi hàng rào đi lại qua cùng một đoạn, phải đếm cạnh phân biệt; quên khử trùng thì quá lớn và số miền sai. Cũng nhớ khi đồ thị không liên thông (dùng cho đồ thị nhiều thành phần là sai).
- Gán sai mặt ngoài cho hai cung biên: với ở góc trái trên và ở góc phải dưới, cạnh trên biên trên và biên phải nối với , biên dưới và trái nối với . Đảo một trong bốn biên là đường đi đối ngẫu "đi tắt" qua biên và cho đáp án quá nhỏ.
- Áp dụng khi hoặc không nằm trên mặt ngoài: phép quy về đường đi ngắn nhất chỉ đúng khi và cùng nằm trên biên một mặt (thường là mặt ngoài). Với ở giữa lưới, đường đi đối ngẫu phải là một chu trình bao quanh mà không bao , cần kỹ thuật khác (cắt theo một đường từ tới ).
- Quên chặn theo 8 hướng khi chặn ô: nếu kẻ địch đi theo 4 hướng thì bức tường gồm các ô bị chặn kề nhau theo 8 hướng; chỉ dùng 4 hướng cho đáp án quá lớn. Ngược lại, kẻ địch đi 8 hướng thì bức tường chỉ được nối theo 4 hướng.
- Cạnh song song và cầu trong đối ngẫu: đồ thị đối ngẫu thường có cạnh song song (hai cạnh gốc cùng ngăn hai mặt) và khuyên (ứng với cầu của đồ thị gốc). Đừng gộp hay bỏ chúng khi bài toán đếm cạnh; với bài đường đi ngắn nhất thì giữ cạnh nhỏ nhất là đủ.
- Tràn số khi cộng trọng số: tổng sức chứa trên đường đi đối ngẫu có thể vượt ; dùng
long long.
Biến thể / Mở rộng
- Đường đi ngắn nhất trên đối ngẫu: chi tiết Dijkstra và 0-1 BFS (trọng số cho ô tường, cho ô thường) xem Dijkstra (Đường đi ngắn nhất) và 0-1 BFS. Khi đồ thị không phẳng, quay về Max Flow (Dinic).
- Chu trình và lát cắt: cầu của là khuyên của , cặp cạnh tạo lát cắt cạnh là cặp cạnh song song của , lát cắt cạnh là tam giác. Kết hợp với Bridge và Articulation Point để xử lý cầu trực tiếp.
- Cây khung đối ngẫu: phần bù của một cây khung của , lấy đối ngẫu, là cây khung của . Thêm cạnh theo thứ tự ngược và theo dõi mặt nào nối với mặt ngoài bằng DSU là kỹ thuật "Kruskal ngược" để biết khi nào một miền bị bao kín; xem thêm Cây khung nhỏ nhất (MST).
- Tô màu mặt và tập cạnh bậc chẵn: trên đồ thị phẳng liên thông, các tập cạnh mà mọi đỉnh có bậc chẵn tương ứng một-một với cách tô các mặt bằng hai màu (mặt ngoài màu , cạnh được chọn khi và chỉ khi hai bên khác màu). Bài chọn cạnh tạo thành các chu trình rời nhau thường đổi thành bài tô ô, rồi quy hoạch động theo hàng như DP bitmask.
- Điểm thuộc mặt nào: xác định mặt chứa một điểm cho trước dùng Point in Polygon (Điểm trong đa giác) hoặc Sweep Line (Quét đường thẳng).
Bài tập luyện
- Xây cổng (gates): (Hard) Hàng rào đi theo bước trên lưới chia mặt phẳng thành nhiều vùng, tìm số cổng ít nhất để nối thông mọi vùng. Đáp án là số miền trừ , tính bằng công thức Euler với đỉnh và cạnh phân biệt.
- Trận chiến Hogwarts (icpc20natb): (Very Hard) Chặn ít ô nhất để kẻ địch không đi được từ góc trái trên tới góc phải dưới của lưới ô. Đối ngẫu: tìm bức tường rẻ nhất gồm các ô kề 8 hướng nối hai cung biên, bằng 0-1 BFS.
- Ranh giới công trình (icpc26natb): (Expert) Xây dần các bức tường không cắt nhau, sau mỗi bước in tổng diện tích bị bao kín. Dựng các mặt của đồ thị cuối cùng bằng duyệt nửa cạnh, rồi thêm cạnh đối ngẫu theo thứ tự ngược vào DSU để biết lúc mỗi mặt bị bao kín.
- Tô màu lục giác (icpc20regh): (Expert) Đếm số cách tô cạnh của lưới lục giác thành các vòng rời nhau với số cạnh tô của mỗi ô cho trước. Tập cạnh bậc chẵn tương ứng với cách tô các mặt (ô) bằng hai màu, rồi quy hoạch động theo hàng.
- Loại bỏ cạnh (icpc24nate): (Expert) Đếm số bộ cạnh mà xoá đi làm đồ thị phẳng mất liên thông. Lát cắt ứng với chu trình trong đối ngẫu, nên đếm khuyên, cặp cạnh song song và tam giác của đồ thị đối ngẫu.
- Tô hai màu bảng (icpc25regb): (Master) Bật tắt các cạnh tô đậm theo truy vấn, sau mỗi truy vấn cho biết bảng có tô hai màu theo thành phần được không. Trên đối ngẫu các điểm lưới, điều kiện thành bậc chẵn tại mọi điểm và đối ngẫu không có cầu, xử lý offline.
Bình luận