Finden einer Abbildung in einem zweistufigen Graphen

Question

Es gibt eine quadratische binäre Matrix, die die Verbindungen in einem zweiseitigen Graphen bezeichnet. Die Frage ist: Gibt es eine Eins-zu-Eins-Zuordnung aller Zeilen zu den Spalten? (Falls ich mich falsch ausdrücke: ein vollständig verbundener Graph erfüllt diese Anforderung, da wir nicht auf eine Eins-zu-Eins-Abbildung beschränkt sind).

Ich habe das Folgende geschrieben. Gibt es eine lächerlich schnellere Möglichkeit, dies zu erreichen?

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

Ich nehme an, dass Sie mit Ihrer Darstellung einen zweiseitigen Graphen meinen, bei dem beide "Seiten" die gleiche Anzahl von Knoten haben, und dass graph[A][B] bedeutet, dass es eine Verbindung von Knoten A auf der "linken" Seite zu Knoten B auf der "rechten" Seite gibt, wenn alle Knoten in jeder Partition in einer vertikalen Linie angeordnet wären.

Ihr Algorithmus ist eigentlich gar nicht so schlecht, wenn der Graph spärlich ist, und er hat den Vorteil der Einfachheit.

Bei dichteren Diagrammen ist es exponentiell, und Sie können es besser machen, wenn Sie bereit sind, den Code dafür zu schreiben. Wenn man dem Graphen einen Quellknoten hinzufügt, der mit allen "linken" Knoten verbunden ist, und eine Senke, die mit allen "rechten" Knoten verbunden ist, und allen Kanten, einschließlich der neuen, die Kapazität 1 zuweist, dann ist der maximale Netzwerkfluss von der Quelle zur Senke gleich SIZE, wenn und nur wenn es eine Eins-zu-Eins-Paarung gibt. Wenn Sie einen Algorithmus wie den folgenden verwenden Ford-Fulkurson um den Fluss zu berechnen, verbindet jede Schleife ein zusätzliches Knotenpaar und ordnet die bestehenden Verbindungen nach Bedarf neu an, bis dies nicht mehr möglich ist. Die Laufzeit wird innerhalb von SIZE^3 liegen.

Dies kann auch direkt in Form eines bipartiten Graphen implementiert werden, indem man Paare von Übereinstimmungen neu anordnet, aber ich finde, dass es am einfachsten zu verstehen ist, wenn man es zunächst als Netzwerkfluss-Implementierung aufbaut und dann von dort aus umstrukturiert. Siehe den Abschnitt "Maximale Übereinstimmungen in zweiseitigen Graphen" auf der Wikipedia-Seite über Graphenübereinstimmungsprobleme für Informationen über das etwas allgemeinere Problem, eine maximale Anzahl von übereinstimmenden Paaren in einem zweiseitigen Graphen zu finden, was die flussbasierte Lösung eigentlich löst.

Wenn Sie WIRKLICH schnell sein wollen, sollten Sie einen Blick auf Hopcroft-Kamp die ich noch nicht umgesetzt habe und über die ich erst jetzt lese. Auf der verlinkten Seite heißt es, dass es (in diesem Beispiel) einen Worst Case von SIZE^(5/2) hat und bei der Optimierung für spärliche Graphen genauso gut oder besser ist als Ford-Fulkerson.