Diskrete Mathematik < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 17:57 Fr 19.08.2005 | | Autor: | fabian1983 |
Hallo, ich habe ein Problem. Ich habe im Oktober eine mündliche Prüfung über den Satz von Brooks. Leider verstehe ich weder Beweis noch Beweisidee. Vielleicht kann mir jemand dabei helfen. Vielen Dank im Voraus. Fabian
|
|
| |
|
Bonjour!
Hm, meinst du, deine Verständnisprobleme lassen sich noch etwas genauer artikulieren - bzw. in eine oder zwei oder drei oder n+1 ;) Fragen fassen?
Das würde für uns das Erklären doch deutlich erleichtern.
Also, vielleicht versuchst du einmal, deine Probleme noch etwas näher zu beschreiben, und dann sehen wir weiter.
Und in der Zwischenzeit kannst du dir ja auch einmal ![[]](/images/popup.gif) diesen Skriptauszug (.ps-Format) ansehen, vielleicht hilft dir dieser ja bereits ein wenig.
Au revoir,
jeu blanc.
|
|
|
| |
|
1. Fall:
G ist zusammenhängend
Bedeutet, dass wenn ich einen Punkt entferne der Graph nicht mehr zusammenhängend ist?
Wir wollen eine Delta-Färbung erhalten?
Wie beweise ich dieses?
2. Fall:
G ist 2-zsh
Bedeutet: Entferne ich einen Punkt ist der Graph noch zsh.
Wie zeige ich die Delta-Färbung?
3. Fall und wahrscheinlich der schwerste:
G-ist 3-zsh
Bedeutet: Entferne ich einen Punkt ist der Graph noch 2-zsh.
Wie zeige ich die Delta-Färbung?
Welche Beweisideen stecken dahinter?
Deltafärbung: Anzahl der Färbung=Anzahl der Punkte??
Vielen Dank für deine Hilfe!
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:43 Mo 22.08.2005 | | Autor: | DaMenge |
Hallo,
wie hier schon gesagt wurde: Wir könnten dir den Beweis hier nochmal aufschreiben und evtl. sogar noch etwas umgangssprachlich fassen, aber dann wüssten wir immernoch nicht, worauf wir eingehen sollen und ob der Beweis derselbe ist, den du vor dir hast.
Also, Vorschlag:
Such dir mal einen Beweis raus und schreibe ihn hier hin (so reden wir alle über die selben Dinge).
Dann versuche es evtl mit eigen Worten wieder zugeben und betone ganz besonders, wo du Verständnisprobleme o.ä. hast.
(So wissen wir, was wir voraussetzen können)
viele Grüße
DaMenge
|
|
|
| |
|
Es geht hier um den Beweis durch Induktion.
1.Fall: G ist zusammenhängend. Also gibt es eine Ecke e, so dass G-e unzusammenhängend.
H1, H2,....., Hi sind Komponten und zusammenhängend.
H1+e, H2+e,.... Die Hi+e sind zsh haben mindestens 3 Ecken i und insgesamt <= n Ecken
Also gilt die IV
Wir färben Hi+e so, dass e stets die gleiche Farbe bekommt. Also erhält man eine Delta-Färbung.
Leider haben wir nirgends eine IV aufgeschrieben. Ist die IV: G ist ein ungerader Kreis oder der K-Delta+1 oder G ist Delta-Färbbar?
Welche Beweisidee steckt dahinter?
2. Fall:
G ist 2-zsh aber nicht 3-zsh
Hi+e+f+k
Gilt für alle Hi+e+f+k die IV, dann sind o.B.d.A. alle e gleichgefärbt und alle f gleichgefärbt und [mm] \gamma(e) \not= \gamma(f)
[/mm]
Dann hat man eine Delta-Färbung.
Hier verstehe ich den Beweis überhaupt nicht.
3. Fall:
G ist 3-zsh
G ist kein vollständiger Graph und auch kein ungerader Kreis.
Da G nicht vollständig ist gibt ei Ecken a,b von G mit dem Abstanf d(a,b)=2
Wir betrachten (G-e)-b=H. Da G 3-zsh ist H zsh.
Wir zählen die Ecken von H so auf, dass wir mit e1 beginnen und e+1 immer mit ej in H verbunden ist
j<i+1
Wir färben so. a,b erhalten die Farbe 1. en mit der ersten Möglichen Farbe. en,.....,ei+e seien schon gefärbt. Wir färben ei
a) i+1> ei hat Maximalgrad Delta. ei färben wir mit der ersten möglichen Farbe.
b) i+1=2 e1 färben wir mit der ersten Möglichen Farbe.
Verstehe die Beweisidee nicht.
Vielen Dank für deine Hilfe.
Gruß Fabian
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:08 Do 22.09.2005 | | Autor: | matux |
Hallo Fabian!
Leider konnte Dir keiner hier mit Deinem Problem / Deinen Rückfragen vollständig in der von Dir vorgegebenen Zeit weiterhelfen.
Vielleicht hast Du ja beim nächsten Mal mehr Glück ![[kleeblatt]](/images/smileys/kleeblatt.gif "[kleeblatt]") .
Viele Grüße,
Matux, der Foren-Agent
Allgemeine Tipps wie du dem Überschreiten der Fälligkeitsdauer entgegenwirken kannst findest du in den Regeln für die Benutzung unserer Foren.
|
|
|
|
