Ctrlalt: Новая страница: «Минимальное вершинное покрытие (minimum vertex cover, MVC) — минимальный по размеру набор вершин, с...»

2021-08-31T01:33:25Z

Новая страница: «Минимальное вершинное покрытие (minimum vertex cover, MVC) — минимальный по размеру набор вершин, с...»

Новая страница

Минимальное вершинное покрытие (minimum vertex cover, MVC) — минимальный по размеру набор вершин, содержащий хотя бы один конец каждого ребра.

В двудольном графе размер минимального вершинного покрытия совпадает с размером максимального паросочетания.

Максимальное независимое множество (maximum independent set, MIS) — максимальный по размеру набор вершин, никакие две из которых не соединены ребром.

В любом графе максимальное независимое множество — дополнение минимального вершинного покрытия (содержит все вершины, не входящие в минимальное вершинное покрытие).

== Построение ==

{|width=100%
|
; Минимальное вершинное покрытие
|
; Максимальное независимое множество
|-
|
* Вычисляем максимальное паросочетание
* Строим вспомогательный ориентированный двудольный граф
:* Рёбра из максимального паросочетания ориентируем из правой доли в левую
:* Рёбра не из максимального паросочетания ориентируем из левой доли в правую
* Запускаем DFS из всех вершин левой доли вспомогательного графа, в которые не входят рёбра
* MVC — объединение {{Changed|непосещённых}} вершин левой доли и {{Changed|посещённых}} вершин правой доли

|
* Вычисляем максимальное паросочетание
* Строим вспомогательный ориентированный двудольный граф
:* Рёбра из максимального паросочетания ориентируем из правой доли в левую
:* Рёбра не из максимального паросочетания ориентируем из левой доли в правую
* Запускаем DFS из всех вершин левой доли вспомогательного графа, в которые не входят рёбра
* MIS — объединение {{Changed|посещённых}} вершин левой доли и {{Changed|непосещённых}} вершин правой доли

|-
|
struct Data {
int an = 0, bn = 0;
vector<pair<int, int>> edges;
};

Data readData() {
Data d;
int edgeCount;

cin >> d.an >> d.bn >> edgeCount;

d.edges.resize(edgeCount);
for (auto &[a, b] : d.edges)
cin >> a >> b;

return d;
}

Graph computeMaxMatching(Data &d) {
Graph g(1 + d.an + d.bn + 1);

for (int a = 0; a < d.an; a++)
g.addEdge(0, 1 + a, 1);

for (auto &[a, b] : d.edges)
g.addEdge(1 + a, 1 + d.an + b, 1);

for (int b = 0; b < d.bn; b++)
g.addEdge(1 + d.an + b, 1 + d.an + d.bn, 1);

g.maxFlow(0, 1 + d.an + d.bn);

return g;
}

vector<vector<int>> buildMVCGraph(Data &d, Graph &g) {
vector<vector<int>> mg(d.an + d.bn);

for (auto &[a, b, _, flow] : g.edges) {
if (0 != a && b != 1 + d.an + d.bn) {
if (flow)
mg[b - 1].push_back(a - 1);
else
mg[a - 1].push_back(b - 1);
}
}

return mg;
}

void dfs(vector<vector<int>> &g, int v, vector<int> &visited) {
visited[v] = 1;
for (int to : g[v])
if (!visited[to])
dfs(g, to, visited);
}

pair<vector<int>, vector<int>> computeMVC(Data &d, vector<vector<int>> &g) {
set<int> startVertices;
for (int i = 0; i < d.an; i++)
startVertices.insert(i);

for (auto &row : g)
for (int to : row)
startVertices.erase(to);

vector<int> visited(d.an + d.bn);
for (int v : startVertices)
dfs(g, v, visited);

vector<int> a;
for (int i = 0; i < d.an; i++)
if ({{Changed|!visited[i]}})
a.push_back(i);

vector<int> b;
for (int i = 0; i < d.bn; i++)
if ({{Changed|visited[d.an + i]}})
b.push_back(i);

return { a, b };
}

void solve() {
auto d = readData();
auto g = computeMaxMatching(d);
auto mg = buildMVCGraph(d, g);
auto [a, b] = computeMVC(d, mg);
}
|
struct Data {
int an = 0, bn = 0;
vector<pair<int, int>> edges;
};

Data readData() {
Data d;
int edgeCount;

cin >> d.an >> d.bn >> edgeCount;

d.edges.resize(edgeCount);
for (auto &[a, b] : d.edges)
cin >> a >> b;

return d;
}

Graph computeMaxMatching(Data &d) {
Graph g(1 + d.an + d.bn + 1);

for (int a = 0; a < d.an; a++)
g.addEdge(0, 1 + a, 1);

for (auto &[a, b] : d.edges)
g.addEdge(1 + a, 1 + d.an + b, 1);

for (int b = 0; b < d.bn; b++)
g.addEdge(1 + d.an + b, 1 + d.an + d.bn, 1);

g.maxFlow(0, 1 + d.an + d.bn);

return g;
}

vector<vector<int>> buildMVCGraph(Data &d, Graph &g) {
vector<vector<int>> mg(d.an + d.bn);

for (auto &[a, b, _, flow] : g.edges) {
if (0 != a && b != 1 + d.an + d.bn) {
if (flow)
mg[b - 1].push_back(a - 1);
else
mg[a - 1].push_back(b - 1);
}
}

return mg;
}

void dfs(vector<vector<int>> &g, int v, vector<int> &visited) {
visited[v] = 1;
for (int to : g[v])
if (!visited[to])
dfs(g, to, visited);
}

pair<vector<int>, vector<int>> computeMIS(Data &d, vector<vector<int>> &g) {
set<int> startVertices;
for (int i = 0; i < d.an; i++)
startVertices.insert(i);

for (auto &row : g)
for (int to : row)
startVertices.erase(to);

vector<int> visited(d.an + d.bn);
for (int v : startVertices)
dfs(g, v, visited);

vector<int> a;
for (int i = 0; i < d.an; i++)
if ({{Changed|visited[i]}})
a.push_back(i);

vector<int> b;
for (int i = 0; i < d.bn; i++)
if ({{Changed|!visited[d.an + i]}})
b.push_back(i);

return { a, b };
}

void solve() {
auto d = readData();
auto g = computeMaxMatching(d);
auto mg = buildMVCGraph(d, g);
auto [a, b] = computeMIS(d, mg);
}
|}

== Ссылки ==
Теория:
* [https://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B2%D1%8F%D0%B7%D1%8C_%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D1%8F_%D0%B8_%D0%BC%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D0%B8%D1%8F_%D0%B2_%D0%B4%D0%B2%D1%83%D0%B4%D0%BE%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D0%B3%D1%80%D0%B0%D1%84%D0%B0%D1%85 neerc.ifmo.ru/wiki — Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]
* [https://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B2%D1%8F%D0%B7%D1%8C_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%BE%D0%BA%D1%80%D1%8B%D1%82%D0%B8%D1%8F_%D0%B8_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%BE%D0%B3%D0%BE_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0 neerc.ifmo.ru/wiki — Связь вершинного покрытия и независимого множества]

Минимальное вершинное покрытие, максимальное независимое множество - История изменений

Ctrlalt: Новая страница: «Минимальное вершинное покрытие (minimum vertex cover, MVC) — минимальный по размеру набор вершин, с...»