Suche Algorithmus fuer Graphenproblem

Hi Forum,

ich bin auf der Suche nach einem Algorithmus der folgendes feststellen kann.
Ich habe einen Graph bestehend aus 2*N Knoten, dieser Graph stellt einen Bipartiegraph da. Ich suche nun einen Algorihmus der feststellt ob es moeglich ist den Graph so aufzuteilen das jeder Subgraph aus genau N knoten besteht natuerlich soll der Graph bipartie bleiben. Gibt es so einen Algorihmus, der auch fuer sehr grosse N schnell genug ist?

Besten Dank

CStoll

Geht das auch etwas ausführlicher? Wenn dein Graph bipartit ist, gilt das natürlich auch für jeden Teilgraphen davon - das heißt den Grapen aufzuteilen ist trivial (einfach die Knoten in zwei Mengen verteilen und nur die Kanten innerhalb der jeweiligen Teilmenge verwenden).
Wenn du noch weitere Anforderungen an den Graphen hast, könnte es ein wenig aufwendiger werden.

Hallo,

sorry habe mich vielleicht missverstaendlich ausgedrueckt. Angenommen N=100 dann habe ich insgesamt 200 Knoten. Diese 200 Knoten stellen jetzt mit ensprechenden Kanten einen Bipartiten Graph da.

Jetst sind aber z.B. in der ersten Teilmenge 150 Knoten und in der anderen 50 Knoten. Jetzt suche ich einen Algorithmus der prueft ob es moeglich ist Knoten zwischen beiden Teilmengen auszutauschen so das am Ende beide Teilmengen je genu 100 Knoten besitzen(also N Knoten).

Gibt es sowas?

Besten Dank

volkard

Zuerstmal stelle ich mir einen zusammenhängenden bipariten Graphen vor:
Wenn ich mir einen beliebigen Knoten als Startknoten herausnehme und auf Westufer lege.
Und alle unklassifizierten Knoten, die damit verbunden sind aufs Ostufer.
Und dann alle unklassifizierten Knoten, die mit Ost-Knoten verbunden sind wieder aufs Westufer.
usw...

Werden dann nicht alle Knoten zwangsläufig auf West/Ost verteilt und zwar auf eindeutige Weise (bis auf daß man die Namen West und Ost vertauschen kann).

Wenn dem so wäre, wäre die Aufgabe so zu fassen:
Jede Zusammenhangskomponente einer Ost/West-Teilung unterziehen.
In jeder Zusammenhangskomponente kann Ost-West vertauscht werden.
Schauen, ob eine Vertauschungskombination besteht, wo alle Ost-Mengen zusammen 100 Elemente haben.

Das läßt sich zurückführne auf ein anderes Problem.
Ich nenne immer die größere Sete die West-Seite. Für jeder Zusammenhangskomponente notiere ich nur die Differenz zwischen Ost und West. Ziel ist dann eine Kombination von Differenzen zu finden, deren Summe genau "100 minus Summe der Ost-Teile" ist. Das wäre dann das http://en.wikipedia.org/wiki/Subset_sum_problem und ist gut diskutiert.

Michael E.

Man kann sich sogar auf Partition beschränken. Und da die Elemente des Partition-Problems durch die Zusammenhangskomponenten des Graphen gegeben sind, läuft ein pseudopolynomieller Algorithmus für Partition in polynomieller Zeit. Hier kannst du also einfach mit dynamischer Programmierung das Problem lösen.

Edit: Die Ost-West-Teilung der Zusammenhangskomponenten nennt sich Zweifärbung bzw. Tiefensuche.

Danke fuer die Informationen ich werde es mal probieren!