Knotengrad bei gerichteten Graphen

Question

es geht um diesen Sachverhalt:

Ich habe einen gerichteten Graphen G=(V,E). V ist die Menge der Knoten und E ist die Menge der Kanten.

|δ⁺(v)| ist die Anzahl an Kanten, die von einem Knoten v∈V ausgehen.

|δ^-(v)| ist die Anzahl an Kanten, die in einen Knoten v∈V eingehen.

Und dabei gilt diese Gleichheit:

$$ \sum_{v\in V}|\delta^+(v)|=|E|=\sum_{v\in V}|\delta^-(v)| $$

Ich verstehe nicht, wie man darauf kommt. Ich habe einige Zeichungen über gerichtete Graphen gemacht. Dort konnte ich sehen, dass diese Gleichhung erfüllt ist. Aber wenn ich versuche das allgemein zu betrachten, komme ich nicht weit.

Zuerst habe ich die Definitionen von δ⁺(v) und δ^-(v) jeweils eingesetzt:

$$ \sum_{v\in V}|\delta^+(v)|=\sum_{v\in V}|\{e\in E:\exists w\in V:e=(v,w)\}| $$

$$ \sum_{v\in V}|\delta^-(v)|=\sum_{v\in V}|\{e\in E:\exists w\in V:e=(w,v)\}| $$

Nur leider bringt mich das auch nicht zu der Erkenntnis, dass man |E| erhält. Anders gesagt: Ich sehe es nicht.

Answer 1

Mach dir einmal (außerhalb der Definition sondern intuitiv im Kopf) klar, was das bedeutet.

Die linke/rechte Summe ist die Summe über die Anzahl der Kanten, die von einem bestimmten Knoten ausgehen/in einen bestimmten Knoten eingehen, für alle Knoten des Graphen.

Aber jede Kante ist genau für einen Ein-grad und einen Aus-grad eines Knotens verantwortlich, da jede Kante aus genau einem Knoten raus und in genau einen Knoten rein geht. Wenn du für jeden Knoten alle ausgehenden Kanten aufsummierst und weißt, dass jede Kante die ausgehende Kante genau eines Knotens ist, dann weißt du, dass du einfach die Anzahl der Kanten aufsummierst. Daher kommt der "intuitive Beweis" der Formel bzw. die Herleitung.

Wie beweist man das? Mit Induktion über die Anzahl der Kanten:

Besitzt ein Graph keine Kanten, dann sind alle Eingangs- und Ausgangsgrade 0, also auch deren Summe, genau wie |E|.

Besitzt ein Graph G jetzt n+1 Kanten, dann wähle eine Kante (v,w) aus, der Graph G' ohne diese Kante besitzt jetzt n Kanten und die Gleichung gilt. Fügst du die Kante (v,w) zu G' hinzu, so erhöht sich |E| um 1, genau wie der Ausgangsgrad von v und der Eingangsgrad von w. Alle anderen Grade bleiben unverändert, also erhöhen sich beide Summen auch um 1.

LG