Graphentheorie < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
ich habe ein Problem mit dem 2.Fall des Satzes von Brooks. Ich verstehe wie der Fall funtkioniert, doch ein Sonderfall macht mir Probleme. In der mündlichen Prüfung wurde ich gefragt, was ich machen müsste, wenn eine der Komponenten ein vollständiger Graph ist. Leider wusste ich damals und auch heute nicht die Antwort. Wir haben den Satz von Brooks über Induktion bewiesen. Der 2. Fall= 2zsh aber nicht 3zsh
Vielen Dank für eure Hilfe
Fabian
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:36 Do 17.11.2005 | | Autor: | Frank05 |
> ich habe ein Problem mit dem 2.Fall des Satzes von Brooks.
Satz von Brooks sagt mir jetzt nichts und was ich auf die Schnelle im Netz dazu gefunden habe scheint nicht grossartig nach Fällen zu unterscheiden. Vielleicht kann da jemand anderes mehr dazu sagen.
> Ich verstehe wie der Fall funtkioniert, doch ein Sonderfall
> macht mir Probleme. In der mündlichen Prüfung wurde ich
> gefragt, was ich machen müsste, wenn eine der Komponenten
> ein vollständiger Graph ist.
Bei Graphfärbung sind vollständige (Teil-)Graphen natürlich immer unangenehm, weil sie viele Farben brauchen. Vom theoretischen Gesichtspunkt her sind vollständige Graphen aber wieder sehr angenehm. Da bei der Färbung zwei benachbarte Knoten nicht die gleiche Farbe tragen dürfen und bei einem vollständigen Graphen alle Knoten benachbart sind kann es somit keine zwei Knoten geben, die dieselbe Farbe besitzen. Um also einen [mm] $K_n$ [/mm] zu färben brauchst du genau $n$ Farben, was gerade der oberen Schranke für die Anzahl der nötigen Farben entspricht.
Da du deine Prüfung aber schon gemacht hast nehme ich an, dass das bereits klar war. Vielleicht hilft es weiter, wenn du die Frage ein wenig ausführlicher formulierst und vielleicht mal den Satz vorstellst, so wie ihr ihn behandelt habt (oder den Beweis, wenn er mit deiner Frage was zu tun hat).
|
|
|
| |
|
Satz von Brooks
Alle Graphen mit n>=3 und einem Maximalgrad Delta, die keine ungeraden Kreise und keine vollständige Graphen sind, sind Delta-Färbbar.
Induktionsanfang: N>=3
Induktionsvorraussetzung: Ein Graph mit n-Ecken (n>=3) und dem Maximalgrad Delta ist Delta färbbar.
Ind. Schritt: Wenn es für n gilt, muss es auch für den Nachfolger von n gelten. Darum setzen wir n=n+1
Fall 1= G ist zsh aber nicht 2-zsh
Ich habe einen Knoten e, der mehrere Komponente verbindet. Würde ich e entfernen würde der Graph in seine einzelnen Komponente auseinanderfallen
Um nach Induktion zu beweisen, dass G<=n Ecken hat, zerlege ich den Graph in die einzelnen Komponenten. Da jede Komponente min. eine Ecke haben muss, hat eine Komponente max. n+1-1=n Ecken. Da die Eckenzahl für jede Komponente <=n ist sind alle Komponenten Delta-färbbar.
Wenn nun in allen Komponenten e die selbe Farbe hat, können die Komponenten zusammengesetzt werden.
Falls e in manchen Komponenten eine andere Farbe hat, müssen in der jeweiligen Komponente die Farben so getauscht werden, dass e die selbe Farbe bekommt wie in den anderen Komponenten.
Fall2: G ist 2-zsh. Aber nicht 3-zsh
Ich habe zwei Punkte e und f, die durch eine Linie verbunden sein können aber nicht müssen. Entferne ich e und f so zerfällt der Graph in die einzelnen Komponenten.
Ist keine der Komponenten ein vollständiger Graph so kann ich den Graph an den Ecken e und f in die einzelnen Komponenten zerlegen. Da wiederum min. eine Ecke in einer weiteren Komponente vorhanden ist, hat eine Komponente n+1-1=n Ecken und ist somit nach Induktionsvorraussetzung Delta-färbbar.
(Wurde in der mündlichen gefragt, konnte ich nicht beantworten)
Falls eine Komponente ein vollständiger Graph ist...???
Vermutung: Muss ich e oder f entfernen und dafür einen Punkt aus einer anderen Komponente nehmen.
E und f dürfen nicht die selbe Farbe haben.
E und f müssen innerhalb der Komponente die selbe Farbe haben um wieder zusammengesetzt werden zu können.
Fall3: G ist 3-zsh, also gilt es auch für alle folgenden Zusammenhänge
Es gibt 2 einen Punkt a und b mit der Distanz 2. Diese Distanz können sie haben, da G kein vollständiger Graph ist.
Entferne ich die Punkte a und b, so muss ein Zusammenhang der Punkte e1 bis en-1 bestehen.
(Jetzt was ich verstanden habe, nur in der Prüfung habe ich es so gesagt wie wir es abgeklärt hatten.)
Ich färbe zuerst die Punkte a und b gleich, falls sie mit einem der Punkte e1 bis en-1 verbunden sind.
Danach färbe ich en-1 mit einer weiteren Farbe. Ich färbe nun weiter in Richtung e1. Ich kann jeden Punkt (abgesehen von e1) färben, da es immer einen Vorgänger gibt der noch ungefärbt ist. Delta-1.
Der Punkt e1 kann gefärbt werden, da a und b die selbe Farbe haben und somit für e1 Delta-1 Farben übrig bleiben.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:40 So 20.11.2005 | | Autor: | Frank05 |
> Satz von Brooks
>
> Alle Graphen mit n>=3 und einem Maximalgrad Delta, die
> keine ungeraden Kreise und keine vollständige Graphen sind,
> sind Delta-Färbbar.
Ok.
> Induktionsanfang: N>=3
Wo ist der Induktionsanfang?
> Induktionsvorraussetzung: Ein Graph mit n-Ecken (n>=3) und
> dem Maximalgrad Delta ist Delta färbbar.
Aber nur wenn er kein ungerader Kreis und nicht vollständig ist!
> Ind. Schritt: Wenn es für n gilt, muss es auch für den
> Nachfolger von n gelten. Darum setzen wir n=n+1
>
> Fall 1= G ist zsh aber nicht 2-zsh
>
> Ich habe einen Knoten e, der mehrere Komponente verbindet.
> Würde ich e entfernen würde der Graph in seine einzelnen
> Komponente auseinanderfallen
>
> Um nach Induktion zu beweisen, dass G<=n Ecken hat, zerlege
> ich den Graph in die einzelnen Komponenten.
Gerade hast du für den I.S. einen Graph mit n+1 Ecken betrachtet und jetzt willst du zeigen er hat nur n Ecken? Willst du nicht vielmehr zeigen, dass er sich mit [mm] $\Delta$ [/mm] Farben färben lässt?
> Da jede
> Komponente min. eine Ecke haben muss, hat eine Komponente
> max. n+1-1=n Ecken. Da die Eckenzahl für jede Komponente
> <=n ist sind alle Komponenten Delta-färbbar.
Das würde ich in einer Prüfung so nicht akzeptieren. Was ist mit den Fällen ungerader Kreise und vollständiger Graphen bei den Komponenten? Bevor du die Induktionshypothese anwendest solltest du schon zeigen, dass auch die Voraussetzungen des Satzes erfüllt sind.
> Wenn nun in allen Komponenten e die selbe Farbe hat, können
> die Komponenten zusammengesetzt werden.
> Falls e in manchen Komponenten eine andere Farbe hat,
> müssen in der jeweiligen Komponente die Farben so getauscht
> werden, dass e die selbe Farbe bekommt wie in den anderen
> Komponenten.
> Fall2: G ist 2-zsh. Aber nicht 3-zsh
>
> Ich habe zwei Punkte e und f, die durch eine Linie
> verbunden sein können aber nicht müssen. Entferne ich e und
> f so zerfällt der Graph in die einzelnen Komponenten.
>
> Ist keine der Komponenten ein vollständiger Graph so kann
> ich den Graph an den Ecken e und f in die einzelnen
> Komponenten zerlegen.
Das kann man immer machen. Ich sehe nicht, wieso du dafür fordern musst, dass die Komponenten keine vollst. Graphen sind.
> Da wiederum min. eine Ecke in einer
> weiteren Komponente vorhanden ist, hat eine Komponente
> n+1-1=n Ecken und ist somit nach Induktionsvorraussetzung
> Delta-färbbar.
Maximal n Ecken. Und wieder wendest du die Ind.Vor. an, ohne vorher die Voraussetzungen zu klären.
> (Wurde in der mündlichen gefragt, konnte ich nicht
> beantworten)
> Falls eine Komponente ein vollständiger Graph ist...???
> Vermutung: Muss ich e oder f entfernen und dafür einen
> Punkt aus einer anderen Komponente nehmen.
Also bauen wir uns die Situation mal ordentlich auf:
Wir haben zwei Knoten e und f, so gewählt, dass gemäß dem 2-fachen Zshg der Graph G nach Entfernen von e und f in die Komponenten [mm] $C_1 \hdots C_k$ [/mm] zerfällt. Zudem ist der maximale Knotengrad in G als [mm] $\Delta$ [/mm] gegeben.
Betrachte nun den Graph [mm] $C_i'$, [/mm] der sich aus einer Komponente [mm] $C_i$ [/mm] und den Ecken e und f ergibt.
Mittels Farbverschiebung genügt es zu zeigen, dass jeder Graph [mm] $C_i'$ $\Delta$-färbbar [/mm] ist. Insbesondere hat [mm] $C_i'$ [/mm] < n+1 Knoten, da jeweils noch mind. eine andere Komponente existiert. Und auch der maximale Knotengrad in [mm] $C_i'$ [/mm] ist <= [mm] $\Delta$ [/mm] weil es sich um Untergraphen von G handelt.
Wenn nun alle [mm] $C_i'$ [/mm] die Voraussetzungen des Satzes erfüllen ist die [mm] $\Delta$-Färbbarkeit [/mm] von G bewiesen, da es genügt alle [mm] $C_i'$ [/mm] mit [mm] $\Delta$ [/mm] Farben zu färben.
Sei nun also [mm] $C_i'$ [/mm] ein vollständiger Graph mit m < n+1 Knoten. Ein solcher Graph benötigt genau m Farben, aber wir wissen auch, dass der Knotengrad der Knoten e und f in [mm] $C_i'$ [/mm] gerade m-1 ist. Da noch mind. eine weitere Komponente existiert, die im Graph G eine Kante zu e und f besitzt gilt: max. Knotengrad in G [mm] $\Delta$ [/mm] >= m. Damit dürfen wir also ohne Probleme die m Farben für [mm] $C_i'$ [/mm] verwenden.
Sei schließlich [mm] $C_i'$ [/mm] ein ungerader Kreis mit n > 3 Knoten (n=3 ist ein vollst. Graph und somit schon behandelt). Dann gilt für alle Knoten in diesem Kreis, dass ihr Knotengrad 2 ist. Wir wissen aber auch, dass 3 Farben genügen, um einen ungeraden Kreis zu Färben. Wiederum folgt aus der Existenz mind. einer weiteren Komponente, dass der Knotengrad von e und f in G aber mind. 3 sein muss.
Natürlich keine Gewähr, dass der Beweis stimmt 
> E und f dürfen nicht die selbe Farbe haben.
> E und f müssen innerhalb der Komponente die selbe Farbe
> haben um wieder zusammengesetzt werden zu können.
Aus dem letzten Satz werd ich nicht schlau. Wenn e und f durch eine Kante verbunden sind dürfen sie natürlich nicht dieselbe Farbe haben. Ansonsten spielt das keine Rolle. Was das Zusammensetzen der Komponenten angeht gibt es aufgrund einer einfachen Farbverschiebung keine Probleme. Die Komponenten schneiden sich ja gerade in den Knoten e und f. Und wie oben gezeigt lassen sie sich mit der entsprechenden Anzahl Farben färben. Um das nun zusammenzusetzen müssen natürlich e und f auf jeweils eine Farbe festgelegt werden. Dies spielt aber keine Rolle, wenn man danach die jeweilige Komponente färbt, da man einfach die vorher ermittelte Färbung verwendet und die Farben neu nummeriert, so dass die Farben von e und f mit den jetzt zu verwendenden übereinstimmen.
> Fall3: G ist 3-zsh, also gilt es auch für alle folgenden
> Zusammenhänge
>
> Es gibt 2 einen Punkt a und b mit der Distanz 2. Diese
> Distanz können sie haben, da G kein vollständiger Graph
> ist.
Was willst du mir damit sagen?
> Entferne ich die Punkte a und b, so muss ein Zusammenhang
> der Punkte e1 bis en-1 bestehen.
Was sind das jetzt plötzlich für Punkte?
> (Jetzt was ich verstanden habe, nur in der Prüfung habe ich
> es so gesagt wie wir es abgeklärt hatten.)
Abgeklärt??
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:05 Do 01.12.2005 | | Autor: | fabian1983 |
Erst einmal dankeschön! Dies war die Zusammenfassung, die ich an einen Bekannten geschickt hatte. Deswegen die Kürze und das "abgeklärt". Nochmal dankeschön für den Beweis des zweiten Falls. Gruß Fabian
|
|
|
|
