Grafik (Diskrete Mathematik)

Ein Diagramm mit sechs Scheitelpunkten und sieben Kanten

Im Mathematik, und genauer gesagt in Graphentheorie, a Graph ist eine Struktur, die sich um a entspricht einstellen von Objekten, in denen einige Paare der Objekte in gewissem Sinne "verwandt" sind. Die Objekte entsprechen mathematische Abstraktionen, die genannt werden Eckpunkte (auch genannt Knoten oder Punkte) und jedes der verwandten Eckpaare wird als als bezeichnet Kante (auch genannt Verknüpfung oder Linie).^[1] Typischerweise wird eine Grafik in abgebildet in diagrammatische Form als eine Reihe von Punkten oder Kreisen für die Eckpunkte, verbunden durch Linien oder Kurven für die Kanten. Diagramme sind eines der Studienobjekte in Diskrete Mathematik.

Die Kanten können gerichtet oder ungerichtet werden. Zum Beispiel, wenn die Eckpunkte Menschen auf einer Party darstellen und es eine Kante zwischen zwei Personen gibt, wenn sie die Hand schütteln A kann einer Person die Hand schütteln B nur wenn B schüttelt auch die Hand mit A. Im Gegensatz dazu, wenn eine Kante von einer Person A zu einer Person B entspricht A schuldet Geld BDann wird dieses Diagramm gerichtet, da das Geld nicht unbedingt erwidert wird.

Diagramme sind das grundlegende Thema, das von untersucht wurde Graphentheorie. Das Wort "Diagramm" wurde zuerst in diesem Sinne von verwendet J. J. Sylvester 1878 in einer direkten Beziehung zwischen Mathematik und chemische Struktur (Was er Chemico-grafisches Bild nannte).^[2][3]

Definitionen

Die Definitionen in der Graphentheorie variieren. Das Folgende sind einige der grundlegenderen Möglichkeiten, Grafiken und verwandte zu definieren Mathematische Strukturen.

Graph

Ein Diagramm mit drei Scheitelpunkten und drei Kanten

A Graph (manchmal genannt ungerichtete Grafik zur Unterscheidung von a gerichteter Graph, oder Einfaches Diagramm zur Unterscheidung von a Multigraph)^[4][5] ist ein Paar G = (V, E), wo V ist ein Set, dessen Elemente genannt werden Eckpunkte (Singular: Scheitelpunkt) und E ist eine Reihe gepaarter Scheitelpunkte, deren Elemente genannt werden Kanten (manchmal Links oder Linien).

Die Eckpunkte x und y einer Kante {x, y} werden als die genannt Endpunkte der Kante. Die Kante soll zu beitreten x und y und zu sein Vorfall an x und y. Ein Scheitelpunkt kann zu keiner Kante gehören, in diesem Fall wird er keiner anderen Scheitelpunkte verbunden.

A Multigraph ist eine Generalisierung, die es mehreren Kanten ermöglicht, das gleiche Paar von Endpunkten zu haben. In einigen Texten werden Multigraphen einfach als Grafiken bezeichnet.^[6][7]

Manchmal dürfen Diagramme enthalten Schleifen, die Kanten sind, die sich einem Scheitelpunkt mit sich selbst verbinden. Zur Erlaubnis von Schleifen muss die obige Definition geändert werden, indem Kanten wie definiert werden Multisets von zwei Scheitelpunkten statt zwei Sätze. Solche verallgemeinerten Grafiken werden genannt Grafiken mit Schleifen oder einfach Grafiken Wenn aus dem Kontext klar ist, dass Loops zulässig sind.

Im Allgemeinen der Satz von Scheitelpunkten V soll endlich sein; Dies impliziert, dass auch die Menge der Kanten endlich ist. Unendliche Grafiken werden manchmal berücksichtigt, aber häufiger als eine besondere Art von angesehen binäre Beziehung, da die meisten Ergebnisse zu endlichen Graphen nicht auf den unendlichen Fall erstrecken oder einen anderen Beweis benötigen.

Ein leere Grafik ist eine Grafik mit einer leeres Set von Scheitelpunkten (und damit ein leerer Satz von Kanten). Das bestellen einer Grafik ist die Anzahl der Eckpunkte |V|. Das Größe einer Grafik ist die Anzahl der Kanten |E|. In einigen Kontexten, wie zum Beispiel zum Ausdruck des Rechenkomplexität von Algorithmen ist die Größe |V| + |E| (Andernfalls könnte ein nicht leeres Diagramm eine Größe 0 haben). Das Grad oder Wertigkeit eines Scheitelpunkts ist die Anzahl der Kanten, die ihm zugeordnet sind; Für Grafiken ^[1]Bei Schleifen wird eine Schleife zweimal gezählt.

In einer Grafik der Ordnung nDer maximale Grad jedes Scheitelpunkts ist n - 1 (oder n Wenn Schleifen erlaubt sind) und die maximale Anzahl von Kanten ist n(n - 1)/2 (oder n(n + 1)/2 Wenn Schleifen erlaubt sind).

Die Kanten einer Grafik definieren a Symmetrische Beziehung auf den Eckpunkten, die genannt Adjazenzbeziehung. Insbesondere zwei Scheitelpunkte x und y sind benachbart wenn {x, y} ist eine Kante. Ein Diagramm kann durch seine vollständig spezifiziert werden Adjazenzmatrix A, was ist ein n × n Quadratmatrix mit A_ij Angabe der Anzahl der Verbindungen vom Scheitelpunkt angeben i zu Scheitelpunkt j. Für eine einfache Grafik, A_ij ∈ {0,1}, Angabe der Trennung bzw. Verbindung, inzwischen A_II = 0 (Das heißt, eine Kante kann nicht mit demselben Eckpunkt beginnen und enden). Diagramme mit Selbstschleifen werden durch einige oder alle charakterisiert A_II gleich einer positiven Ganzzahl gleich sein, und Multigraphen (mit mehreren Kanten zwischen Scheitelpunkten) werden durch einige oder alle charakterisiert A_ij gleich einer positiven Ganzzahl sein. Unbekannte Graphen haben eine symmetrische Adjazenzmatrix (A_ij = A_ji).

Gerichteter Graph

Ein gerichtetes Diagramm mit drei Scheitelpunkten und vier gerichteten Kanten (der Doppelpfeil repräsentiert eine Kante in jeder Richtung)

A gerichteter Graph oder Digraph ist ein Diagramm, in dem Kanten Orientierungen haben.

In einem eingeschränkten, aber sehr gesunden Menschenverstand, den Begriff,^[8] a gerichteter Graph ist ein Paar G = (V, E) bestehend aus:

• V, a einstellen von Eckpunkte (auch genannt Knoten oder Punkte);
• E ⊆ {(((x,y) | (x,y) ∈ V², x ≠ y}, a einstellen von Kanten (auch genannt gerichtete Kanten, gerichtete Links, Regielinien, Pfeile oder Bögen) welche sind bestellte Paare von Scheitelpunkten (dh eine Kante ist mit zwei unterschiedlichen Eckpunkten verbunden).

Um Unklarheiten zu vermeiden, kann diese Art von Objekt genau a bezeichnet werden Direktes einfaches Diagramm.

Am Rand (x,y) Regie von x zu y, die Eckpunkte x und y werden als die genannt Endpunkte der Kante, x das Schwanz der Kante und y das Kopf der Kante. Die Kante soll zu beitreten x und y und zu sein Vorfall an x und weiter y. Ein Scheitelpunkt kann in einer Grafik existieren und nicht zu einer Kante gehören. Die Kante (y,x) wird genannt umgekehrte Kante von (x,y). Mehrere Kanten, nicht unter der obigen Definition zulässig, sind zwei oder mehr Kanten sowohl mit demselben Schwanz als auch mit demselben Kopf.

In einem allgemeinen Sinne des Begriffs, der mehrere Kanten zulässt,^[8] a gerichteter Graph ist ein bestelltes Triple G = (V, E, ϕ) bestehend aus:

• V, a einstellen von Eckpunkte (auch genannt Knoten oder Punkte);
• E, a einstellen von Kanten (auch genannt gerichtete Kanten, gerichtete Links, Regielinien, Pfeile oder Bögen);
• ϕ: E → {((x,y) | (x,y) ∈ V², x ≠ y}, ein Inzidenzfunktion Zuordnen jeder Kante zu einem geordnetes Paar von Scheitelpunkten (dh eine Kante ist mit zwei unterschiedlichen Eckpunkten verbunden).

Um Unklarheiten zu vermeiden, kann diese Art von Objekt genau a bezeichnet werden Regissed Multigraph.

A Schleife ist eine Kante, die sich einem Scheitelpunkt an sich selbst verbindet. Regiegrafische Diagramme, die in den beiden obigen Definitionen definiert sind x Für sich selbst ist die Kante (für ein gerichtetes einfaches Diagramm) oder ist auf (für einen gerichteten Multigraph) festgefallen) (x,x) das ist nicht in {((x,y) | (x,y) ∈ V², x ≠ y}. Um Schleifen zuzulassen, müssen die Definitionen erweitert werden. Für gerichtete einfache Grafiken die Definition von E sollte modifiziert werden an E ⊆ {(((x,y) | (x,y) ∈ V²}. Für gerichtete Multigraphen die Definition von ϕ sollte modifiziert werden an ϕ: E → {((x,y) | (x,y) ∈ V²}. Um Unklarheiten zu vermeiden, können diese Arten von Objekten genau a bezeichnet werden Regie Directed Simple Graph, die Schleifen erlauben und ein Regie als Multigraph -Genehmigungsschleifen (oder ein Köcher) beziehungsweise.

Die Kanten eines gerichteten einfachen Diagramms zulässigen Schleifen G ist ein homogene Beziehung ~ auf den Eckpunkten von G das heißt das Adjazenzbeziehung von G. Insbesondere für jede Kante (x,y), seine Endpunkte x und y sollen sein benachbart zueinander, was bezeichnet wird x ~ y.

Gemischte Grafik

A gemischte Grafik ist ein Diagramm, in dem einige Kanten gerichtet werden können und einige möglicherweise ungerichtet werden. Es ist ein bestelltes Triple G = (V, E, A) Für ein gemischte einfache Grafik und G = (V, E, A, ϕ_E, ϕ_A) Für ein gemischtes Multigraph mit V, E (die ungerichteten Kanten), A (die gerichteten Kanten), ϕ_E und ϕ_A definiert wie oben. Regie und ungerichtete Grafiken sind Sonderfälle.

Gewichtete Grafik

Ein gewichtetes Diagramm mit zehn Scheitelpunkten und zwölf Kanten

A gewichtete Grafik oder ein Netzwerk^[9][10] ist ein Diagramm, in dem jeder Kante eine Zahl (das Gewicht) zugeordnet ist.^[11] Solche Gewichte können beispielsweise Kosten, Längen oder Kapazitäten darstellen, abhängig vom vorliegenden Problem. Solche Diagramme entstehen in vielen Kontexten zum Beispiel in kürzeste Pfadprobleme so wie die Problem mit reisenden Verkäufern.

Arten von Grafiken

Orientierte Grafik

Eine Definition von a Orientierte Grafik ist, dass es sich um eine gerichtete Grafik handelt, in der höchstens eine von (x, y) und (y, x) Kann Kanten des Diagramms sein. Das heißt, es ist ein gerichtetes Diagramm, das als gebildet werden kann Orientierung eines ungerichteten (einfachen) Diagramms.

Einige Autoren verwenden "orientiertes Diagramm", um dasselbe wie "gerichtete Grafik" zu bedeuten. Einige Autoren verwenden "orientiertes Diagramm", um eine Orientierung eines gegebenen ungerichteten Diagramms oder Multigraphen zu bedeuten.

Regelmäßige Grafik

A Regelmäßige Grafik ist ein Diagramm, in dem jeder Scheitelpunkt die gleiche Anzahl von Nachbarn hat, d. H. Jeder Scheitelpunkt hat den gleichen Grad. Ein reguläres Diagramm mit Gradschätzchen k wird als a genannt k- reguläre Grafik oder reguläres Gradgraf k.

Symmetrische Grafik

A Symmetrische Grafik ist ein Diagramm, so dass für alle Kantenpaare eine Symmetrieoperation aufweist, die den ersten in beide angegebenen Orientierungen auf die zweite ändert.

Komplette Graph

Ein komplettes Diagramm mit fünf Eckpunkten und zehn Kanten. Jeder Scheitelpunkt hat eine Kante für jeden anderen Scheitelpunkt.

A Komplette Graph ist ein Diagramm, in dem jedes Eckpaar durch eine Kante verbunden ist. Ein vollständiges Diagramm enthält alle möglichen Kanten.

Finite Graph

A Finite Graph ist ein Diagramm, in dem der Scheitelpunkt und der Kantensatz sind Finite -Sets. Ansonsten wird es als als genannt Infinite Graph.

Am häufigsten in der Graphentheorie wird impliziert, dass die diskutierten Grafiken endlich sind. Wenn die Grafiken unendlich sind, wird dies normalerweise spezifisch angegeben.

Verbundenes Diagramm

In einem ungerichteten Diagramm ein ungeordnetes Eckpaar {x, y} wird genannt in Verbindung gebracht Wenn ein Pfad von führt x zu y. Ansonsten wird das nicht ordnungsgemäße Paar genannt getrennt.

A verbundenes Diagramm ist ein ungerichteter Diagramm, in dem jedes ungeordnete Paar von Scheitelpunkten im Diagramm verbunden ist. Ansonsten wird es a genannt getrenntes Diagramm.

In einem gerichteten Diagramm ein geordnetes Eckpaar von Scheitelpunkten (x, y) wird genannt stark verbunden Wenn ein gerichteter Pfad von führt x zu y. Andernfalls heißt das geordnete Paar genannt schwach verbunden Wenn ein ungerichteter Weg von führt x zu y Nach dem Ersetzen aller gerichteten Kanten durch ungerichtete Kanten. Andernfalls heißt das geordnete Paar genannt getrennt.

A stark verbundene Grafik ist ein gerichteter Diagramm, in dem jedes geordnete Eckpaar im Diagramm stark verbunden ist. Ansonsten wird es a genannt schwach verbundene Grafik Wenn jedes geordnete Eckpaar im Diagramm schwach verbunden ist. Sonst wird es a genannt getrenntes Diagramm.

A K-Vertex-verbundenes Diagramm oder K-Kanten-verbundenes Diagramm ist eine Grafik, in der kein Satz von k - 1 Scheitelpunkte (jeweils Kanten) existiert, dass beim Entfernen die Grafik getrennt wird. EIN k-Vertex-verbundenes Diagramm wird oft als einfach a bezeichnet K-vernetzte Grafik.

Bipartitale Grafik

A Bipartitale Grafik ist ein einfaches Diagramm, in dem der Scheitelpunktsatz sein kann verteilt in zwei Sätze, W und X, damit keine zwei Scheitelpunkte in W Teilen Sie eine gemeinsame Kante und keine zwei Scheitelpunkte in X Teilen Sie eine gemeinsame Kante. Alternativ ist es eine Grafik mit a Chromatische Zahl von 2.

In einem Komplette zweigliedrige GrafikDas Scheitelpunktsatz ist die Vereinigung von zwei disjunkten Sätzen, W und X, damit jeder Scheitelpunkt in W ist neben jedem Scheitelpunkt in angrenzend X Aber es gibt keine Kanten innerhalb W oder X.

Pfadgrafik

A Pfadgrafik oder Lineare Graph von Ordnung n ≥ 2 ist ein Diagramm, in dem die Eckpunkte in einer Reihenfolge aufgeführt werden können v₁, v₂,…, v_n so dass die Kanten die sind {v_i, v_i+1} wo i = 1, 2,…, n - 1. Pfaddiagramme können als verbundene Graphen charakterisiert werden Untergraph eines anderen Diagramms ist es a Weg in dieser Grafik.

Planare Graph

A Planare Graph ist ein Diagramm, dessen Eckpunkte und Kanten in einer Ebene so gezeichnet werden können, dass sich keine zwei der Kanten kreuzen.

Zyklusdiagramm

A Zyklusdiagramm oder Rundgrafik von Ordnung n ≥ 3 ist ein Diagramm, in dem die Eckpunkte in einer Reihenfolge aufgeführt werden können v₁, v₂,…, v_n so dass die Kanten die sind {v_i, v_i+1} wo i = 1, 2,…, n - 1 plus die Kante {v_n, v₁}. Zyklusdiagramme können als verbundene Graphen charakterisiert werden, in denen der Grad aller Scheitelpunkte 2 beträgt. Wenn ein Zyklusdiagramm als Untergraphen eines anderen Diagramms auftritt, handelt es sich um einen Zyklus oder eine Schaltung in diesem Diagramm.

Baum

A Baum ist eine ungerichtete Grafik, in der zwei zwei beliebt sind Eckpunkte sind verbunden von genau eins Wegoder äquivalent a in Verbindung gebracht acyclisch ungerichtete Grafik.

A Wald ist eine ungerichtete Grafik, in der zwei beliebige Scheitelpunkte verbunden sind höchstens eine Pfad oder äquivalent ein acyclisch ungerichteter Diagramm oder gleichwertig a Union Union von Bäumen.

Polytree

A Polytree (oder Regieer Baum oder Orientierter Baum oder Einzelnetzwerk) ist ein Regie acyclische Graphen (DAG), dessen zugrunde liegender Diagramm ein Baum ist.

A Polyforest (oder Regiewald oder Orientierter Wald) ist eine gerichtete acyclische Graphen, deren zugrunde liegender und gereizter Diagramm ein Wald ist.

Fortgeschrittene Klassen

Fortgeschrittenere Arten von Grafiken sind:

• Petersen Graph und seine Verallgemeinerungen;
• Perfekte Grafiken;
• COgraphen;
• Akkorddiagramme;
• Andere Grafiken mit groß Automorphismusgruppen: Scheitelpunkt-transitiv, Arc-transitiv, und Entfernungstransitive Diagramme;
• stark reguläre Grafiken und ihre Verallgemeinerungen Abstandsregeln.

Eigenschaften von Graphen

Zwei Kanten einer Grafik werden genannt benachbart Wenn sie einen gemeinsamen Scheitelpunkt haben. Zwei Kanten einer gerichteten Grafik werden genannt aufeinanderfolgenden Wenn der Kopf des ersten der Schwanz des zweiten ist. In ähnlicher Weise werden zwei Eckpunkte genannt benachbart Wenn sie eine gemeinsame Kante haben (aufeinanderfolgenden Wenn der erste der Schwanz und der zweite der Kopf einer Kante ist), wird in diesem Fall die gemeinsame Kante gesagt beitreten die beiden Eckpunkte. Eine Kante und ein Scheitelpunkt an dieser Kante werden genannt Vorfall.

Das Diagramm mit nur einem Scheitelpunkt und keinen Kanten wird als die genannt triviale Grafik. Ein Diagramm mit nur Scheitelpunkten und keine Kanten ist als bekannt als eine zartloser Diagramm. Das Diagramm ohne Scheitelpunkte und ohne Kanten wird manchmal als die genannt NULL -Diagramm oder leere GrafikAber die Terminologie ist nicht konsistent und nicht alle Mathematiker erlauben dieses Objekt.

Normalerweise sind die Eckpunkte eines Diagramms von Natur aus als Elemente eines Satzes unterscheidbar. Diese Art von Diagramm kann genannt werden Scheitelpunkt markiert. Für viele Fragen ist es jedoch besser, Eckpunkte als nicht zu unterscheiden zu behandeln. (Natürlich können die Eckpunkte durch die Eigenschaften des Graphen selbst, z. B. durch die Anzahl der einfallenden Kanten, immer noch unterscheidbar sein.) Die gleichen Bemerkungen gelten für Kanten, sodass Diagramme mit gekennzeichneten Kanten genannt werden Kantenmarkierung. Diagramme mit den an Kanten oder Scheitelpunkten verbundenen Beschriftungen sind allgemeiner als als beschriftet. Folglich sind Grafiken, in denen Scheitelpunkte nicht zu unterscheiden sind, und die Kanten sind nicht zu unterscheiden unbeschrieben. (In der Literatur der Begriff beschriftet Kann für andere Arten von Kennzeichnungen gelten, abgesehen von dem, was nur dazu dient, verschiedene Scheitelpunkte oder Kanten zu unterscheiden.)

Das Kategorie aller Grafiken ist die Komma -Kategorie Setzen Sie ↓ D wo D: Set → Set ist das Functor ein Set nehmen s zu s × s.

Beispiele

Ein Diagramm mit sechs Scheitelpunkten und sieben Kanten

• Das Diagramm ist eine schematische Darstellung des Diagramms mit Scheitelpunkten ${\ displayStyle v = \ {1,2,3,4,5,6 \}}$ und Kanten ${\ displayStyle e = \ {\ {1,2 \}, \ {1,5 \}, \ {2,3 \}, \ {2,5 \}, \ {3,4 \}, \ {4 , 5 \}, \ {4,6 \} \}.}$
• Im Informatik, gerichtete Grafiken werden verwendet, um Wissen darzustellen (z. B., konzeptionelle Grafik), endliche Staatsmaschinenund viele andere diskrete Strukturen.
• A binäre Beziehung R auf einem Set X Definiert ein angegebenes Diagramm. Ein Element x von X ist ein direkter Vorgänger eines Elements y von X dann und nur dann, wenn Xry.
• Ein gerichteter Diagramm kann Informationsnetzwerke wie z. B. modellieren Twitter, mit einem Benutzer, der einem anderen folgt.^[12][13]
• Besonders regelmäßige Beispiele für gerichtete Graphen werden von der angegeben Cayley -Grafiken sowohl von endlich erzeugten Gruppen als auch von Schreier Coset Graphs
• Im Kategoriestheorie, jeder Kleine Kategorie hat ein zugrunde liegendes gerichtetes Multigraph, dessen Eckpunkte Objekte der Kategorie sind und deren Kanten die Pfeile der Kategorie sind. In der Sprache der Kategorie Theorie sagt man, dass es a gibt vergesslicher Funkern von dem Kategorie kleiner Kategorien zum Kategorie von Köpfen.

Grafikoperationen

Es gibt mehrere Operationen, die neue Grafiken aus den ersten produzieren, die in die folgenden Kategorien eingeteilt werden könnten:

• Unary Operations, die ein neues Diagramm aus einem anfänglichen erstellen, wie z. B.:
  • Kantenkontraktion,
  • Liniendiagramm,
  • Dual -Graph,
  • Komplementgrafik,
  • Grafikumschreiben;
• Binäre Operationen, die ein neues Diagramm aus zwei anfänglichen erstellen, wie z. B.:
  • Uneiniger Vereinigung von Graphen,
  • kartesischer Produkt von Grafiken,
  • Tensorprodukt von Graphen,
  • starkes Produkt von Grafiken,
  • Lexikografisches Produkt von Graphen,
  • Serie -Parallel -Diagramme.

Verallgemeinerungen

In einem HypergraphEine Kante kann mehr als zwei Eckpunkte verbinden.

Eine ungerichtete Grafik kann als als angesehen werden Einfacher Komplex bestehend aus 1-Einfaches (die Kanten) und 0-Simplices (die Eckpunkte). Als solche sind Komplexe Verallgemeinerungen von Graphen, da sie höherdimensionale Vereinfachungen ermöglichen.

Jede Grafik führt zu einem Matroid.

Im Modelltheorie, eine Grafik ist nur ein Struktur. Aber in diesem Fall gibt es keine Einschränkung für die Anzahl der Kanten: Es kann jede sein Kardinalzahl, sehen kontinuierliche Grafik.

Im Computerbiologie, Leistungsdiagrammanalyse führt Leistungsdiagramme als alternative Darstellung ungerichteter Graphen ein.

Im Geografisches Informationssystem, Geometrische Netzwerke werden nach Grafiken eng modelliert und leihen viele Konzepte aus Graphentheorie räumliche Analyse in Straßennetzwerken oder Versorgungsnetze durchzuführen.

Siehe auch

• Konzeptionelle Grafik
• Graph (abstrakter Datentyp)
• Graph database
• Grafikzeichnung
• Liste der Graphentheorethemen
• Liste der Veröffentlichungen in der Graphentheorie
• Netzwerktheorie

Anmerkungen

Verweise

• Balakrishnan, V. K. (1997). Graphentheorie (1. Aufl.). McGraw-Hill. ISBN 978-0-07-005489-9.
• Bang-Jensen, J.; Gutin, G. (2000). Digraphen: Theorie, Algorithmen und Anwendungen. Springer.
• Bender, Edward A.; Williamson, S. Gill (2010). Listen, Entscheidungen und Grafiken. Mit einer Einführung in die Wahrscheinlichkeit.
• Berge, Claude (1958). Théorie des Graphes et Ses Anwendungen (auf Französisch). Paris: Dunod.
• Biggs, Norman (1993). Algebraische Graphentheorie (2. Aufl.). Cambridge University Press. ISBN 978-0-521-45897-9.
• Bollobás, Béla (2002). Moderne Graphentheorie (1. Aufl.). Springer. ISBN 978-0-387-98488-9.
• Diestel, Reinhard (2005). Graphentheorie (3. Aufl.). Berlin, New York: Springer-Verlag. ISBN 978-3-540-26183-4.
• Graham, R. L.; Grötschel, M.; Lovász, L. (1995). Handbuch der Kombinatorik. MIT Press. ISBN 978-0-262-07169-7.
• Gross, Jonathan L.; Yellen, Jay (1998). Graphentheorie und ihre Anwendungen. CRC Press. ISBN 978-0-8493-3982-0.
• Gross, Jonathan L.; Yellen, Jay (2003). Handbuch der Graphentheorie. CRC. ISBN 978-1-58488-090-5.
• Harary, Frank (1995). Graphentheorie. Addison Wesley Publishing Company. ISBN 978-0-201-41033-4.
• Iyanaga, Shôkichi; Kawada, Yukiyosi (1977). Enzyklopädische Wörterbuch für Mathematik. MIT Press. ISBN 978-0-262-09016-2.
• Zwillinger, Daniel (2002). Mathematische Tische und Formeln von CRC Standard (31. ed.). Chapman & Hall/CRC. ISBN 978-1-58488-291-6.

Weitere Lektüre

• Trudeau, Richard J. (1993). Einführung in die Graphentheorie (Korrigiert, vergrößerte Veröffentlichung. Ed.). New York: Dover Publications. ISBN 978-0-486-67870-2. Abgerufen 8. August 2012.

Externe Links

• Medien im Zusammenhang mit der Grafik (diskrete Mathematik) bei Wikimedia Commons
• Weisstein, Eric W. "Graph". Mathord.