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

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

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

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

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

Построение

Минимальное вершинное покрытие

Максимальное независимое множество

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

Рёбра из максимального паросочетания ориентируем из правой доли в левую
Рёбра не из максимального паросочетания ориентируем из левой доли в правую

Запускаем DFS из всех вершин левой доли вспомогательного графа, в которые не входят рёбра
MVC — объединение непосещённых вершин левой доли и посещённых вершин правой доли

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

Рёбра из максимального паросочетания ориентируем из правой доли в левую
Рёбра не из максимального паросочетания ориентируем из левой доли в правую

Запускаем DFS из всех вершин левой доли вспомогательного графа, в которые не входят рёбра
MIS — объединение посещённых вершин левой доли и непосещённых вершин правой доли

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 (!visited[i])
            a.push_back(i);

    vector<int> b;
    for (int i = 0; i < d.bn; i++)
        if (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 (visited[i])
            a.push_back(i);

    vector<int> b;
    for (int i = 0; i < d.bn; i++)
        if (!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);
}

Ссылки

Теория:

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

Построение

Ссылки

Навигация

Поиск