Найти отображение в двудольном графе

Question

Существует квадратная двоичная матрица, которая обозначает связи в двудольном графе. Вопрос в том, существует ли взаимно-однозначное сопоставление всех строк и столбцов? (Для ясности, если я использую неправильный язык, полностью связанный граф удовлетворяет этому требованию, так как мы не ограничены ТОЛЬКО однозначным отображением).

Я написал следующее. Есть ли смехотворно быстрый способ сделать это?

/* Is there a one-to-one mapping possible with the given bipartite graph?
   input:  graph[a][b] = connected (1) or not (0)
   return: 0=no 1=yes */
int one_to_one(int graph[SIZE][SIZE], int rows_checked /* =0 */, int col_chosen /* =0 */)
{
    int my_graph[SIZE][SIZE], i, j, retval;
    memcpy(my_graph, graph, sizeof(graph[0][0]) * SIZE * SIZE);

    if (rows_checked > 0) 
        for (i=rows_checked; i<SIZE; i++)
            my_graph[i][col_chosen] = -1; /* flag for "this column done" */

    retval=1;
    for (i=0; i<SIZE; i++) {
        if (my_graph[rows_checked][i] == -1)
                    continue;
        retval=0;
        if (my_graph[rows_checked][i] == 1)
            if (one_to_one(my_graph, rows_checked+1, i))
                return 1;
    }
    return retval;
}

Answer 1

Я предполагаю, что в вашем представлении вы имеете в виду, что у вас есть двудольный граф, в котором обе "стороны" имеют одинаковое количество узлов, и этот граф [A][B] означает, что существует соединение от узла A на " слева "до узла B" справа ", если все узлы в каждом разделе были расположены вертикально.

Ваш алгоритм на самом деле не так уж плох, если график разрежен, и он имеет преимущество простоты.

Для более плотных графиков это экспоненциально, и вы можете добиться большего успеха, если захотите написать код для него. Если вы добавляете исходный узел к графу, подключенному ко всем "левым" узлам, и приемник, подключенный ко всем "правым" узлам, и назначаете емкость 1 для всех ребер, включая новые, то максимальный сетевой поток от источника к сток равен РАЗМЕРУ, если и только если есть спаривание один к одному. Если вы используете алгоритм, такой как Ford-Fulkurson, для расчета потока, каждый цикл будет соединять дополнительную пару узлов, переставляя существующие соединения по мере необходимости, чтобы это произошло, пока это больше не станет возможным. Время выполнения будет в пределах РАЗМЕРА ^3.

Это также может быть реализовано непосредственно с точки зрения представления двудольного графа и перестановки пар совпадений, но я считаю, что проще всего понять, если вы построите его как реализацию сетевого потока для запуска, а затем рефакторинга обратно оттуда. См. Раздел "Максимальное совпадение в двудольных графах" на странице Википедии о проблемах сопоставления графов для получения информации о слегка более общей задаче, если вы найдете максимальное число совпадающих пар в двудольном графе, что и является решением, основанным на потоке. решает.

Если вы ДЕЙСТВИТЕЛЬНО хотите скорость, взгляните на Хопкрофт-Камп, которую я еще не реализовал и сейчас читаю о себе. Связанная страница утверждает, что она имеет наихудший случай (в этом примере) SIZE^(5/2) и так же хороша или лучше подходит для оптимизации разреженных графиков, как Ford-Fulkerson.