Im mathematischen Feld der Graph-Theorie ist ein zweiteiliger Graph (oder bigraph) ein Graph, dessen Scheitelpunkte in zwei zusammenhanglose Sätze U und V solch geteilt werden können, dass jeder Rand einen Scheitelpunkt in U zu einem in V verbindet; d. h. U und V sind unabhängige Sätze. Gleichwertig ist ein zweiteiliger Graph ein Graph, der keine Zyklen der sonderbaren Länge enthält.

Von den zwei Sätzen U und V kann als ein Färben des Graphen mit zwei Farben gedacht werden: Wenn man alle Knoten im U Blau, und alle Knoten in V Grün färbt, hat jeder Rand Endpunkte von sich unterscheidenden Farben, wie im Graph-Färben-Problem erforderlich ist. Im Gegensatz ist solch ein Färben im Fall von einem nichtzweiteiligen Graphen wie ein Dreieck unmöglich: Nachdem ein Knoten blau und ein anderes Grün gefärbt wird, wird der dritte Scheitelpunkt des Dreiecks mit Scheitelpunkten von beiden Farben verbunden, es davon abhaltend, jede Farbe zugeteilt zu werden.

Man schreibt häufig G = (U, V, E), um einen zweiteiligen Graphen anzuzeigen, dessen Teilung die Teile U und V hat. Wenn |U = |V, d. h. wenn die zwei Teilmengen gleichen cardinality haben, dann wird G einen erwogenen zweiteiligen Graphen genannt.

Beispiele

Zweiteilige Graphen tauchen in vielen Plätzen auf und sind deshalb häufig verwendetes Werkzeug, um zu modellieren und damit zu rechnen. Wenn sie Beziehungen zwischen zwei verschiedenen Klassen von Gegenständen modellieren, entstehen zweiteilige Graphen sehr häufig natürlich. Nehmen Sie einen Graphen von Footballspielern und Klubs, und lassen Sie dort, ein Rand zwischen einem Spieler und einem Klub zu sein, wenn der Spieler um diesen Klub gespielt hat. Das erweist sich, ein zweiteiliger Graph zu sein (es gibt keine Ränder zwischen Spielern und anderen Spielern, und Klubs und anderen Klubs). Außerdem wählt das maximale Zusammenbringen im Graphen den größten Satz von Paaren des Spielers/Klubs aus, wo kein Spieler und kein Klub zweimal erscheinen.

Ein anderes Beispiel, wo zweiteilige Graphen natürlich erscheinen, ist im Eisenbahnoptimierungsproblem, wo wir eine Reihe von Zügen, eine Reihe von Bahnstationen und einen Rand zwischen einem Zug und einer Station haben, wenn der Zug an der Station anhält. Das ist klar ein zweiteiliger Graph ebenso (aus demselben Grund wie oben). Das Eisenbahnoptimierungsproblem bittet, kleinsten Satz von Bahnstationen solch zu finden, dass jeder Zug einen von ihnen besucht. Dieses Problem ist NP-complete.

• Jeder Graph ohne sonderbare Zyklen ist zweiteilig. Demzufolge dessen:
• Jeder Baum ist zweiteilig.
• Zyklus-Graphen mit einer geraden Zahl von Scheitelpunkten sind zweiteilig.
• Jeder planare Graph, wo alle Gesichter in seiner planaren Darstellung aus einer geraden Zahl von Rändern bestehen, ist zweiteilig. Spezielle Fälle davon sind Bratrost-Graphen und squaregraphs, in dem jedes innere Gesicht aus 4 Rändern besteht.
• Der ganze zweiteilige Graph auf n und M Scheitelpunkte, die durch K angezeigt sind, ist der zweiteilige Graph G = (V, U, E), wo V und U zusammenhanglose Sätze der Größe n und M beziehungsweise sind, und E jeden Scheitelpunkt in V mit allen Scheitelpunkten in U verbindet. Hieraus folgt dass K nm Ränder hat.

Prüfung der Zweiteiligkeit

Da sich das Beispiel an der Oberseite von diesem Artikel zeigt, kann jeder zweiteilige Graph durch zwei solche Farben gefärbt werden, dass keine angrenzenden Scheitelpunkte dieselbe Farbe haben. Tatsächlich gibt das einen gierigen Algorithmus, um Zweiteiligkeit sofort zu prüfen. Picken Sie jeden Scheitelpunkt auf und teilen Sie ihn das Farbenrot zu. Dann gehen Sie weiter, indem Sie alle seine blauen Nachbarn färben. Für jeden farbigen Scheitelpunkt, färben Sie seinen ganzen Nachbar mit der entgegengesetzten Farbe. Wenn es irgendwelche Kollisionen gibt, bedeutend, dass wir einen Scheitelpunkt mit einer verschiedenen Farbe färben wollen, als es hat, brechen wir ab und beschließen, dass der Graph nicht zweifarbig sein kann und folglich es nicht zweiteilig ist (es muss einen sonderbaren Zyklus enthalten).

Wenn ein zweiteiliger Graph verbunden wird, kann sein bipartition durch die Gleichheit der Entfernungen von jedem willkürlich gewählten Scheitelpunkt v definiert werden: Eine Teilmenge besteht aus den Scheitelpunkten in sogar der Entfernung zu v, und die andere Teilmenge besteht aus den Scheitelpunkten in der sonderbaren Entfernung zu v.

So kann man effizient prüfen, ob ein Graph durch das Verwenden dieser Paritätstechnik zweiteilig ist, um Scheitelpunkte den zwei Teilmengen U und V, getrennt innerhalb jedes verbundenen Bestandteils des Graphen zuzuteilen, und dann jeden Rand zu untersuchen, um nachzuprüfen, dass es Endpunkte verschiedenen Teilmengen zuteilen ließ.

Sonderbarer Zyklus Transversal

Odd Cycle Transversal (OCT) ist ein algorithmisches Problem, das, in Anbetracht eines Graphen G = (V, E) und eine Nummer k fragt, können Sie, k Scheitelpunkte von solchem G entfernen, dass der resultierende Graph zweiteilig ist. Das ist ein berühmtes NP-complete Problem (bewiesener NP-complete durch Mihalis Yannakakis 1978). Es war eine seit langer Zeit bestehende geöffnete Frage, ob dieses Problem lenksamer fester Parameter war, der 2004 von Reed, Smith und Vetta gelöst wurde, der 4kmn Algorithmus gegeben hat, um OKT zu lösen; für einen festen k gibt es einen polynomischen Zeitalgorithmus, der herausfindet, ob ein Graph einen OKT der Größe am grössten Teil von k hat.

Anwendungen

Zweiteilige Graphen sind nützlich, um das Zusammenbringen von Problemen zu modellieren. Ein Beispiel des zweiteiligen Graphen ist ein Job, der Problem vergleicht. Nehmen Sie an, dass wir einen Satz P Leute und eines Satzes J Jobs mit nicht alle für alle Jobs passenden Leute haben. Wir können das als ein zweiteiliger Graph (P, J, E) modellieren. Wenn eine Person p für einen bestimmten Job j passend ist, gibt es einen Rand zwischen p und j im Graphen. Der Ehe-Lehrsatz stellt eine Charakterisierung von zweiteiligen Graphen zur Verfügung, die vollkommenen matchings erlauben.

Zweiteilige Graphen werden in der modernen Codiertheorie umfassend verwendet, um besonders vom Kanal erhaltene Kennwörter zu decodieren. Faktor-Graphen und Gerber-Graphen sind Beispiele davon.

In der Informatik ist ein Netz von Petri ein mathematisches modellierendes Werkzeug, das in der Analyse und den Simulationen von gleichzeitigen Systemen verwendet ist. Ein System wird als ein zweiteiliger geleiteter Graph mit zwei Sätzen von Knoten modelliert: Eine Reihe von "Platz"-Knoten, die Mittel und eine Reihe von "Ereignis"-Knoten enthalten, die erzeugen und/oder Mittel verbrauchen. Es gibt zusätzliche Einschränkungen auf die Knoten und Ränder, die das Verhalten des Systems beschränken. Netze von Petri verwerten die Eigenschaften von zweiteiligen geleiteten Graphen und anderen Eigenschaften, mathematische Beweise des Verhaltens von Systemen zu erlauben, während sie auch leichte Durchführung von Simulationen des Systems erlauben.

In der projektiven Geometrie sind Graphen von Levi eine Form des zweiteiligen Graphen, der verwendet ist, um die Vorkommen zwischen Punkten und Linien in einer Konfiguration zu modellieren.

Das Modellieren von Mehrgraphen und Hypergraphen

Zweiteilige Graphen können den allgemeineren Mehrgraphen modellieren. In Anbetracht eines Mehrgraphen M, nehmen Sie U als der Scheitelpunkt-Satz der M und nehmen Sie V als der Rand-Satz der M. Dann schließen Sie sich einem Element V zu genau den zwei Elementen von U an, die die Enden dieses Randes in der M sind. So wird jeder Mehrgraph völlig durch einen zweiteiligen Graphen beschrieben, der einseitiger Stammkunde des Grads 2, und umgekehrt ist.

Ähnlich kann jeder geleitete Hypergraph als ein zweiteiliger Digraph vertreten werden. Nehmen Sie U als der Scheitelpunkt-Satz im Hypergraphen, und V als Satz von Rändern. Für jeden und, verbinden Sie u mit v, wenn der Hypergraph-Rand v u als ein Eingang enthält, und verbinden Sie v mit u, wenn v u als eine Produktion enthält.

Eigenschaften

• Ein Graph ist zweiteilig, wenn, und nur wenn er keinen sonderbaren Zyklus enthält. Deshalb kann ein zweiteiliger Graph keine Clique der Größe 3 oder mehr enthalten.
• Ein Graph ist zweiteilig, wenn, und nur wenn es 2-angeblich ist, (d. h. seine chromatische Zahl ist weniger als oder gleich 2).
• Die Größe des minimalen Scheitelpunkt-Deckels ist der Größe des Maximums gleich, das (der Lehrsatz von König) zusammenpasst.
• Die Größe des maximalen unabhängigen Satzes plus die Größe des Maximums, das zusammenpasst, ist der Zahl von Scheitelpunkten gleich.
• Für einen verbundenen zweiteiligen Graphen ist die Größe des minimalen Rand-Deckels der Größe des maximalen unabhängigen Satzes gleich.
• Für einen verbundenen zweiteiligen Graphen ist die Größe des minimalen Rand-Deckels plus die Größe des minimalen Scheitelpunkt-Deckels der Zahl von Scheitelpunkten gleich.
• Jeder zweiteilige Graph ist ein vollkommener Graph.
• Das Spektrum eines Graphen ist symmetrisch, wenn, und nur wenn es ein zweiteiliger Graph ist.

Siehe auch

• Vollenden Sie zweiteiligen Graphen
• Zergliederung von Dulmage-Mendelsohn
• Angrenzen-Matrix eines zweiteiligen Graphen
• Rekordverbindung

Außenverbindungen

• Informationssystem auf Graph-Klasseneinschließungen: zweiteiliger Graph