Planare Graphen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:33 Di 31.01.2006 | | Autor: | dump_0 |
Hallo.
Ich soll folgendes Beweisen:
Enthält ein einfacher, planarer Graph mit n [mm] \ge [/mm] 3 vielen Knoten und m vielen Kanten keine (induizierten) [mm] C_3, [/mm] also Kreise mit 3 Knoten, dann gilt [tex]m \le 2n - 4[/tex].
Hinweis: Betrachten Sie die Flächen.
Ich habe leider keine Ahnung wie ich das genau anstellen soll.
Ich weiß nur das die Anzahl der Flächen = [mm] \vmat{E} [/mm] - [mm] \vmat{V} [/mm] + 2 ist.
Wäre schön wenn mir jemand helfen könnte.
Grüße
[mm] dump_0
[/mm]
|
|
| |
|
Hallo und guten Abend,
sei f die Anzahl der Flaechen, m=|E| und n die Anzahl der Knoten.
Dann ist jede Kante zu zwei Flaechen benachbart
und jede Flaeche hat mindestens 4 Kanten, die sie umranden.
Also 4(m-n+2) = 4f [mm] \leq m\cdot [/mm] 2 und das ergibt
m [mm] \leq [/mm] 2n-4.
Viele Gruesse,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:58 Mi 01.02.2006 | | Autor: | dump_0 |
Vielen Dank für deine Antwort, ist ja doch nicht so schwer. :)
Grüße
[mm] dump_0
[/mm]
|
|
|
|
