Bipartitale Grafik

Beispiel für ein zweipartneres Diagramm ohne Zyklen
A Komplette zweigliedrige Grafik mit m = 5 und n = 3

In dem mathematisch Bereich Graphentheorie, a Bipartitale Grafik (oder Bigraph) ist ein Graph Deren Eckpunkte kann in zwei unterteilt werden disjunkt und unabhängige Sets und , das ist jeder Kante verbindet a Scheitel in zu einem in . Scheitelpunktsätze und werden normalerweise die genannt Teile der Grafik. Äquivalent ist ein zweipartneres Diagramm ein Diagramm, das keine ungerade Länge enthält Fahrräder.[1][2]

Die beiden Sätze und kann als als betrachtet werden Färbung des Diagramms mit zwei Farben: Wenn man alle Knoten in farben blau und alle Knoten in Grün, jede Kante hat Endpunkte unterschiedlicher Farben, wie im Diagramm -Färbungsproblem erforderlich ist.[3][4] Im Gegensatz dazu ist eine solche Färbung im Falle eines nicht-grafischen Diagramms wie a unmöglich Dreieck: Nachdem ein Knoten blau und ein anderes Grün gefärbt ist, ist der dritte Scheitelpunkt des Dreiecks mit Scheitelpunkten beider Farben verbunden, was verhindert, dass es einer der beiden Farbe zugewiesen wird.

Man schreibt oft zu bezeichnen, eine zweigliedrige Grafik, deren Partition die Teile hat und , mit Kennzeichnung der Kanten des Diagramms. Wenn ein zweigliedriger Diagramm nicht ist in Verbindung gebrachtMöglicherweise haben es mehr als eine Bipartition;[5] In diesem Fall die Notation ist hilfreich bei der Angabe einer bestimmten Bipartition, die in einer Anwendung von Bedeutung sein kann. Wenn Das heißt, wenn die beiden Teilmengen gleich sind Kardinalität, dann wird als a genannt ausgewogen Bipartitale Grafik.[3] Wenn alle Scheitel Grad, dann wird genannt biregular.

Beispiele

Beim Modellieren Beziehungen Zwischen zwei verschiedenen Klassen von Objekten ergeben sich sehr häufig zweiteilige Diagramme auf natürliche Weise. Zum Beispiel ist eine Grafik von Fußballspielern und Clubs mit einem Vorsprung zwischen einem Spieler und einem Verein, wenn der Spieler für diesen Verein gespielt hat, ein natürliches Beispiel für eine Zugehörigkeitsnetzwerk, eine Art von zweiteiliger Graphen, die in verwendet wird Analyse des sozialen Netzwerks.[6]

Ein weiteres Beispiel, in dem zweipartnere Graphen natürlich erscheinen, ist in der (NP-Complete) Das Problem der Eisenbahnoptimierung, bei dem der Eingang ein Züge und ihre Stopps ist, und das Ziel ist es, eine Reihe von Bahnhöfen so klein wie möglich zu finden, so dass jeder Zug mindestens eine der ausgewählten Stationen besucht. Dieses Problem kann als modelliert werden dominierender Satz Problem in einem zweigliedrigen Diagramm mit einem Scheitelpunkt für jeden Zug und jeden Bahnhofs und einer Kante für jedes Paar eines Bahnhofs und einen Zug, der an diesem Bahnhof hält.[7]

Ein drittes Beispiel ist im akademischen Bereich der Numismatik. Alte Münzen werden unter Verwendung von zwei positiven Eindrücken des Designs (der Vorderseite und der Rückseite) gemacht. Die Diagramme Numismatiker produzieren, um die Produktion von Münzen darzustellen.[8]

Weitere abstrakte Beispiele sind die folgenden:

  • Jeder Baum ist zweigliedrig.[4]
  • Zyklusgraphen Mit einer geraden Anzahl von Scheitelpunkten sind zweigliedern.[4]
  • Jeder Planare Graph Deren Gesichter Alle haben sogar Länge überparteilich.[9] Besondere Fälle davon sind Grid -Diagramme und Quadratgraphen, in dem jedes innere Gesicht aus 4 Kanten besteht und jeder innere Scheitelpunkt vier oder mehr Nachbarn hat.[10]
  • Das Komplette zweigliedrige Grafik an m und n Scheitelpunkte, gekennzeichnet durch Kn, m ist das zweigliedrige Diagramm , wo U und V sind disjunkt Größensätze m und njeweils und E verbindet jeden Scheitelpunkt in U mit allen Scheitelpunkten in V. Es folgt dem Km, n hat mn Kanten.[11] Eng verwandte mit den vollständigen zweigliedrigen Grafiken sind die Kronengrafiken, gebildet aus kompletten zweiparteilen Graphen durch Entfernen der Kanten von a Perfektes Matching.[12]
  • Hypercube -Diagramme, Teilwürfel, und Mediangrafiken sind zweigliedrig. In diesen Grafiken können die Eckpunkte von gekennzeichnet werden Bitvektorenso, dass zwei Scheitelpunkte nur dann benachbart sind, wenn sich die entsprechenden Bitvektoren in einer einzelnen Position unterscheiden. Eine zweistaatliche Unterbrechung kann gebildet werden, indem die Eckpunkte getrennt werden, deren Bitvektoren eine gleichmäßige Anzahl von Eckpunkten mit einer ungeraden Anzahl von Einsen haben. Bäume und Quadratgraphen bilden Beispiele für mediane Graphen, und jeder Median -Diagramm ist ein Teilwürfel.[13]

Eigenschaften

Charakterisierung

Bipartite Diagramme können auf verschiedene Arten charakterisiert werden:

  • Ein Diagramm ist zweipartner dann und nur dann, wenn es enthält keine ungerade Zyklus.[14]
  • Ein Diagramm ist zweipartner, wenn es nur 2-körperler ist (d. H. SEIN Chromatische Zahl ist weniger als oder gleich 2).[3]
  • Ein Diagramm ist nur dann zweigliedrig, wenn jede Kante einer ungeraden Anzahl von gehört Fesseln, minimale Teilmengen von Kanten, deren Entfernung die Anzahl der Komponenten des Diagramms erhöht.[15]
  • Ein Diagramm ist nur dann überparteilich, wenn die Spektrum der Grafik ist symmetrisch.[16]

Kőnigs Theorem und perfekte Grafiken

In zweiparteilen Grafiken die Größe von Mindestabdeckung von Scheitelpunkten ist gleich der Größe der Maximale Matching; das ist Kőnig's Theorem.[17][18] Eine alternative und äquivalente Form dieses Satzes ist, dass die Größe der Größe der Maximal unabhängiger Satz plus die Größe der maximalen Übereinstimmung entspricht der Anzahl der Scheitelpunkte. In jeder Grafik ohne isolierte Eckpunkte Die grosse von Mindestkantenabdeckung plus die Größe einer maximalen Übereinstimmung entspricht der Anzahl der Scheitelpunkte.[19] Die Kombination dieser Gleichheit mit Kőnigs Theorem führt zu den Fakten, dass in zweiparteilen Graphen die Größe der minimalen Kantenabdeckung gleich der Größe des maximalen unabhängigen Satz ist gleich der Anzahl der Eckpunkte.

Eine weitere Klasse verwandter Ergebnisse betrifft Perfekte Grafiken: Jedes zweigliedrige Diagramm, die ergänzen von jeder zweigliedrigen Grafik die Liniendiagramm Von jedem zweigliedrigen Diagramm und der Ergänzung der Liniengrafik jeder zweigliedrigen Grafik sind alle perfekt. Die Perfektion von zweiparteilen Graphen ist leicht zu sehen (ihre Chromatische Zahl ist zwei und ihre Maximale Clique Größe ist auch zwei), aber Perfektion der Ergänzungen von zweiparteilen Graphen ist weniger trivial und eine weitere Wiederholung des Theorems von Kőnig. Dies war eines der Ergebnisse, die die anfängliche Definition perfekter Grafiken motivierten.[20] Die Perfektion der Komplemente von Liniengraphen perfekter Graphen ist eine weitere Wiederholung von Kőnigs Theorem, und die Perfektion der Liniengraphen selbst ist eine Wiederholung eines früheren Theorems von Kőnig, dass jede zweistartitische Grafik eine hat Kantenfarbe Verwenden einer Anzahl von Farben entspricht maximaler Grad.

Laut dem starker perfekter DiagrammsatzDie perfekten Grafiken haben eine Verbotene Diagrammcharakterisierung Ähnlich der von zweiparteilen Graphen: Ein Diagramm ist zweipartner, wenn es nur dann keinen ungeraden Zyklus als Untergraphen hat, und ein Diagramm ist perfekt, wenn es nur dann ist, wenn es keinen ungeraden Zyklus hat oder sein ergänzen als an induzierter Untergraph. Die zweipartnerischen Grafiken, Liniengraphen der zweigliedrigen Graphen und deren Ergänzungen bilden vier der fünf grundlegenden Klassen perfekter Grafiken, die im Beweis des starken perfekten Graph -Theorems verwendet werden.[21]

Grad

Für einen Scheitelpunkt wird die Anzahl der benachbarten Scheitelpunkte als die genannt Grad des Scheitelpunkts und wird bezeichnet . Das Abschlusssumme Für eine zweigliedrige Grafik gibt an[22]

Die Gradsequenz eines zweiteiligen Diagramms ist das Paar von Listen, die jeweils die Grad der beiden Teile enthalten und . Zum Beispiel die vollständige zweipartnerische Grafik K3,5 hat Gradsequenz . Isomorphe zweipartitliche Diagramme haben die gleiche Gradsequenz. Die Gradsequenz identifiziert jedoch im Allgemeinen nicht eindeutig ein zweipartneres Diagramm. In einigen Fällen können nicht isomorphe zweipartitische Diagramme die gleiche Gradsequenz aufweisen.

Das Bippartitiner Realisierungsproblem ist das Problem, ein einfaches zweipartneres Diagramm zu finden, wobei die Gradsequenz zwei angegebene Listen natürlicher Zahlen ist. (Nachfolgende Nullen können ignoriert werden, da sie durch Hinzufügen einer geeigneten Anzahl isolierter Eckpunkte zum Digraph trivial realisiert werden.)

Beziehung zu Hypergraphen und gerichteten Graphen

Das BiadjaCacy -Matrix einer zweigliedrigen Grafik ist ein (0,1) Matrix von Größe Das hat eine für jedes Paar benachbarte Scheitelpunkte und eine Null für nicht adjaziente Eckpunkte.[23] Biadjazenzmatrizen können verwendet werden, um Äquivalenzen zwischen zweiparteilen Graphen, Hypergraphen und gerichteten Graphen zu beschreiben.

A Hypergraph ist eine kombinatorische Struktur, die wie ein ungerichteter Diagramm Scheitelpunkte und Kanten enthält, in dem jedoch die Kanten willkürliche Scheitelpunkte sein können, anstatt genau zwei Endpunkte zu haben. Eine zweipartnere Grafik kann verwendet werden, um einen Hypergraph zu modellieren, in dem U ist der Satz von Scheitelpunkten des Hypergraphen, V ist der Satz von Hyperedges und E Enthält eine Kante aus einem Hypergraph -Scheitelpunkt v zu einer Hypergraphenkante e Genau wann v ist einer der Endpunkte von e. Unter dieser Korrespondenz sind die Biadjazenzmatrizen der zweigliedrigen Graphen genau die Inzidenzmatrizen der entsprechenden Hypergraphen. Als Sonderfall dieser Korrespondenz zwischen zweiparteilen Graphen und Hypergraphen alle beliebig Multigraph (Ein Diagramm, in dem es zwei oder mehr Kanten zwischen denselben zwei Scheitelpunkten geben kann) kann als Hypergraphen interpretiert werden Scheitelpunkte auf einer Seite der Bipartition haben alle Grad zwei.[24]

Eine ähnliche Neuinterpretation von Adjazenzmatrizen kann verwendet werden, um eine Eins-zu-Eins-Korrespondenz zwischen zu zeigen Regie Graphen (Auf einer bestimmten Anzahl von beschrifteten Eckpunkten, die Selbstschleifen ermöglichen) und ausgewogene zweigliedrige Diagramme mit der gleichen Anzahl von Scheitelpunkten auf beiden Seiten der Bipartition. Denn die Adjazenzmatrix eines gerichteten Diagramms mit n Scheitelpunkte können jeder sein (0,1) Matrix von Größe , was dann als Adjazenzmatrix eines zweigliedern n Scheitelpunkte auf jeder Seite seiner Bipartition.[25] In dieser Konstruktion ist die zweigliedrige Grafik die Grafik Bippartize doppelte Abdeckung der gerichteten Grafik.

Algorithmen

Prüfung testen

Es ist möglich zu testen, ob ein Diagramm überparteilich ist, und entweder einen zweifarbigen (falls es sich um zweisteilige) oder einen ungeraden Zyklus (falls nicht) in lineare Zeit, verwenden Tiefe-First-Suche. Die Hauptidee besteht darin, jedem Scheitelpunkt die Farbe zuzuweisen, die sich von der Farbe seiner Eltern im Tiefen-ersten Suchwald unterscheidet und Farben in einem zuweist Vorbestellung durchquert des Tiefenwaldes. Dies wird notwendigerweise einen zweifarbigen von der liefern Spannungswald bestehend aus den Kanten, die Scheitelpunkte mit ihren Eltern verbinden, aber es kann einige der Nichtwaldkanten nicht richtig färben. In einem Tiefenwald ist einer der beiden Endpunkte aller Nichtwaldkanten ein Vorfahr des anderen Endpunkts, und wenn die Tiefensuche eine Kante dieses Typs entdeckt, sollte dies überprüfen, ob diese beiden Scheitelpunkte unterschiedliche Farben haben. Wenn dies nicht der Fall ist, bildet der Weg im Wald vom Vorfahren zum Nachkommen zusammen mit der misslassten Kante einen seltsamen Zyklus, der zusammen mit dem Ergebnis, dass der Diagramm nicht bipartit ist, aus dem Algorithmus zurückgegeben wird. Wenn der Algorithmus jedoch endet, ohne einen ungeraden Zyklus dieses Typs zu erkennen, muss jede Kante ordnungsgemäß gefärbt sein und der Algorithmus die Färbung zusammen mit dem Ergebnis zurückgibt, dass der Diagramm zweistartig ist.[26]

Alternativ kann ein ähnliches Verfahren mit verwendet werden Breite-First-Suche Anstelle der Tiefe-First-Suche. Auch hier erhält jeder Knoten der entgegengesetzten Farbe für seine Eltern im Suchwald in Breite zuerst. Wenn, wenn ein Scheitelpunkt gefärbt ist, gibt es eine Kante, die ihn mit einem zuvor gefärbten Scheitelpunkt mit derselben Farbe verbindet, diese Kante zusammen mit den Pfaden im Breiten-First-Suchwald, der seine beiden Endpunkte mit ihren Endpunkten verbindet Niedrigster gemeinsamer Vorfahr bildet einen seltsamen Zyklus. Wenn der Algorithmus endet, ohne auf diese Weise einen merkwürdigen Zyklus zu finden, muss er eine ordnungsgemäße Färbung gefunden haben und kann sicher zu dem Schluss kommen, dass das Diagramm überparteilich ist.[27]

Für die Kreuzungsdiagramme von Liniensegmente oder andere einfache Formen in der Euklidische EbeneEs ist möglich zu testen, ob das Diagramm zweigliedrig ist und entweder einen zweifarbigen oder einen ungeraden Zyklus in der Zeit zurückgibt , obwohl die Grafik selbst möglicherweise bis zu Kanten.[28]

Odd Cycle Transversal

Hauptartikel: Odd Cycle Transversal
Ein Diagramm mit einem ungeraden Zyklus -Transversal der Größe 2: Das Entfernen der zwei blauen Scheitelpunkte hinterlässt ein zweigliedriges Diagramm.

Odd Cycle Transversal ist ein NP-Complete Algorithmisch Problem, das nach einer Grafik fragt, G = (V,E) und eine Nummer k, ob es einen Satz von gibtk Scheitelpunkte, deren Entfernung von G würde dazu führen, dass das resultierende Diagramm überparteilich ist.[29] Das Problem ist Fix-Parameter-TraktableDies bedeutet, dass es einen Algorithmus gibt, dessen Laufzeit durch eine Polynomfunktion der Größe des Diagramms mit einer größeren Funktion von multipliziert werden kann k.[30] Der Name Odd Cycle Transversal Kommt aus der Tatsache, dass ein Diagramm nur dann überparteilich ist, wenn es keine Unklar gibt Fahrräder. Um Scheitelpunkte aus einem Diagramm zu löschen, um ein zweipartneres Diagramm zu erhalten Transversal einstellen. In der Abbildung enthält jeder merkwürdige Zyklus im Diagramm die blauen (die Bottommost-) Scheitelpunkte, sodass das Entfernen dieser Eckpunkte alle seltsamen Zyklen abtötet und ein zweipartneres Diagramm hinterlässt.

Das Edge Bipartisierung Das Problem ist das algorithmische Problem beim Löschen von möglichst wenigen Kanten wie möglich, um ein Diagramm -Bipartiten zu erstellen, und ist auch ein wichtiges Problem in der Diagrammveränderungsalgorithmic. Dieses Problem ist auch Fix-Parameter-Traktableund kann rechtzeitig gelöst werden ,[31] wo k ist die Anzahl der Kanten zum Löschen und m ist die Anzahl der Kanten in der Eingangsgrafik.

Matching

Hauptartikel: Matching (Graphentheorie)

A Matching In einem Diagramm befindet sich eine Teilmenge seiner Kanten, von denen keine zwei einen Endpunkt teilen. Polynomzeit Algorithmen sind für viele algorithmische Probleme bei Matchings bekannt, einschließlich Maximale Matching (Finden einer Übereinstimmung, die so viele Kanten wie möglich verwendet), maximales Gewichtsanpassung, und stabile Ehe.[32] In vielen Fällen sind Matching-Probleme einfacher, in zweigliedrigen Grafiken zu lösen als in nicht bipartiten Graphen.[33] und viele passende Algorithmen wie die Hopcroft -Karp -Algorithmus Für maximale Kardinalitätsanpassung[34] Arbeiten Sie nur an zweiparteilen Eingängen korrekt.

Nehmen wir als einfaches Beispiel an, dass ein Satz von Menschen suchen alle nach Jobs aus einer Reihe von Jobs, mit nicht allen Menschen, die für alle Jobs geeignet sind. Diese Situation kann als zweipartneres Diagramm modelliert werden Wenn eine Kante jeden Arbeitssuchenden mit jedem geeigneten Job verbindet.[35] A Perfektes Matching beschreibt einen Weg, alle Arbeitssuchenden gleichzeitig zu befriedigen und alle Jobs zu füllen; Halls Heiratssatz Bietet eine Charakterisierung der zweigliedrigen Graphen, die perfekte Übereinstimmungen ermöglichen. Das National Resident Matching -Programm Wendet Grafikanpassungsmethoden an, um dieses Problem für zu lösen US -Medizinstudent Arbeitssuchende und Krankenhausaufenthalt Arbeitsplätze.[36]

Das Dulmage -Mendelsohn -Zersetzung ist eine strukturelle Zersetzung von zweiparteilen Graphen, die für die Suche nach maximalen Übereinstimmungen nützlich sind.[37]

Zusätzliche Anwendungen

Bipartite Diagramme werden in der Moderne ausgiebig eingesetzt Codierungstheorie, besonders um zu dekodieren Codewörter vom Kanal erhalten. Faktorgrafiken und Tannergrafiken sind Beispiele dafür. Ein Tanner -Diagramm ist ein zweipartneres Diagramm, in dem die Scheitelpunkte auf einer Seite der Bipartition Ziffern eines Codeworts darstellen, und die Scheitelpunkte auf der anderen Seite darstellen Kombinationen von Ziffern, von denen erwartet wird, dass sie in einem Codewort ohne Fehler auf Null summieren.[38] Eine Faktorgrafik ist eng verwandt Glaubensnetzwerk verwendet zur probabilistischen Dekodierung von LDPC und Turbocodes.[39]

In Informatik, a Petrischetz ist ein mathematisches Modellierungsinstrument, das in der Analyse und Simulationen gleichzeitiger Systeme verwendet wird. Ein System wird als partitisches Diagramm mit zwei Sätzen von Knoten modelliert: eine Reihe von "Platzieren" -Knoten, die Ressourcen enthalten, und eine Reihe von "Ereigniskommschneidern", die Ressourcen generieren und/oder konsumieren. Es gibt zusätzliche Einschränkungen für die Knoten und Kanten, die das Verhalten des Systems einschränken. Petri Nets verwenden die Eigenschaften von zweiparteilen gerichteten Diagrammen und anderen Eigenschaften, um mathematische Beweise für das Verhalten von Systemen zu ermöglichen und gleichzeitig eine einfache Implementierung von Simulationen des Systems zu ermöglichen.[40]

Im projektive Geometrie, Levi -Grafiken sind eine Form von zweiparteilen Graphen, die zur Modellierung der Vorfälle zwischen Punkten und Linien in a verwendet werden Aufbau. Entsprechend der geometrischen Eigenschaft von Punkten und Linien, die alle zwei Zeilen in höchstens einem Punkt treffen und alle zwei Punkte mit einer einzigen Linie verbunden sind, enthalten Levi -Diagramme notwendigerweise keine Zyklen mit vier Längen, sodass ihre so ihre Länge enthält, also ihre. Umfang Muss sechs oder mehr sein.[41]

Siehe auch

  • Bipartitale Dimension, die Mindestanzahl vollständig zweipartnerer Graphen, deren Vereinigung die angegebene Grafik ist
  • Bipartite double cover, eine Möglichkeit, ein Diagramm in ein zweigliedriges Diagramm zu verwandeln, indem es seine Scheitelpunkte verdoppelt
  • Bippartizer Hypergraph, eine Verallgemeinerung von zweierer Kenntnis Hypergraphen.
  • Bippartize Matroid, eine Klasse von Matroiden, die die enthält Grafikmatroide von zweiparteilen Graphen
  • Bipartite Netzwerkprojektion, eine Gewichtungstechnik zum Komprimieren von Informationen über zweigliedrige Netzwerke
  • Konvexe zweigliedrige Grafik, ein zweipartneres Diagramm, dessen Eckpunkte so bestellt werden können
  • Mehrteilige Grafik, eine Verallgemeinerung von zweiparteilen Graphen auf mehr als zwei Teilmengen von Scheitelpunkten
  • Paritätsgrafik, eine Verallgemeinerung von zweiparteilen Graphen, in denen alle zwei induzierte Pfade Zwischen den gleichen zwei Punkten haben die gleiche Parität
  • Quasi-bipartitale Grafik, eine Art von Steiner -Baumprobleminstanz, in der die Terminals einen unabhängigen Satz bilden
  • Split Graph, ein Diagramm, in dem die Scheitelpunkte in zwei Teilmengen aufgeteilt werden können, von denen einer unabhängig ist und der andere eine Clique ist
  • Zarankiewicz Problem an der maximalen Anzahl von Kanten in einem zweigliedrigen Diagramm mit verbotenen Untergraphen

Verweise

  1. ^ Diestel, Reinard (2005), Graphentheorie, Graduiertentexte in Mathematik, Springer, ISBN 978-3-642-14278-9
  2. ^ Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland (1998), Bipartite Diagramme und deren Anwendungen, Cambridge Tracts in Mathematics, Vol. 131, Cambridge University Press, ISBN 9780521593458.
  3. ^ a b c Asratian, Denley & Häggkvist (1998), p. 7.
  4. ^ a b c Scheinerman, Edward R. (2012), Mathematik: Eine diskrete Einführung (3. Aufl.), Cengage Learning, p. 363, ISBN 9780840049421.
  5. ^ Chartrand, Gary; Zhang, Ping (2008), Chromatische Graphentheorie, Diskrete Mathematik und ihre Anwendungen, Vol. 53, CRC Press, p. 223, ISBN 9781584888000.
  6. ^ Wasserman, Stanley; Faust, Katherine (1994), Analyse des sozialen Netzwerks: Methoden und Anwendungen, Strukturanalyse in den Social Sciences, Vol. 8, Cambridge University Press, S. 299–302, ISBN 9780521387071.
  7. ^ Niedermeier, Rolf (2006), Einladung zu festen Parameteralgorithmen, Oxford Lecture Series in Mathematics und ihre Anwendungen, Oxford University Press, S. 20–21, ISBN 978-0-19-856607-6
  8. ^ Bracey, Robert (2012), "Über die grafische Interpretation von Herodes Münzen der 3 Jahre", in Jacobson, David M.; Kokkinos, Nikos (Hrsg.), Judäa und Rom in Münzen 65 v. Chr. - 135 n., Spink & Sohn, S. 65–84
  9. ^ Soifer, Alexander (2008), Das mathematische Malbuchbuch, Springer-Verlag, S. 136–137, ISBN 978-0-387-74640-1. Dieses Ergebnis wurde manchmal als "zwei Farbstheorem" bezeichnet. Soifer schreibt es einem berühmten Papier von 1879 von 1879 zu Alfred Kempe mit einem falschen Beweis des Vier Farbsatz.
  10. ^ Bandelt, H.-J.; Chepoi, V.; Eppstein, D. (2010), "Kombinatorik und Geometrie endlicher und unendlicher Quadratgraphen", Siam Journal über diskrete Mathematik, 24 (4): 1399–1440, Arxiv:0905.4537, doi:10.1137/090760301, S2CID 10788524.
  11. ^ Asratian, Denley & Häggkvist (1998), p. 11.
  12. ^ Erzdiakon, D.; Debowsky, M.; Dinitz, J.; Gavlas, H. (2004), "Zyklussysteme im vollständigen zweigliedrigen Diagramm abzüglich eines Ein-Faktors", Diskrete Mathematik, 284 (1–3): 37–43, doi:10.1016/j.disc.2003.11.021.
  13. ^ Ovchinnikov, Sergei (2011), Grafiken und Würfel, Universitechse, Springer. Siehe insbesondere Kapitel 5, "Teilwürfel", S. 127–181.
  14. ^ Asratian, Denley & Häggkvist (1998), Satz 2.1.3, p. 8. Asratian et al. Diese Charakterisierung einer Arbeit von 1916 von 1916 von zuschreiben Dénes kőnig. Für unendliche Graphen erfordert dieses Ergebnis das Axiom der Wahl.
  15. ^ Woodall, D. R. (1990), "Ein Beweis von McKees eulerisch-bipartiten Charakterisierung", Diskrete Mathematik, 84 (2): 217–220, doi:10.1016/0012-365X (90) 90380-Z, HERR 1071664
  16. ^ Biggs, Norman (1994), Algebraische Graphentheorie, Cambridge Mathematical Library (2. Aufl.), Cambridge University Press, p. 53, ISBN 9780521458979.
  17. ^ Kőnig, Dénes (1931), "Gráfok és Mátrixok", Matematikai és Fizikai Lapok, 38: 116–119.
  18. ^ Gross, Jonathan L.; Yellen, Jay (2005), Graphentheorie und ihre Anwendungen, Diskrete Mathematik und ihre Anwendungen (2. Aufl.), CRC Press, p. 568, ISBN 9781584885054.
  19. ^ Chartrand, Gary; Zhang, Ping (2012), Ein erster Kurs in der Graphentheorie, Courier Dover Publications, S. 189–190, ISBN 9780486483689.
  20. ^ Béla Bollobás (1998),, Moderne Graphentheorie, Graduiertentexte in Mathematics, Vol. 184, Springer, p. 165, ISBN 9780387984889.
  21. ^ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The Starke Perfect Graph Theorem", Annalen der Mathematik, 164 (1): 51–229, Arxiv:Math/0212070, Citeseerx 10.1.1.111.7265, doi:10.4007/Annals.2006.164.51, S2CID 119151552.
  22. ^ Lovász, László (2014), Kombinatorische Probleme und Übungen (2. Aufl.), Elsevier, p. 281, ISBN 9780080933092
  23. ^ Asratian, Denley & Häggkvist (1998), p. 17.
  24. ^ A. A. Sapozhenko (2001) [1994], "Hypergraph", Enzyklopädie der Mathematik, EMS Press
  25. ^ Bructdi, Richard A.; Harary, Frank; Miller, Zevi (1980), "Bigraphs gegen Digraphen über Matrizen", Zeitschrift für Graphentheorie, 4 (1): 51–73, doi:10.1002/jgt.3190040107, HERR 0558453. Brualdi et al. Gutschrift die Idee für diese Äquivalenz zu Dulmage, A. L.; Mendelsohn, N. S. (1958), "Bedeckungen von zweigliedrigen Grafiken", Canadian Journal of Mathematics, 10: 517–534, doi:10.4153/CJM-1958-052-0, HERR 0097069.
  26. ^ Sedgewick, Robert (2004), Algorithmen in Java, Teil 5: Graph -Algorithmen (3. Aufl.), Addison Wesley, S. 109–111.
  27. ^ Kleinberg, Jon; TARDOS, ÉVA (2006), Algorithmus Design, Addison Wesley, S. 94–97.
  28. ^ Eppstein, David (2009), "Testen der zweiteiligen geometrischen Kreuzungsgrafiken", ACM -Transaktionen auf Algorithmen, 5 (2): Kunst. fünfzehn, Arxiv:CS.CG/0307023, doi:10.1145/1497290.1497291, HERR 2561751, S2CID 60496.
  29. ^ Yannakakis, Mihalis (1978), "Node-and Edge-Deletion NP-Complete-Probleme", Verfahren des 10. ACM -Symposiums über die Computertheorie (STOC '78), S. 253–264, doi:10.1145/800133.804355, S2CID 363248
  30. ^ Reed, Bruce; Smith, Kaleigh; Vetta, Adrian (2004), "Finden von Odd Cycle Transvers", Operations Forschungsbriefe, 32 (4): 299–301, Citeseerx 10.1.1.112.6357, doi:10.1016/j.orl.2003.10.009, HERR 2057781.
  31. ^ Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian (2006), "Kompressionsbasierte Festparameter-Algorithmen für den Rückkopplungsscheiben-Set und die Edge-Bipartisierung", Journal of Computer and System Sciences, 72 (8): 1386–1396, doi:10.1016/j.jcss.2006.02.001
  32. ^ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), "12. Aufgaben und Matchings", Netzwerkströme: Theorie, Algorithmen und Anwendungen, Prentice Hall, S. 461–509.
  33. ^ Ahuja, Magnanti & Orlin (1993), p. 463: "Nicht übereinsteitige Matching -Probleme sind schwieriger zu lösen, da sie nicht auf Standard -Netzwerkflussprobleme reduzieren."
  34. ^ Hopcroft, John E.; Karp, Richard M. (1973), "und n5/2 Algorithmus für maximale Übereinstimmungen in zweigliedrigen Graphen ", Siam Journal über Computing, 2 (4): 225–231, doi:10.1137/0202019.
  35. ^ Ahuja, Magnanti & Orlin (1993), Anwendung 12.1 Bipartite Personalzuordnung, S. 463–464.
  36. ^ Robinson, Sara (April 2003), "Treffen Medizinstudenten ihre (bestmögliche) Spiele?" (PDF), Siam News (3): 36, archiviert von das Original (PDF) Am 2016-11-18, abgerufen 2012-08-27.
  37. ^ Dulmage & Mendelsohn (1958).
  38. ^ Moon, Todd K. (2005), Fehlerkorrekturcodierung: mathematische Methoden und Algorithmen, John Wiley & Sons, p. 638, ISBN 9780471648000.
  39. ^ Moon (2005), p. 686.
  40. ^ Cassandras, Christos G.; LaFortune, Stephane (2007), Einführung in diskrete Ereignissysteme (2. Aufl.), Springer, p. 224, ISBN 9780387333328.
  41. ^ Grünbaum, Branko (2009), Konfigurationen von Punkten und Linien, Graduiertenstudien in Mathematik, vol. 103, American Mathematical Society, p. 28, ISBN 9780821843086.

Externe Links