Knoten und Kanten erklärt

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Die formale Definition eines Graphen

Fast jede Einführung sagt, ein Graph seien „durch Linien verbundene Punkte“. Dieses Bild ist nützlich, und es ist zugleich der Grund, warum so viele Menschen später nicht weiterkommen: Die Punkte und Linien sind nicht das mathematische Objekt. Das Objekt ist ein Paar von Mengen.

Diestels Graph Theory, das Standardwerk für Fortgeschrittene, beginnt mit der Definition in ihrer klarsten Form:

Ein Graph ist ein Paar G = (V, E) von Mengen mit E ⊆ [V]², wobei [V]² die Menge aller 2-elementigen Teilmengen von V bezeichnet.

Packt man das aus, folgt alles Weitere in diesem Artikel:

• V ist eine Menge von Objekten , genannt Knoten. Über sie wird nichts vorausgesetzt. Es können Städte, Menschen, Webseiten, chemische Atome oder ganze Zahlen sein. Die Theorie blickt nie in sie hinein; sie interessiert nur, welche sich unterscheiden lassen.
• E ist eine Menge von 2-elementigen Teilmengen von V. Eine Kante ist buchstäblich die Menge {u, v}, kein Pfeil und keine Kurve. Sie hält nichts fest außer dem Paar, das sie verbindet.
• Da E eine Mengeist, ist eine Kante entweder vorhanden oder nicht. Sie kann nicht zweimal vorkommen.
• Da jedes Element von E genau zwei verschiedene Elementehat, kann eine Kante keinen Knoten mit sich selbst verbinden.

Diese beiden letzten Folgerungen sind keine Einschränkungen, die jemand später hinzugefügt hat. Sie ergeben sich direkt aus der Mengenlehre, und ein Graph, der sie erfüllt, heißt einfach. Mehrfachkanten oder Schleifen zuzulassen bedeutet, die Definition selbst zu ändern; darum geht es in Abschnitt 4.

Zwei weitere Standardnotationen begegnen Ihnen überall. Wenn mehrere Graphen im Spiel sind, schreibt man V(G) und E(G) , um anzugeben, welcher Graph gemeint ist. Und die beiden Größenmaße haben Namen: Die Anzahl der Knoten ist die Ordnung des Graphen, die Anzahl der Kanten seine Größe. Die meisten Algorithmentexte kürzen sie ab zu n = |V| und m = |E|, und diese Konvention gilt auf der gesamten Website.

Dieser Graph ist das durchgehende Beispiel für den Rest des Artikels. Seine Knotenmenge ist V = {A, B, C, D, E, F}, die Ordnung also n = 6, und seine Kantenmenge ist

E = { {A,B}, {A,C}, {B,C}, {B,D}, {C,D}, {D,E}, {E,F} }        also  m = 7

2. Knoten: was sie sind und was nicht

Ein Knoten trägt keine eigene Struktur. Im formalen Objekt ist er ein anonymes Element einer Menge, und alles, was sich über ihn sagen lässt, ergibt sich aus den Kanten, die ihn berühren. Darauf sollte man bestehen, denn genau das macht Graphentheorie übertragbar: Ein Satz über Knoten ist zugleich ein Satz über Flughäfen, Transistoren, Proteine und Git-Commits.

Drei Folgerungen, über die man in der Praxis stolpert:

• Knoten sind unterscheidbar, aber ansonsten austauschbar. Zwei Graphen, die sich nur in der Benennung der Knoten unterscheiden, sind isomorph, und die Graphentheorie behandelt sie als denselben Graphen. Wenn Sie Knoten im Code beschriften, fügen Sie Buchführung hinzu, keine Mathematik.
• Ein isolierter Knoten ist trotzdem ein Knoten. Ein Knoten ganz ohne Kanten ist völlig zulässig und heißt isoliert. Anfänger bauen einen Graphen oft aus einer Kantenliste auf und verlieren dabei stillschweigend jeden isolierten Knoten, was die Ordnung des Graphen ändert und unbemerkt alles bricht, was durch nteilt.
• Der leere Graph existiert, und unendliche Graphen ebenso. Nichts in der Definition verbietet V = ∅, und nichts in ihr verbietet, dass V unendlich ist; das ist das Thema des Leitfadens zu endlichen und unendlichen Graphen. Die meisten Texte lassen es zu, einige wenige schließen es per Festlegung aus; entscheidend ist, zu wissen, welche Konvention Ihre Quelle verwendet, bevor Sie einem Randfall trauen.

Die historische Anmerkung ist eine Zeile wert, denn das Vokabular ist über ein Jahrhundert Literatur hinweg nicht stabil. Hararys klassischer Text von 1969 nennt sie Punkte und Linien. Physiker und viele angewandte Arbeiten sagen Knoten (nodes) und Verbindungen (links). Chemiker sprachen, im Anschluss an Sylvesters Notiz von 1878 in Nature , die dem Fachgebiet überhaupt erst das Wort „Graph“ gab, von Atomen und Bindungen. Alle vier Vokabulare beschreiben dasselbe Paar von Mengen.

3. Kanten, Adjazenz und Inzidenz

Eine Kante verbindet genau zwei Knoten, und diese beiden sind ihre Endknoten oder Enden. Aus dieser einen Beziehung erhalten die beiden Wörter, die Anfänger am häufigsten verwechseln, ihre genaue Bedeutung:

• Adjazenz ist eine Beziehung zwischen zwei Knoten. Die Knoten u und v sind benachbart (adjazent), geschrieben u ~ v, wenn {u, v} ∈ E. Benachbarte Knoten heißen auch Nachbarn, und die Menge aller Nachbarn von v ist seine Nachbarschaft, geschrieben N(v).
• Inzidenz ist eine Beziehung zwischen einem Knoten und einer Kante. Die Kante {u, v} ist inzident zu u und inzident zu v, und zu keinem anderen Knoten.

Die Unterscheidung klingt pedantisch, bis man auf einen Satz wie „zwei benachbarte Kanten“ trifft. Er ist korrekt und meint zwei Kanten mit einem gemeinsamen Endknoten. Knoten sind über eine Kante benachbart; Kanten sind über einen Knoten benachbart. Die beiden Beziehungen auseinanderzuhalten ist das, was es erlaubt, eine Definition wie die einer zulässigen Färbung („benachbarte Knoten erhalten verschiedene Farben“) ohne Mehrdeutigkeit zu lesen.

Im durchgehenden Beispiel ist N(B) = {A, C, D}, B hat also drei Nachbarn. Die Kante {B, D} ist inzident zu B und zu D. Die Kanten {B, D} und {C, D} sind zueinander benachbart, da beide inzident zu D sind.

4. Schleifen und parallele Kanten: wo die Definition sich ändern muss

Reale Systeme erzeugen zwei Dinge, die die Mengendefinition nicht ausdrücken kann. Eine Straße, die einen Kreisverkehr verlässt und zu ihm zurückkehrt, ist eine Kante von einem Knoten zu sich selbst. Zwei getrennte Flüge zwischen demselben Flughafenpaar sind zwei verschiedene Kanten, die dasselbe Paar verbinden. Unter E ⊆ [V]2 gibt es keines von beiden: {A, A} ist eine einelementige Menge, und eine Menge kann dasselbe Element nicht zweimal enthalten.

Die Lösung ist keine Fußnote, sondern eine andere Definition. Bondy und Murtys Graph Theory führt neben den beiden Mengen eine explizite Inzidenzfunktion mit:

G = (V, E, ψ)      mit  ψ: E → ungeordnete Paare von (nicht notwendig verschiedenen) Knoten

Jetzt ist eine Kante ein eigenständiges Objekt mit einer Identität, und ψ gibt an, welches Paar sie verbindet. Zwei verschiedene Kanten dürfen auf dasselbe Paar abgebildet werden, das ergibt parallele Kanten, auch Mehrfachkanten genannt. Eine Kante darf auf ein Paar abgebildet werden, dessen beide Einträge übereinstimmen, das ergibt eine Schleife. Wests Introduction to Graph Theory geht denselben Weg und definiert einen Graphen als Knotenmenge, Kantenmenge und eine Relation, die jeder Kante ihre Endknoten zuordnet.

Das daraus resultierende Vokabular:

Zwei praktische Warnungen. Erstens wird „Multigraph“ nicht einheitlich verwendet: Manche Autoren schließen Schleifen ein, andere nicht; prüfen Sie also die Quelle, bevor Sie einen Satz zitieren. Zweitens trägt eine Schleife 2 zum Grad ihres Knotens bei, nicht 1, denn beide Enden setzen dort an. Diese Konvention ist nicht willkürlich, und der nächste Abschnitt erklärt genau, warum es so sein muss.

Sofern ein Text nichts anderes sagt, bedeutet „Graph“ „einfacher Graph“. Jedes Ergebnis im Rest dieses Artikels setzt das voraus, und der begleitende Leitfaden zu einfachen Graphen und Multigraphen arbeitet genau heraus, was die beiden Erweiterungen verändern und welche Standardschranken ohne sie nicht mehr gelten.

5. Grad und der erste Satz der Graphentheorie

Der Grad eines Knotens v, geschrieben deg(v) oder d(v), ist die Anzahl der zu ihm inzidenten Kanten. Gleichwertig, und nützlicher, ist er die Anzahl der Kantenenden , die in vzusammentreffen. In einem einfachen Graphen ist er gleich der Größe der Nachbarschaft, deg(v) = |N(v)|.

Zwei verwandte Größen tauchen ständig in Schranken und Beweisen auf: der Minimalgrad δ(G) und der Maximalgrad Δ(G). Ein Graph, in dem jeder Knoten denselben Grad k hat, heißt k-regulär.

Nun zum ältesten Satz des Fachgebiets. Er stammt aus Eulers Arbeit von 1736 über die Königsberger Brücken, der Arbeit, mit der die Graphentheorie begann:

Handschlaglemma. In jedem endlichen Graphen ist die Summe aller Knotengrade gleich dem Doppelten der Kantenzahl: ∑v∈V deg(v) = 2m.

Der Beweis ist eine Zeile doppeltes Abzählen. Man zählt die Paare (Knoten, dort ankommendes Kantenende). Die Summe über die Knoten ergibt ∑ deg(v). Die Summe über die Kanten ergibt 2m, denn jede Kante hat genau zwei Enden. Beide zählen dieselbe endliche Menge, also sind sie gleich. Beachten Sie, dass genau dieses Argument eine Schleife doppelt zählen lässt: Auch eine Schleife hat zwei Enden, und beide landen am selben Knoten.

Prüfen Sie es am durchgehenden Beispiel: Die Grade sind 2, 3, 3, 3, 2, 1, ihre Summe ist 14, und der Graph hat 7 Kanten. Das Lemma hat eine unmittelbare und sehr nützliche Folgerung.

Folgerung. In jedem Graphen ist die Anzahl der Knoten ungeraden Grades gerade.

Teilen Sie die Summe in Knoten ungeraden und geraden Grades auf. Die Gesamtsumme ist gerade und der Anteil der Knoten geraden Grades ist gerade, also muss auch der Anteil der Knoten ungeraden Grades gerade sein, was eine gerade Anzahl ungerader Summanden erzwingt. Deshalb kann es auf einer Feier nie genau drei Menschen geben, die jeweils einer ungeraden Zahl anderer die Hand geschüttelt haben, und es ist dasselbe Paritätsargument, das entscheidet, ob ein Eulerweg existiert.

6. Gradfolgen: welche Zahlenlisten Graphen sind

Schreibt man die Grade in nicht aufsteigender Reihenfolge auf, erhält man die Gradfolge. Für das durchgehende Beispiel lautet sie (3, 3, 3, 2, 2, 1). Die natürliche Frage läuft in die andere Richtung: Gibt es zu einer gegebenen Zahlenliste einen Graphen mit genau diesen Graden? Eine Liste, für die es einen gibt, heißt graphisch.

Das Handschlaglemma schließt bereits die Hälfte der Kandidaten aus: Jede Folge mit ungerader Summe ist nicht graphisch. Doch dieser Test reicht bei Weitem nicht aus. Betrachten Sie (3, 3, 1, 1). Die Summe ist 8, also gerade, und kein Knoten verlangt mehr als die 3 verfügbaren Nachbarn. Trotzdem realisiert kein einfacher Graph sie: Die beiden Knoten vom Grad 3 müssen jeweils mit allen drei anderen Knoten verbunden sein, was beide Knoten vom Grad 1 auf Grad 2 zwingt.

Zwei klassische Ergebnisse klären die Frage vollständig:

• Der Satz von Erdős–Gallai (1960) liefert ein exaktes Kriterium: Eine nicht aufsteigende Folge mit gerader Summe ist genau dann graphisch, wenn für jedes kdie Summe der ersten k Glieder höchstens k(k-1) plus die Summe über die übrigen Glieder von min(di, k)ist. Das ist ein geschlossener Test, nach dem Sortieren in linearer Zeit prüfbar.
• Der Havel–Hakimi-Algorithmus, von Havel (1955) und unabhängig davon Hakimi (1962), ist die konstruktive Variante: Man entfernt den größten Grad d, zieht 1 von den nächsten d Einträgen ab, sortiert neu und wiederholt. Die ursprüngliche Folge ist genau dann graphisch, wenn diese Reduktion bei lauter Nullen endet, und die Schritte dienen zugleich als Bauanleitung für einen Graphen, der sie realisiert.

Havel–Hakimi am gescheiterten Beispiel, um zu sehen, wie es funktioniert:

(3, 3, 1, 1)   die 3 entfernen, 1 von den nächsten drei Einträgen abziehen
(2, 0, 0)      neu sortiert
               die 2 entfernen, 1 von den nächsten zwei Einträgen abziehen
(-1, -1)       negativ, die Folge ist also NICHT graphisch

Und am durchgehenden Beispiel, wo es gelingt:

(3, 3, 3, 2, 2, 1)  →  (2, 2, 1, 2, 1)  → sortiert (2, 2, 2, 1, 1)
(2, 2, 2, 1, 1)     →  (1, 1, 1, 1)     → sortiert (1, 1, 1, 1)
(1, 1, 1, 1)        →  (0, 1, 1)        → sortiert (1, 1, 0)
(1, 1, 0)           →  (0, 0)           → lauter Nullen, die Folge IST also graphisch

Eine Warnung, die viele überrascht: Eine graphische Folge kann durch mehrere nicht isomorphe Graphen realisiert werden. Alle Grade zu kennen, legt den Graphen nicht fest.

7. Gerichtete Kanten: Bögen, Eingangs- und Ausgangsgrad

Ersetzt man das ungeordnete Paar durch ein geordnetes Paar, erhält man einen gerichteten Graphen oder Digraphen:

D = (V, A)      mit  A ⊆ V × V

Ein Element (u, v) von A ist ein Bogen oder eine gerichtete Kante, die von ihrem Anfangsknoten u zu ihrem Endknoten vverläuft. Weil das Paar geordnet ist, sind (u, v) und (v, u) verschiedene Bögen, und beide dürfen vorhanden sein. Bang-Jensen und Gutins Digraphs ist das Standardwerk für die Terminologie und reserviert „Bogen“ für das gerichtete Objekt, gerade um die Mehrdeutigkeit zu vermeiden, beides Kanten zu nennen.

Der Grad spaltet sich in zwei:

• Ausgangsgrad d+(v), die Anzahl der Bögen mit Anfangsknoten v.
• Eingangsgrad d-(v), die Anzahl der Bögen mit Endknoten v.

Das Handschlaglemma spaltet sich mit. Jeder Bogen hat genau einen Anfangs- und genau einen Endknoten, also ergibt das getrennte Zählen der Bogenanfänge und Bogenenden

∑v∈V d+(v)  =  ∑v∈V d-(v)  =  |A|

Beachten Sie den fehlenden Faktor 2: Im ungerichteten Fall trug jede Kante zwei Enden zu einer Summe bei, hier trägt jeder Bogen ein Ende zu jeder von zwei Summen bei. Der vollständige Vergleich, einschließlich Orientierungen, der drei Arten von Zusammenhang und der Frage, welche Algorithmen weiter funktionieren, steht im Leitfaden zu gerichteten und ungerichteten Graphen. Knoten mit Eingangsgrad 0 sind Quellen , solche mit Ausgangsgrad 0 Senken, und genau auf diesem Vokabular bauen topologische Sortierung und Netzwerkfluss auf.

8. Gewichtete Kanten und warum Gewichte außerhalb des Graphen liegen

Kürzeste-Wege-Probleme brauchen Entfernungen, Flussprobleme brauchen Kapazitäten, und Planungsprobleme brauchen Dauern. Nichts davon steckt in G = (V, E), und das soll auch so sein. Ein gewichteter Graph ist ein Graph plus eine Funktion:

w: E → ℝ        ordnet jeder Kante eine reelle Zahl zu

Die Gewichte in einer eigenen Funktion statt in den Kanten zu halten, ist genau das, was einem Graphen erlaubt, mehrere Kostenmodelle zugleich zu tragen. Dasselbe Straßennetz ist ein Graph mit drei Gewichtsfunktionen: Kilometer, Minuten und Kraftstoff. Der begleitende Leitfaden zu gewichteten und ungewichteten Graphen verfolgt diese Idee durch Algorithmenwahl, negative Gewichte und Knotenstärke. Wer die Funktion austauscht, verändert jeden kürzesten Weg, ohne einen einzigen Knoten oder eine einzige Kante anzurühren.

Es erklärt auch, warum Algorithmen Bedingungen an w stellen und nicht an den Graphen. Der Dijkstra-Algorithmus verlangt w(e) ≥ 0 für jede Kante; Bellman-Ford toleriert negative Gewichte, aber keine negativen Kreise. Das sind Bedingungen an die Funktion, und das zugrunde liegende Mengenpaar ist ihnen gegenüber gleichgültig.

9. Wie viele Kanten kann ein Graph haben?

In einem einfachen Graphen mit n Knoten ist eine Kante eine Auswahl von 2 verschiedenen Knoten aus n, das Maximum ist also der Binomialkoeffizient

mmax = C(n, 2) = n(n - 1) / 2

Der Graph, der es erreicht und in dem jedes Knotenpaar benachbart ist, ist der vollständige Graph Kn. Für das durchgehende Beispiel ergibt n = 6 eine Obergrenze von 15 Kanten, und der Graph nutzt 7 davon. Das Verhältnis 2m / (n(n-1)) ist die Dichte, hier 0,47.

Diese eine Schranke ist der Grund, warum zwei Begriffe die Algorithmenliteratur beherrschen:

• Ein dichter Graph hat m nahe am Maximum, also m = Θ(n2).
• Ein dünn besetzter Graph hat m weit darunter, typischerweise m = O(n) oder O(n log n). Fast jedes große reale Netzwerk ist dünn besetzt: Straßenkarten, soziale Graphen und Webgraphen haben einen durchschnittlichen Grad im ein- oder zweistelligen Bereich, unabhängig davon, wie viele Knoten sie enthalten.

Dünnbesetztheit ist kein Detail. Sie entscheidet, welche Datenstruktur man verwendet, das Thema des nächsten Abschnitts, und sie ist der Grund, warum eine Komplexität von O(m log n) auf realen Eingaben O(n2) schlägt, obwohl beide im schlimmsten Fall identisch sind.

10. Knoten und Kanten im Code speichern

Es gibt drei Standardarten, V und E im Speicher zu halten, und die Abwägungen zwischen ihnen legen Cormen, Leiserson, Rivest und Stein in Introduction to Algorithmsdar. Der vollständige Vergleich, einschließlich des komprimierten Zeilenformats (CSR) und der Dichteschwelle, ab der eine Matrix die kleinere Variante wird, steht im Leitfaden zur Darstellung von Graphen.

Die praktische Regel folgt aus Abschnitt 9. Traversierungen wie BFS und DFS verbringen ihre gesamte Laufzeit damit, Nachbarmengen abzulaufen, auf einem dünn besetzten Graphen liefert die Adjazenzliste also O(n + m) , wo die Matrix O(n2) erzwingen würde, nur um Zeilen voller Nullen zu durchsuchen. Auf einem dichten Graphen gewinnt die Matrix bei Speicher und Einfachheit. Eine Kantenliste wirkt primitiv, bis man dem Kruskal-Algorithmusbegegnet, der alle Kanten nach Gewicht sortiert und nie Nachbarn nachschlagen muss.

11. Entscheiden, was ein Knoten sein soll

Der schwierigste Teil der Anwendung von Graphentheorie ist kein Satz. Es ist die Wahl, was die Knoten sind, denn diese Wahl legt alles Weitere fest und ist selten eindeutig.

Nehmen Sie ein Straßennetz. Das naheliegende Modell macht Kreuzungen zu Knoten und Straßenabschnitte zu Kanten, und genau das will eine Routing-Engine: Ein Pfad im Graphen ist eine Route im Gelände. Doch Abbiegeverbote und Abbiegekosten gehören zu Kreuzungen, nicht zu Straßen, und dieses Modell hat keinen Platz für sie. Die übliche Lösung kehrt die Wahl um: Man macht jeden Straßenabschnitt zu einem Knoten und verbindet zwei davon, wenn man legal vom einen in den anderen fahren darf. Jetzt ist ein Abbiegevorgang eine Kante und kann Kosten tragen.

Diese Umkehrung ist eine formale Konstruktion, kein Behelf. Der Kantengraph L(G) hat einen Knoten für jede Kante von G, wobei zwei davon benachbart sind, wenn die entsprechenden Kanten von G einen Endknoten teilen. Er geht auf Whitneys Arbeit von 1932 über kongruente Graphen zurück, und er ist der Grund, warum sich ein Problem über Kanten oft einem Algorithmus übergeben lässt, der nur Knoten kennt. Matching-Probleme etwa werden zu Problemen unabhängiger Mengen auf dem Kantengraphen.

Eine kurze Checkliste, die die meisten Modellierungsfehler abfängt:

• Können zwei Ihrer Knoten mehr als einmal verbunden sein? Wenn ja, brauchen Sie einen Multigraphen, oder Sie müssen die parallelen Kanten zu einem Gewicht zusammenfassen.
• Ist die Beziehung symmetrisch? „Ist befreundet mit“ ist es meist, „folgt“ und „hängt ab von“ sind es nicht. Wer das falsch einschätzt, wendet einen ungerichteten Algorithmus auf ein gerichtetes Problem an.
• Betrifft die Beziehung mehr als zwei Dinge zugleich? Eine Kante verbindet genau zwei Knoten. Ein Ausschuss aus fünf Personen oder eine chemische Reaktion mit drei Reagenzien ist eine Hypergraph -Kante, und sie in gewöhnliche Kanten zu zerlegen, verliert Information.
• Ändert sich die Struktur mit der Zeit? Ein gewöhnlicher Graph ist eine Momentaufnahme. Temporale oder dynamische Graphen sind eigene Modelle mit eigener Literatur.

12. Begriffsfallen zwischen Lehrbüchern

Die Graphentheorie ist in mehreren Fachgebieten zugleich gewachsen, daher hat dasselbe Objekt mehrere Namen, und einige Namen bedeuten bei verschiedenen Autoren Verschiedenes. Diese hier verursachen tatsächlich Fehler:

Die sichere Gewohnheit ist die, der jede Fachveröffentlichung folgt: Legen Sie Ihre Konventionen einmal zu Beginn fest und halten Sie sich dann daran. Wenn Sie einen Satz zitieren, zitieren Sie die Definition, unter der er bewiesen wurde.

13. Symbolverzeichnis

Die auf dieser Website und in den folgenden Quellen verwendete Notation.

15. Quellen

Die Definitionen, Sätze und Zuschreibungen oben stammen aus diesen Quellen, in chronologischer Reihenfolge aufgeführt.

1. Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8 (erschienen 1741), 128 bis 140. Die Arbeit über die Königsberger Brücken und der Ursprung des Gradarguments.
2. Sylvester, J. J. (1878). "Chemistry and Algebra." Nature 17, 284. Die Notiz, die das Wort „Graph“ in seinem modernen Sinn einführte.
3. Whitney, H. (1932). "Congruent Graphs and the Connectivity of Graphs." American Journal of Mathematics 54(1), 150 bis 168. Quelle der Konstruktion des Kantengraphen.
4. König, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaft. Das erste Buch, das ausschließlich der Graphentheorie gewidmet war.
5. Havel, V. (1955). "A remark on the existence of finite graphs" (auf Tschechisch). Časopis pro pěstování matematiky 80, 477 bis 480.
6. Erdős, P. und Gallai, T. (1960). "Graphs with prescribed degrees of vertices" (auf Ungarisch). Matematikai Lapok 11, 264 bis 274. Das exakte Kriterium für graphische Folgen.
7. Hakimi, S. L. (1962). "On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I." Journal of the Society for Industrial and Applied Mathematics 10(3), 496 bis 506.
8. Harary, F. (1969). Graph Theory. Reading, Massachusetts: Addison-Wesley. Der Klassiker, der Knoten „points“ und Kanten „lines“ nennt.
9. Bollobás, B. (1998). Modern Graph Theory. Graduate Texts in Mathematics 184. New York: Springer.
10. West, D. B. (2001). Introduction to Graph Theory, 2. Auflage. Upper Saddle River: Prentice Hall. Definiert einen Graphen über eine Knotenmenge, eine Kantenmenge und eine Endknotenrelation.
11. Bondy, J. A. und Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. London: Springer. Quelle der in Abschnitt 4 verwendeten Formulierung mit Inzidenzfunktion.
12. Bang-Jensen, J. und Gutin, G. (2009). Digraphs: Theory, Algorithms and Applications, 2. Auflage. London: Springer. Standardwerk für Bögen und gerichtete Grade.
13. Cormen, T. H., Leiserson, C. E., Rivest, R. L. und Stein, C. (2009). Introduction to Algorithms, 3. Auflage. Cambridge, Massachusetts: MIT Press. Quelle der Darstellungskosten in Abschnitt 10.
14. Diestel, R. (2017). Graph Theory, 5. Auflage. Graduate Texts in Mathematics 173. Berlin: Springer. Quelle der in Abschnitt 1 zitierten Definition.