Knotengrad und das Handschlaglemma

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Der Grad eines Knotens

Der Grad eines Knotens ist die Anzahl der Kanten, die an ihn stoßen. In einem einfachen Graphen ist das dasselbe wie die Anzahl seiner Nachbarn. Es ist die lokalste Zahl, die ein Graph hat: Sie können sie an einem einzigen Knoten ablesen, ohne auf irgendetwas anderes zu schauen. Dennoch wird erstaunlich viel globale Struktur allein durch die Grade bestimmt, und genau darum geht es in diesem Artikel.

Die Schreibweise ist kurz. deg(v) ist der Grad von v, δ(G) ist der Minimalgrad über alle Knoten und Δ(G) der Maximalgrad. Ein Knoten vom Grad 0 heißt isoliert, ein Knoten vom Grad 1 ist ein Blatt oder Endknoten, und ein Graph, in dem jeder Knoten denselben Grad r hat, ist r-regulär. Das Grundvokabular, einschließlich der Frage, warum eine Schleife 2 zum Grad beiträgt, steht im Leitfaden zu Knoten und Kanten; dieser Artikel nimmt es als Ausgangspunkt und fragt, was Grade verraten können.

Ein kleines Freundschaftsnetz trägt den ganzen Artikel. Acht Personen, A bis H, und zwölf Freundschaften:

E = {AB, AC, AD, BC, BD, CD, AE, DE, AF, EF, FG, AH}       12 Kanten

deg:   A 6   B 3   C 3   D 4   E 3   F 3   G 1   H 1
δ = 1 (G und H)      Δ = 6 (A)      Durchschnittsgrad = 24 / 8 = 3

2. Das Handschlaglemma

Addieren Sie die Grade des Beispiels, so erhalten Sie 24, genau das Doppelte seiner 12 Kanten. Das ist kein Zufall dieses Graphen.

Handschlaglemma. In jedem Graphen ist die Summe der Grade aller Knoten gleich der doppelten Anzahl der Kanten: ∑ deg(v) = 2m.

Der Beweis ist eine doppelte Abzählung. Zählen Sie die Paare (Knoten, Kantenende an diesem Knoten). Zählt man nach Knoten, erhält man die Summe der Grade. Zählt man nach Kanten, erhält man 2 für jede Kante, weil jede Kante genau zwei Enden hat, und das gilt auch für eine Schleife, deren beide Enden am selben Knoten sitzen. Beide Zählungen beschreiben dieselbe Menge von Paaren, also sind sie gleich. Die Beobachtung geht auf Eulers Arbeit von 1736 über die Brücken von Königsberg zurück, wo sie in der Sprache von Brücken und Landgebieten erscheint; der Name „Handschlaglemma“ ist modern und stammt vom Bild einer Party, bei der an jedem Händedruck zwei Hände beteiligt sind.

Die nützlichste Folgerung des Lemmas ergibt sich sofort. Die Summe aller Grade ist gerade, also müssen die ungeraden Grade paarweise auftreten:

Jeder Graph hat eine gerade Anzahl von Knoten ungeraden Grades.

Im Beispiel sind die Knoten ungeraden Grades B, C, E, F, G und H: sechs Stück, eine gerade Anzahl, wie versprochen.

3. Grade aus einem gespeicherten Graphen berechnen

Wie günstig Sie einen Grad ablesen können, hängt davon ab, wie der Graph gespeichert ist, ein Zielkonflikt, der im Leitfaden zur Graphdarstellung behandelt wird. Bei einer Adjazenzliste ist der Grad von v die Länge seiner Liste, verfügbar in O(1) bei gespeicherter Länge. Bei einer Adjazenzmatrix ist er die Summe der Zeile v, was O(n) kostet. Bei einer bloßen Kantenliste müssen Sie alle m Kanten durchgehen, daher berechnet man üblicherweise alle Grade in einem Durchlauf und speichert das Ergebnis. Das folgende Programm tut genau das, prüft das Handschlaglemma und berechnet außerdem die beiden Durchschnitte, auf denen Abschnitt 9 aufbaut.

from collections import Counter

edges = ['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'AE', 'DE', 'AF', 'EF', 'FG', 'AH']
adj = {v: set() for v in 'ABCDEFGH'}
for u, v in edges:
    adj[u].add(v)
    adj[v].add(u)

deg = {v: len(adj[v]) for v in adj}
print(deg)
# {'A': 6, 'B': 3, 'C': 3, 'D': 4, 'E': 3, 'F': 3, 'G': 1, 'H': 1}

print(sum(deg.values()), 2 * len(edges))     # das Handschlaglemma
# 24 24
print(sorted(v for v in deg if deg[v] % 2))   # immer eine gerade Anzahl davon
# ['B', 'C', 'E', 'F', 'G', 'H']

# Das Freundschaftsparadoxon: Durchschnittsgrad gegenüber dem Durchschnittsgrad eines Freundes.
mean_degree = sum(deg.values()) / len(deg)
mean_friend = sum(deg[v] ** 2 for v in deg) / sum(deg.values())
print(mean_degree, mean_friend)
# 3.0 3.75

# Wie viele Personen haben weniger Freunde, als ihre Freunde im Durchschnitt haben?
fewer = [v for v in adj if deg[v] < sum(deg[w] for w in adj[v]) / deg[v]]
print(sorted(fewer))
# ['B', 'C', 'E', 'F', 'G', 'H']
print(Counter(deg.values()).most_common(1))  # irgendein Grad wiederholt sich immer
# [(3, 4)]

Zwei Zeilen der Ausgabe verdienen schon jetzt Beachtung. Die Prüfung des Handschlaglemmas gibt 24 24 aus. Und die letzte Zeile meldet, dass der Grad 3 viermal vorkommt. Irgendein Grad wiederholt sich immer, aus einem Grund, den Abschnitt 4 erklärt.

4. Rätsel, die das Lemma sofort löst

Das Handschlaglemma verwandelt mehrere Fragen, die nach einer Suche zu verlangen scheinen, in eine Zeile Arithmetik.

• Können sieben Personen jeweils genau drei anderen die Hand schütteln? Nein. Dazu bräuchte man eine Gradsumme von 7 × 3 = 21, die ungerade ist, aber jede Gradsumme ist das Doppelte einer ganzen Zahl von Händedrücken.
• Gibt es einen 3-regulären Graphen mit 9 Knoten? Nein, aus demselben Grund. Ein r-regulärer Graph mit n Knoten hat nr / 2 Kanten, also muss, wenn r ungerade ist, n gerade sein.
• Wie viele Kanten hat ein Graph mit 10 Knoten und Durchschnittsgrad 3? Genau 15, denn der Durchschnittsgrad ist 2m / n.
• Kann ein Kantenzug jede Kante genau einmal benutzen und an verschiedenen Orten beginnen und enden, wenn nur ein Knoten ungeraden Grad hat? Die Frage stellt sich gar nicht: Ein Graph kann nicht genau einen ungeraden Knoten haben. Eulers Kriterium verlangt null oder zwei davon, wie der Leitfaden zu Eulerwegen erklärt, und das Lemma schließt jede ungerade Anzahl aus.

Ein zweiter Klassiker verwendet stattdessen das Schubfachprinzip:

In jedem einfachen Graphen mit mindestens zwei Knoten haben zwei Knoten denselben Grad.

Bei n Knoten sind die möglichen Grade 0, 1, …, n − 1, also n Werte für n Knoten, sodass „alle verschieden“ bedeuten würde, dass jeder Wert genau einmal vorkommt. Aber 0 und n − 1 können nicht beide auftreten: Ein Knoten vom Grad n − 1 ist mit allen benachbart, also hat niemand Grad 0. Damit bleiben höchstens n − 1 nutzbare Werte für n Knoten, und zwei müssen sich einen teilen. Im Alltag heißt das: Auf jeder Party gibt es zwei Personen, die dort gleich viele Freunde haben. Die Aussage setzt voraus, dass der Graph einfach ist; mit Mehrfachkanten gilt sie nicht. Sie wurde per Brute Force an jedem einfachen Graphen mit bis zu sieben Knoten überprüft.

5. Gradfolgen: Welche Listen können Graphen sein?

Listen Sie die Grade vom größten zum kleinsten auf, so erhalten Sie die Gradfolge, (6, 4, 3, 3, 3, 3, 1, 1) im Beispiel. Eine Folge, die ein einfacher Graph tatsächlich besitzt, heißt graphisch. Eine gerade Summe ist nach dem Handschlaglemma notwendig, aber bei Weitem nicht hinreichend: (4, 4, 4, 1, 1) hat eine gerade Summe und keinen Graphen. Drei Knoten vom Grad 4 unter fünf wären jeweils mit allen anderen benachbart, was den letzten beiden Knoten mindestens Grad 3 geben würde.

Zwei klassische Tests entscheiden die Frage exakt. Der Leitfaden zu Knoten und Kanten führt beide von Hand vor; hier stehen sie als Code. Die Havel–Hakimi-Methode von Havel (1955) und Hakimi (1962) verbindet wiederholt den Knoten mit dem größten verbleibenden Grad mit den nächsten in der Reihe und baut so entweder einen Graphen oder bleibt stecken. Der Erdős–Gallai-Satz von 1960 ist ein Test in geschlossener Form: Eine nicht wachsende Folge mit gerader Summe ist genau dann graphisch, wenn für jedes k die Summe der k größten Grade höchstens k(k − 1) plus die Summe von min(di, k) über die übrigen beträgt.

import heapq

def havel_hakimi(seq):
    """Liefert die Kanten eines einfachen Graphen mit diesen Graden oder None, falls es keinen gibt."""
    if sum(seq) % 2:
        return None                           # eine ungerade Summe verletzt das Handschlaglemma
    heap = [(-d, i) for i, d in enumerate(seq) if d > 0]
    heapq.heapify(heap)
    edges = []
    while heap:
        d, v = heapq.heappop(heap)
        d = -d
        if d > len(heap):
            return None                       # nicht genug andere Knoten zum Verbinden übrig
        taken = [heapq.heappop(heap) for _ in range(d)]
        for dw, w in taken:                   # v mit den d Knoten größten Grades verbinden
            edges.append((v, w))
            if dw + 1 < 0:
                heapq.heappush(heap, (dw + 1, w))
    return edges

def erdos_gallai(seq):
    """True genau dann, wenn die Folge graphisch ist (Erdős und Gallai, 1960)."""
    d = sorted(seq, reverse=True)
    if sum(d) % 2:
        return False
    for k in range(1, len(d) + 1):
        if sum(d[:k]) > k * (k - 1) + sum(min(x, k) for x in d[k:]):
            return False
    return True

print(len(havel_hakimi([6, 4, 3, 3, 3, 3, 1, 1])))
# 12
print(havel_hakimi([4, 4, 4, 1, 1]), erdos_gallai([4, 4, 4, 1, 1]))
# None False
print(havel_hakimi([3, 3, 3, 3, 3]), erdos_gallai([3, 3, 3, 3, 3]))
# None False

Für (4, 4, 4, 1, 1) scheitert die Erdős–Gallai-Ungleichung bei k = 3: Die drei größten Grade summieren sich zu 12, aber die Schranke ist 3 × 2 + 1 + 1 = 8. Beide Funktionen wurden per Brute Force an jeder der 2.353 nicht wachsenden Folgen der Länge n ≤ 7 mit Einträgen von höchstens n − 1 geprüft, und bei der Havel–Hakimi-Funktion wurde zusätzlich geprüft, dass sie einen echten einfachen Graphen mit genau den verlangten Graden liefert. Eine graphische Folge hat meist viele verschiedene Realisierungen, also beschreibt eine Gradfolge eine Familie von Graphen, nicht einen einzelnen Graphen.

6. Was ein großer Minimalgrad garantiert

Wer jeden Knoten zwingt, viele Nachbarn zu haben, erzwingt Struktur. Die Argumente hinter den ersten drei Tatsachen sind alle Variationen einer einzigen Idee: Gehen Sie so weit wie möglich und schauen Sie, wo die Nachbarn des letzten Knotens liegen.

• δ ≥ 2 erzwingt einen Kreis. Nehmen Sie einen längsten Weg. Sein letzter Knoten hat mindestens zwei Nachbarn, und alle liegen auf dem Weg, sonst ließe sich der Weg verlängern. Einer von ihnen ist nicht sein Vorgänger, und diese Kante schließt einen Kreis.
• δ ≥ k erzwingt einen Weg mit mindestens k Kanten. Derselbe längste Weg muss alle δ Nachbarn seines letzten Knotens enthalten, also hat er mindestens δ + 1 Knoten.
• δ ≥ (n − 1) / 2 erzwingt, dass der Graph zusammenhängend ist. Zwei Knoten in verschiedenen Komponenten bräuchten jeweils mindestens (n − 1) / 2 Nachbarn innerhalb ihrer eigenen Komponenten, die zusammen mehr als n Knoten enthielten.

Das berühmteste Ergebnis dieser Art betrifft Hamiltonkreise, also Kreise, die jeden Knoten genau einmal durchlaufen. Zu entscheiden, ob es einen gibt, ist im Allgemeinen NP-vollständig, aber ein großer Minimalgrad entscheidet die Frage.

Satz von Dirac (1952). Jeder einfache Graph mit n ≥ 3 Knoten und Minimalgrad mindestens n / 2 hat einen Hamiltonkreis.

Ore verstärkte den Satz 1960: Es genügt, dass die Grade je zweier nicht benachbarter Knoten zusammen mindestens n ergeben. Die Schwelle n / 2 lässt sich nicht senken. Der vollständige bipartite Graph K2,3 hat fünf Knoten und Minimalgrad 2, knapp unter 5 / 2, und hat keinen Hamiltonkreis, weil ein Kreis durch alle fünf Knoten zwischen den beiden Seiten abwechseln müsste und die Seiten verschieden groß sind.

Das Beispielnetz hat δ = 1, weit unter 8 / 2, und es hat keinen Hamiltonkreis: Ein Kreis kann nie durch ein Blatt wie G laufen, das nur eine Kante hat. Diracs Bedingung ist hinreichend, nicht notwendig, ein Verfehlen beweist also für sich genommen nichts; hier sind die Blätter der eigentliche Grund.

7. Was der Maximalgrad beschränkt

Der Maximalgrad steuert die Färbung. Färben Sie die Knoten einzeln in beliebiger Reihenfolge und geben Sie jedem die kleinste Farbe, die seine bereits gefärbten Nachbarn nicht verwenden. Ein Knoten hat höchstens Δ Nachbarn, also sind höchstens Δ Farben blockiert, und eine der ersten Δ + 1 ist immer frei.

Jeder Graph lässt sich mit höchstens Δ + 1 Farben zulässig färben, und der gierige Algorithmus schafft das in jeder Knotenreihenfolge.

Brooks bewies 1941, dass eine Farbe weniger genügt, mit genau zwei Arten von Ausnahmen: Ein zusammenhängender Graph braucht Δ + 1 Farben nur, wenn er ein vollständiger Graph oder ein ungerader Kreis ist. Ein ungerader Kreis hat Δ = 2 und braucht 3 Farben, und Kn hat Δ = n − 1 und braucht n. Bei der Kantenfärbung ist die Antwort noch genauer: Vizing zeigte 1964, dass sich die Kanten jedes einfachen Graphen mit Δ oder Δ + 1 Farben färben lassen.

Im Beispiel ist Δ = 6, also verwendet die gierige Färbung garantiert höchstens 7 Farben, und der Satz von Brooks senkt die Schranke auf 6. Tatsächlich sind es 4, denn das Beispiel enthält den vollständigen Graphen auf den Knoten A, B, C und D, der 4 Farben braucht, und 4 genügen. Der Maximalgrad ist eine grobe Schranke, wenn ein Knoten weit stärker beschäftigt ist als die übrigen. Die Heuristik von Welsh und Powell aus dem Jahr 1967, die die Knoten nach absteigendem Grad färbt, ist eine Antwort darauf; der nächste Abschnitt liefert eine schärfere.

8. Degeneriertheit und k-Kerne

Der Hub A bläht Δ auf, ohne den Graphen schwer färbbar zu machen. Ein besseres Maß betrachtet, wie dünn der Graph überall ist, statt auf seinen einzelnen am stärksten beschäftigten Knoten zu schauen. Löschen Sie wiederholt einen Knoten mit dem kleinsten verbleibenden Grad. Der größte Grad, bei dem Sie je löschen mussten, ist die Degeneriertheit des Graphen. Gleichwertig dazu: Der k-Kern ist der größte Teilgraph, in dem jeder Knoten mindestens k Nachbarn innerhalb des Teilgraphen hat, ein Begriff, den Seidman 1983 einführte, und die Degeneriertheit ist das größte k mit nicht leerem k-Kern.

Das Abschälen läuft in linearer Zeit, wenn die Knoten nach ihrem aktuellen Grad in Buckets gehalten werden. Matula und Beck gaben 1983 eine solche Smallest-Last-Ordnung in linearer Zeit an, und der Bucket-Algorithmus von Batagelj und Zaveršnik berechnet die Kernzahl jedes Knotens in O(m):

def core_numbers(adj):
    """Kernzahl jedes Knotens: wiederholt einen Knoten kleinsten verbleibenden Grades abschälen."""
    deg = {v: len(adj[v]) for v in adj}
    buckets = [set() for _ in range(max(deg.values(), default=0) + 1)]
    for v, d in deg.items():
        buckets[d].add(v)
    core, k = {}, 0
    for _ in range(len(adj)):
        d = next(i for i, b in enumerate(buckets) if b)   # kleinster nicht leerer Bucket
        k = max(k, d)                         # die Kernzahl sinkt nie wieder
        v = buckets[d].pop()
        core[v] = k
        for w in adj[v]:
            if w not in core:                 # w verliert einen Nachbarn: einen Bucket tiefer verschieben
                buckets[deg[w]].remove(w)
                deg[w] -= 1
                buckets[deg[w]].add(w)
    return core

edges = ['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'AE', 'DE', 'AF', 'EF', 'FG', 'AH']
adj = {v: set() for v in 'ABCDEFGH'}
for u, v in edges:
    adj[u].add(v)
    adj[v].add(u)

core = core_numbers(adj)
print(dict(sorted(core.items())))
# {'A': 3, 'B': 3, 'C': 3, 'D': 3, 'E': 2, 'F': 2, 'G': 1, 'H': 1}
print(max(core.values()))                     # die Degeneriertheit des Graphen
# 3

Die Degeneriertheit des Beispiels ist 3, weit unter seinem Δ von 6. Das ist für die Färbung wichtig, denn gieriges Färben in umgekehrter Abschälreihenfolge gibt jedem Knoten höchstens Degeneriertheit bereits gefärbte Nachbarn, also verwendet es höchstens Degeneriertheit + 1 Farben: hier 4, was optimal ist. Die Degeneriertheit beschränkt auch den Aufwand der Cliquenaufzählung, bei der die Verarbeitung der Knoten in Degeneriertheitsreihenfolge die übliche Beschleunigung ist, und k-Kerne sind ein verbreiteter erster Blick auf große Netze: Die inneren Kerne sind das dicht verwobene Zentrum, die äußeren Schalen die Peripherie.

9. Das Freundschaftsparadoxon

1991 wies der Soziologe Scott Feld auf etwas hin, das wie eine Beleidigung klingt: Im Durchschnitt haben Ihre Freunde mehr Freunde als Sie. Das ist keine Tatsache über Menschen, sondern über Grade, und das Programm in Abschnitt 3 hat es für das Beispiel bereits berechnet. Der Durchschnittsgrad ist 3, aber der Durchschnittsgrad eines Freundes ist 3,75.

Der Grund ist eine Stichprobenverzerrung. Wenn Sie über Personen mitteln, zählt jeder einmal. Wenn Sie über Freunde mitteln, gehen Sie jede Freundschaft durch und betrachten die Person am anderen Ende, sodass eine Person mit d Freunden d-mal gezählt wird. Beliebte Menschen sind in den Freundeslisten anderer gerade deshalb überrepräsentiert, weil sie beliebt sind. In Formeln ist der Durchschnittsgrad ∑ d / n, während der Durchschnittsgrad eines Freundes ∑ d² / ∑ d ist, und die Cauchy–Schwarz-Ungleichung zeigt, dass der zweite Wert nie kleiner als der erste ist, mit Gleichheit nur dann, wenn alle Knoten denselben Grad haben.

Die Abbildung zeigt eine verwandte Version, Person für Person: Sechs der acht Personen haben weniger Freunde als ihre eigenen Freunde im Durchschnitt, und nur A und D liegen vorn. Der Extremfall ist ein Stern: In einem Stern mit neun Blättern ist der Durchschnittsgrad 1,8, aber der Durchschnittsgrad eines Freundes ist 5, und jedes Blatt hat weniger Freunde als sein einziger Freund. Seien Sie bei der personenbezogenen Version allerdings vorsichtig. Die obige Ungleichung betrifft Durchschnitte und garantiert nichts darüber, wie viele Einzelne darunter liegen. In realen Netzen ist der Effekt trotzdem stark: In der Studie von Ugander und Kollegen aus dem Jahr 2011 zum Facebook-Graphen hatten 92,7 % der Nutzer weniger Freunde als die durchschnittliche Freundeszahl ihrer Freunde.

Das Paradoxon hat praktischen Nutzen. Ein Freund einer zufälligen Person ist ein besserer als zufälliger Weg, eine gut vernetzte Person zu finden. Deshalb wurde vorgeschlagen, Freunde zufällig ausgewählter Personen zu beobachten, um eine Epidemie früh zu erkennen, und deshalb kann das Impfen von Bekannten mehr Menschen schützen als zufälliges Impfen.

10. Gradverteilungen in realen Netzen

Bei einem großen Netz ist die Liste der Grade zu lang zum Lesen, deshalb fasst man sie durch die Gradverteilung zusammen: den Anteil der Knoten mit Grad k, für jedes k. Ihre Form sagt viel darüber aus, wie das Netz entstanden ist.

• Zufallsgraphen im Erdős–Rényi-Modell, in dem jedes Paar unabhängig verbunden wird, haben Grade, die eng um den Durchschnitt konzentriert sind, und kaum ein Knoten liegt weit davon entfernt.
• Viele reale Netze sehen ganz anders aus: Die meisten Knoten haben kleinen Grad, und wenige Hubs haben enormen Grad. Barabási und Albert schlugen 1999 vor, dass bevorzugte Anbindung, bei der sich neue Knoten bevorzugt mit bereits beliebten verbinden, eine Potenzgesetz-Verteilung erzeugt, und von dort verbreitete sich der Begriff „skalenfreies Netz“.
• Wie häufig echte Potenzgesetze sind, ist umstritten. Broido und Clauset testeten 2019 insgesamt 927 Netzwerk-Datensätze und fanden nur bei einer kleinen Minderheit davon starke Belege für eine skalenfreie Struktur. Gradverteilungen mit schweren Rändern sind häufig, ein sauberes Potenzgesetz ist es nicht.

Zwei gradbasierte Maße tauchen in der Netzwerkanalyse ständig auf. Gradzentralität ordnet Knoten einfach nach ihrem Grad, die billigste Antwort auf die Frage „Wer ist wichtig?“. Und Assortativität, 2002 von Newman eingeführt, misst, ob Knoten hohen Grades dazu neigen, sich mit anderen Knoten hohen Grades zu verbinden. Newman fand soziale Netze assortativ und viele technische und biologische Netze disassortativ, mit Hubs, die vor allem mit Knoten niedrigen Grades verbunden sind. Das Beispielnetz ist ebenfalls disassortativ: Sein Hub A ist der einzige Freund beider Blätter.

11. Gerichtete Graphen: Eingangsgrad und Ausgangsgrad

In einem gerichteten Graphen hat jeder Bogen einen Anfangs- und einen Endknoten, also hat ein Knoten einen Eingangsgrad, die Anzahl der ankommenden Bögen, und einen Ausgangsgrad, die Anzahl der abgehenden. Das Handschlaglemma teilt sich entsprechend auf: Jeder Bogen trägt eins zu einem Ausgangsgrad und eins zu einem Eingangsgrad bei, also gilt

∑ in-deg(v)  =  ∑ out-deg(v)  =  m          die Anzahl der Bögen

Beachten Sie den fehlenden Faktor 2, ein häufiger Fehler beim Wechsel von ungerichteten zu gerichteten Graphen. Gerichtete Grade haben ihre eigenen Bedeutungen. Ein Knoten mit Eingangsgrad 0 ist eine Quelle und einer mit Ausgangsgrad 0 eine Senke; topologisches Sortieren mit dem Algorithmus von Kahn beginnt bei den Quellen und arbeitet, indem es Eingangsgrade verringert. Ein zusammenhängender Digraph hat genau dann einen geschlossenen Kantenzug, der jeden Bogen genau einmal benutzt, wenn bei jedem Knoten der Eingangsgrad gleich dem Ausgangsgrad ist. Und in einem Webgraphen ist der Eingangsgrad ein erstes Maß für Popularität, die Größe, die PageRank verfeinert, indem es jeden eingehenden Link nach der Bedeutung seiner Quelle gewichtet.

12. Häufige Fehler

13. Glossar

15. Quellen

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

1. Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8 (veröffentlicht 1741), 128 bis 140. Die Beobachtung hinter dem Handschlaglemma, formuliert für Brücken und Landgebiete.
2. Brooks, R. L. (1941). "On Colouring the Nodes of a Network." Proceedings of the Cambridge Philosophical Society 37(2), 194 bis 197.
3. Dirac, G. A. (1952). "Some Theorems on Abstract Graphs." Proceedings of the London Mathematical Society s3-2(1), 69 bis 81.
4. Havel, V. (1955). "Poznámka o existenci konečných grafů." Časopis pro pěstování matematiky 80(4), 477 bis 480. Eine Bemerkung über die Existenz endlicher Graphen.
5. Erdős, P. und Gallai, T. (1960). "Gráfok előírt fokszámú pontokkal." Matematikai Lapok 11, 264 bis 274. Graphen mit vorgegebenen Knotengraden.
6. Ore, O. (1960). "Note on Hamilton Circuits." American Mathematical Monthly 67(1), 55.
7. Hakimi, S. L. (1962). "On the 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. Vizing, V. G. (1964). "On an Estimate of the Chromatic Class of a p-Graph." Diskretnyi Analiz 3, 25 bis 30.
9. Welsh, D. J. A. und Powell, M. B. (1967). "An Upper Bound for the Chromatic Number of a Graph and Its Application to Timetabling Problems." The Computer Journal 10(1), 85 bis 86.
10. Matula, D. W. und Beck, L. L. (1983). "Smallest-Last Ordering and Clustering and Graph Coloring Algorithms." Journal of the ACM 30(3), 417 bis 427.
11. Seidman, S. B. (1983). "Network Structure and Minimum Degree." Social Networks 5(3), 269 bis 287. Der k-Kern.
12. Feld, S. L. (1991). "Why Your Friends Have More Friends Than You Do." American Journal of Sociology 96(6), 1464 bis 1477.
13. Barabási, A.-L. und Albert, R. (1999). "Emergence of Scaling in Random Networks." Science 286(5439), 509 bis 512.
14. Newman, M. E. J. (2002). "Assortative Mixing in Networks." Physical Review Letters 89(20), 208701.
15. Ugander, J., Karrer, B., Backstrom, L. und Marlow, C. (2011). "The Anatomy of the Facebook Social Graph." arXiv:1111.4503.
16. Batagelj, V. und Zaveršnik, M. (2011). "Fast Algorithms for Determining (Generalized) Core Groups in Social Networks." Advances in Data Analysis and Classification 5(2), 129 bis 145. Erstmals 2003 verbreitet als "An O(m) Algorithm for Cores Decomposition of Networks."
17. Broido, A. D. und Clauset, A. (2019). "Scale-Free Networks Are Rare." Nature Communications 10, 1017.
18. Diestel, R. (2017). Graph Theory, 5. Auflage. Graduate Texts in Mathematics 173. Berlin: Springer.