Beweis:Graph 3-färbbar < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:31 So 02.01.2011 | | Autor: | cremaaa |
Behauptung: Der Graph A(n) ist dreifärbbar und man kann Farben für Ecken A und B einer Diagonale [mm] e=\overline{AB} [/mm] vorgeben.
Beweis durch vollständige Induktion:
Induktionsanfang:n=3 -> Figur ist Dreieck, welches man dreifärben kann
Induktionsschluss:
Indkutionsvoraussetzung: A(n´) und A(n´´) mit n'<n und n´´<n [mm] \forall n\in\IN [/mm] sind dreifärbbar, [mm] Farbe(A)\not=Farbe(B)
[/mm]
Kann ich diese Behauptung einfach aufstellen? Stimmt das so?
Induktionsschritt: n>3 [mm] \forall n\inN. [/mm] Da n>3 kann man den Graphen an einer Diagonale mit den Ecken A, B in zwei kleinere Graphen A(n´) und A(n´´) mit n'<n und n´´<n [mm] \forall n\in\IN [/mm] zerlegen.
Nach Induktionsvoraussetzung sind A(n´) und A(n´´) dreifärbbar und man kann Farben für A und B vorgeben (z.B.: Farbe(A)=rot, Farbe(B)=grün). Durch "Zusammenkleben" der Graphen ergibt sich eine Dreifärbung des gesamten Graphen A(n).
Das Zusammenkleben funktioniert ja gerade deswegen reibungslos, da ich wieder die Ecken A und B aufeinander klebe, oder?
Ist dieser Induktionsbeweis nun vollständig? Ich wäre für Anregungen und Verbesserungen dankbar!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:22 Sa 08.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
