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

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

2 голосов
/ 05 мая 2011

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

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

/* 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;
}

1 Ответ

1 голос
/ 05 мая 2011

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

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

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

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

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

...