Handschlaglemma -kleines v?
Hallo Com,
ich beschäftige mich momentan mit dem Handschlaglemma und kann mir die Formel nicht erklären (Bild).
Was bedeutet das kleine v?
Oder noch besser: Kann mir jemand die ganze Formel erklären?
Danke!
2 Antworten
Hallo;
fangen wir mal ganz oben:
G = (V, E)
Das ist dein Graph, bestehend aus einem Tupel mit V und E.
V und E sind jeweils Mengen:
V ist die Menge aller Knoten:
V = {Knoten1, Knoten2, Knoten3, etc}
E ist die Menge aller Kanten:
E = {Kante1, Kante2, Kante3, etc.}
Da steht v∈V; das heißt v ist Element von V;
Also ist v einfach ein Platzhalter für Knoten1 oder Knoten2 oder Knoten3 oder etc.
d(v) ist der Grad eines Knotens. Der Grad eines Knotens ist einfach die Anzahl der Kanten die vom Knoten weg oder hin führen.
Beispiel:
1-----2 | | 3
Knoten 1 hat den Grad 2 und Knoten 2 und 3 haben den Grad 1.
So, was heißt jetzt die Formel:
Die Summe jeden Grades aller Knoten ist gleich das doppelte der Kardinalität von der Menge aller Kanten.
Das ist die Formel ausgeschrieben.
Beispiel:
V = {1, 2, 3, 4}
E = {-, |, /, \} // Einfach Beispiel
G = (V, E)
1--------2
|\ /
| \ /
3 4
Wir haben 4 Knoten und 4 Kanten die als Beispiel so verbunden sind
Knoten 1 hat jetzt den Grad d(v) => d(1)=3
d(2)=2
d(3)=1
d(4)=2
|E|=4 // 4 Elemente sind in E
Wenden wir nun die Formel an:
d(1)+d(2)+d(3)+d(4) = 2*|E|
=> 3+2+1+2 = 2*4
<=> 8 = 8
Da jede Kante immer irgendwo rein und raus gehen muss ist es logisch, dass die Summe der Grade das doppelte der Kanten sein muss.
V bezeichnet eine Menge und v bezeichnet ein Element von V.
(Man nimmt oft ein Paar aus Großbuchstaben und zugehörigem Kleinbuchstaben um eine Menge und eins ihrer Elemente zu bezeichnen.)
E ist vermutlich (offensichtlich - was anderes bleibt bei Graphen ja nicht übrig) die Menge der Kanten.
Letztlich heißt die Formel, dass jede Kante nicht mehr und nicht weniger als zwei Knoten miteinander verbindet. (Die beiden Knoten einer Kante müssen nicht unbedingt voneinander verschieden sein: "Schlinge")