Grad aller Knoten eines Graph. < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei G ein Graph im graphentheoretischen Sinne und bezeichne E die Kantenmenge des Graphen.
Man zeige: [mm] $\sum_{v\in V(G)} [/mm] d(v) = 2|E| $
Hinweis: Verwenden Sie das Prinzip der doppelten Abzählung. |
Nun, die erste Beweisidee, die mir diesbezügl. Kam lautet so:
Man betrachte einen beliebigen Graphen $G$ mit n Kanten. Nun konzentriere man sich auf seine Kanten; man ziehe jede Kante so viel weg, sodass sie gerade nicht mehr einander berühren. Nun erkennt man glasklar: Von jedem Knoten geht genau eine Kante aus. Also hat jeder Knoten Grad 1. Da es doppelt so viele Knoten wie Kannten gibt, muss die Summe aller Grade nun das doppelte der Kantenzahl sein! Da unser Graph beliebig war, ist unsere Behauptung bewiesen.
So, ich bin mir nicht ganz sicher, ob ich in meinem obigen Beweis auch wirklich das Prinzip der doppelten Abzählung benutzt habe, aber, ich denke, man könnte so hinkommen.
Betrachte die Relation $a$ ~$b$ [mm] $:\Leftrightarrow [/mm] $ $a$ inzidiert $b$.
Nun erstelle man eine Tabelle eines Graphen $G,$ wobei man die Knoten vertikal und die Kanten horizontal unterbringe. Inzidiert nun ein Knoten mit einer Kate, so mache man eine 1 in die Tabelle, sonst 0. Die Regel der doppelten Abzählung besagt doch, dass es für die Summe aller 1en egal ist, ob ich die 1en in den Spalten oder die 1en in den Zeilen (auf)summiere.
Egal, welchen Graphen man mit dieser Tabelle beschreibt, man wird am
Schluss immer finden, dass eine Kante zwei Knoten inzidiert.
Meint ihr vielleicht so:
Einmal betachte ich meine Relation $~$ aus der Sicht der Kanten und einmal aus der Sicht der Knoten. Aber wie schreibe ich das formal hin?
Mein Problem: Ich weiß nicht ganz genau, wie mir die doppelte Abzählung hier zum Beweis verhilft. Kann mir da jemand weiterhelfen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:26 Di 29.05.2012 | | Autor: | clemenum |
Ich denke, ich habe mich ein bisschen zu langwierig ausgedrückt:
Ich wollte einfach nur wissen, ob ich Doppelte Abzählung richtig angewendet habe. Wer das sieht, kann es mir ja sagen! 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Do 31.05.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:42 Do 31.05.2012 | | Autor: | Teufel |
Hi!
Deine erste Variante leuchtet mir leider nicht so ein. Ich würde eher deinen zweiten Weg bevorzugen, dort wird auch doppelte Abzählung verwendet. Nehmen wir an, du machst eine Tabelle, in der links die Knoten und oben die Kanten eingetragen sind. Dann machst du eine 1 in die Tabelle, wenn Knoten und Kante aneinander grenzen und 0 sonst.
Dann stehen in jeder Spalte e der Tabelle genau 2 einsen, weile eine Kante e ja immer an genau 1 Knoten angrenzt. Summiert man das über alle Spalten auf, erhält man $2|E|$.
Nun zu den Zeilensummen. Die Summe aller einsen der Zeile v ist gerade der Grad des Knotens v, also d(v). Summiert man über alle Zeilen, erhält man gerade [mm] \summe_{v \in V}^{}d(v). [/mm]
Das doppelte Abzählen sagt dir nun, dass es egal war, ob du erst die Spaltensummen ausrechnest und dann über alle Spalten addierst oder ob du die Zeilensummen ausrechnest und über alle Zeilen summierst.
Daher muss [mm] $2|E|=\summe_{v \in V}^{}d(v)$ [/mm] gelten!
|
|
|
|
