 |
 |
 |
 |
 |
 |
Startseite » Forum » Beweis zum Dinitz-Problem
Beweis zum Dinitz-Problem
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie
 
|
  |
|---|
|
Hey liebe Freunde der Mathematik, habe hier einen Beweis mit Induktionsbeweis, verstehe diesen aber leider nicht. Könnte mir jemand dabei behilflich sein? Da fehlen nämlich noch einige Schritte. vielen Dank im Voraus. Sei ⃗=(V,E) ein gerichteter Graph, und für jede Ecke v∈V sei eine Farbmenge gegeben, die größer ist als der Aus-Grad, |≥d^+ . Besitzt jeder induzierte Untergraph von ⃗ einen Kern, so existiert eine Listenfärbung von mit einer Farbe aus für jedes . Beweis: Wir verwenden Induktion über . Für gibt es nichts zu beweisen. Wir wählen eine Farbe c∈C=⋃_(v∈V)▒〖C(v)〗 und setzen A(c):=v∈V:c∈C(v)}.Nach Voraussetzung besitzt der induzierte Untergraph einen Kern . Nun färben wir alle v∈K(c) mit der Farbe das ist möglich,da unabhängig ist) und entfernen aus mit aus C. Es sei G´ der induzierte Untergraph auf ohne den Kern und ohne die Farbe als neue Liste von Farbmengen. Man beachte, dass für jedes v∈A(c)\K(c) der Aus-Grad (v)sich um mindestens 1 verringert hat. Somit ist die Voraussetzung |≥d^+ nach wie vor gültig. Dieselbe Bedingung ist auch für die Ecken außerhalb von erfüllt, da in diesem Fall die Farbmenge unverändert ist. Der neue Graph G´ hat nun weniger Ecken als und der Beweis folgt mit Induktiion Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
|
|
|
Hier die Bilder |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1079398
1079397