Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Beweis einer gefärbten Liste, die ein Mindest-lokales Minima der Farben aufweist
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Beweis einer gefärbten Liste, die ein Mindest-lokales Minima der Farben aufweist
rapiz
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.11.2019
Mitteilungen: 108
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-07-07


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
thureduehrsen
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.11.2007
Mitteilungen: 797
Aus: Kiel, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-07-07


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
rapiz
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 26.11.2019
Mitteilungen: 108
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-07-07


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])  



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6546
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-07-08


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 ...



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]