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

Необходимо в двудольном графе найти минимальное вершинное покрытие

Вершинное покрытие графа - некоторое множество вершин графа такое, что любая вершина графа либо принадлежит покрытию, либо связана ребром с вершиной из покрытия.

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

Асимптотика O(NM²).

P.S. ниже приведена реализация жадного алгоритма, возможно в будущем на нашем сайте появится реализация более эффективного алгоритма .

Листинг C++

// процедура включения вершины в покрытие
void include_to_set (int v, vector < vector < int > > &e, vector < int > &degree,
                     vector < int > &is1, vector < int > &is2)
{
    is1[v] = 1;
    for (int i = 0; i < e[v].size (); ++ i)
    {
        int u = e[v][i];
        is2[u - is1.size ()] = 1;

        for (int j = 0; j < e[u].size (); ++ j)
            -- degree[e[u][j]];
    }
}
// минимальное вершинное покрытие в двудольном графе
void min_vert_set (int n, int m, vector < vector < int > > &e, vector < int > &p)
{
    int i, j;

    vector < int > is1 (n, 0); // включена ли вершина перво доли в покрытие
    vector < int > is2 (m, 0); // связана ли вершина второй доли с покрытием
    vector < int > degree (n + m, 0); // степени вершин
    for (i = 0; i < n + m; ++ i)
        degree[i] = e[i].size ();

    // включаем в покрытие все вершины первой доли связанные с одностепенными вершинами
    for (i = n; i < n + m; ++ i)
        if (degree[i] == 1)
            include_to_set (e[i][0], e, degree, is1, is2);

    // есть ли вершины во второй доле, не связанные с покрытием
    bool flag = 0;
    for (i = n; i < n + m; ++ i)
        flag = (flag || ! is2[i - n]);

    while (flag)
    {
        // выбираем среди вершину первой доли с максимальной степенью
        for (i = 0; i < n && is1[i] == 1; ++ i);
        for (j = i + 1; j < n; ++ j)
            if (is1[j] == 0 && degree[j] > degree[i])
                i = j;

        // если все вершины первой доли уже в покрытии - выход
        if (i >= n)    break;

        // включаем выбранную вершину в покрытие
        include_to_set (i, e, degree, is1, is2);

        // есть ли вершины во второй доле, не связанные с покрытием
        flag = 0;
        for (i = n; i < n + m; ++ i)
            flag = (flag || ! is2[i - n]);
    }

    // формируем результат
    for (i = 0; i < n; ++ i)
        if (is1[i])
            p.push_back (i);
}

31.08.2008, 16:28

По всем вопросам обращаться: rumterg@gmail.com