Forum:  Graphentheorie
Thema: Beweis einer gefärbten Liste, die ein Mindest-lokales Minima der Farben aufweist
Themen-Übersicht
rapiz
Aktiv
Dabei seit: 26.11.2019
Mitteilungen: 108
Aus:
Themenstart: 2020-07-07 22:14

Aufgabe:

Beweisen Sie:

Eine Liste der Länge n sei mit k Farben gültig gefärbt. Dann bilden die lokalen Minima der Farben eine
unabhängige Menge der Größe mindestens n/(2k −2)−1.


Problem/Ansatz:

Habe folgenden ähnlichen Beweis:

Beweisen Sie: Eine Liste der Länge n sei mit k Farben gültig gefärbt. Dann bilden die lokalen Minima der Farben eine
unabhängige Menge der Größe mindestens (n/2k)−1.





Seien die Farben x[1], .., x[2k]

Widerspruchsbeweis: Annahme: 2k aufeinander folgende Listenelemente enthalten kein lokales Minimum.

Dann gibt es kein i (für 1 < i < 2k) mit x[i - 1] > x[i] < x[i + 1]

Also gilt für alle i: x[i - 1] < x[i] < x[i + 1],
                    x[i - 1] > x[i] > x[i + 1], oder
                    x[i - 1] < x[i] > x[i + 1]
                 
Setze i = k.
Im ersten Fall folgt aus x[k - 1] < x[k] < x[k + 1] auch x[k - 2] < x[k - 1] < x[k] < x[k + 1], sonst wäre k - 1 ein lokales Minimum. Rekursiv folgt also x[1] < x[2] < ... < x[k] < x[k + 1].
Das sind k + 1 Elemente, die unterschiedliche Farben haben, aber es gibt nur k Farben. Widerspruch!

Im zweiten Fall folgt analog: x[k - 1] > x[k] > x[k + 1] > ... > x[2k] und derselbe Widerspruch.


Im letzten Fall folgt: x[1] < x[2] < ... < x[k]
Das sind k Elemente, also x[1] = 0, .., x[k] = k - 1
Da x[k] != x[k+1] und x[k+1] <= k, folgt x[k] > x[k + 1], also x[k] > x[k + 1] > .. > x[2k]
Das sind k + 1 Element, also x[k] = k - 1, x[k + 1] = k - 2, .., x[2k] = k - 1 - k = -1.

Widerspruch!





Wie kann man diesen richtig für den obigen Beweis umwandeln, jemand eine Idee?

Sehe beim Beispiel auch nicht so ganz den Beweis für mindestens (n/2k)−1.


thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 797
Aus: Kiel, Deutschland
Beitrag No.1, eingetragen 2020-07-07 22:25

Hallo,

was sind Farben? Einfach ein Anfangsstück der natürlichen Zahlen?
Was ist ein lokales Extremum einer Liste?

Und was ist eine unabhängige Menge auf Listen? Auf Graphen ist mir das wohl ein Begriff...

mfg
thureduehrsen


rapiz
Aktiv
Dabei seit: 26.11.2019
Mitteilungen: 108
Aus:
Beitrag No.2, vom Themenstarter, eingetragen 2020-07-07 22:59

Geht im Endeffekt wie ich es verstehe um diese Art von Färbung wie in der Graphentheorie nur auf nummerierte Listen in Reihenfolge angewendet.

Als lokales Minimum haben wir defininiert, dass i's Farbe kleiner als der Eintrag davor und danach ist.

Also Farben als Zahlen gekennzeichnet

color(l[i-i]) < color(l[i] ) < color(l[i+1])  


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6546
Aus: Niedersachsen
Beitrag No.3, eingetragen 2020-07-08 11:57

Ich nehme mal an, dass "gültig gefärbt" auch beinhaltet, dass keine zwei benachbarten Knoten die gleiche Farbe haben, richtig?

Zum ersten Beweis:
Es wurde gezeigt, dass 2k aufeinanderfolgende Elemente stets mindestens ein Minimum enthalten. Man kann die n Knoten also in $\lfloor \frac{n}{2k} \rfloor$ disjunkte Gruppen einteilen, die jeweils ein Minimum enthalten.
$\frac{n}{2k}-1$ ist eine Abschätzung nach unten für $\lfloor \frac{n}{2k} \rfloor$, die die Gaußklammern vermeidet.

Zum zweiten Beweis:
Man kann die Beweisidee feintunen, wenn man zwei Fälle unterscheidet:
In eine bestimmten Gruppe aufeinanderfolgender Elemente kommt die Farbe 1 vor. Der entsprechende Knoten ist dann ein Minimum, oder in der Gruppe kommt die Farbe 1 gar nicht vor, dann ...




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=248551=7080
Druckdatum: 2020-09-18 14:42