Graphenfärbung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:27 Sa 27.10.2007 | | Autor: | TUMMUT |
| Aufgabe | Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
Den Maximalgrad eines Graphen G=(V,E) bezeichnen wir mit Delta(G):=max v element V deg(v), den Minimalgrad mit delta(G):=min v element V deg(v). Der Graph H=(V`,E`) ist ein Subgraph von G, falls V`teilmenge V und E`teilmenge E gilt, wofür wir auch H Teilmenge G schreiben. Beweisen Sie:
a) chi(G)<=Delta(G)+1
b) chi(G)<=1+max H teilmenge G sigma(H)
c) Was können Sie aus b) für die chromatische Zahl planarer Graphen schlussfolgern? |
Guten Tag, hab zu dieser Aufgabe folgende Fragen:
Wie soll ich a) beweisen ich finde keinerlei Ansatz und hab keine Idee hab schon zig mal meine Aufschriebe durchgelesen und kommen auf keinen grünen Zweig (Evtl. Induktionsbeweis?).
Bei b) denke ich mal das es irgendwie über Induktion gehen muss hab aber auch keinen Ansatz!
|
|
| |
|
Juckjuck, wiiiiiiiir habens! :P
zu a):
Ab Färbungszahl 4 geht es eh immer, siehe Guthie-Beweis!
Bis zum dritten Grad ist der Beweis durch logische Schlussfolgerungen möglich (z.B. für V=1 ist [mm] \Delta [/mm] (G) = 0 [mm] \Rightarrow [/mm] 1 [mm] \le [/mm] 1
Richtigen Beweis haben wir auch nicht, gruß aus Garching (nach münchen innenstadt?)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:00 Mo 29.10.2007 | | Autor: | TUMMUT |
servus, naja wenigstens etwas DANKE! die antwort für c) hab ich im internet in wiki "recherchiert"
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:10 Mo 29.10.2007 | | Autor: | TUMMUT |
es ist nicht die rede davon das der graph planar ist, also ist max delta(G) (n*(n-1)), da jeder knoten aus n mit n-1 anderen knoten verbunden ist, ausserdem muss die färbungszahl gleich n betragen, da ja jeder knoten mit jedem anderen knoten verbunden ist und somit nicht jeder knoten diesselbe farbe haben kann! In Glg.: n<(n-1)*n
|
|
|
|
