Bearbeiten von: [Änderungshistorie]
  Zeilenumbrüche automatisch mache ich selbst mit HTML    

Ich möchte eine Mail an , nachdem mein Vorschlag bearbeitet ist.
  Nachricht zur Änderung:

Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
[Link zurück zum Kommentar]

Vorschau:
Re: Der Fünffarbensatz

Hi!

Die Fünffärbung hat gegenüber der Vierfärbung vermutlich auch den Vorteil, dass man Landkarten algorithmisch vermutlich recht gut fünffärben kann.

Sei f: N -> N die FUnktion, die angibt, wie lange usnerer Algorithmus für Graphen mit n Ecken arbeitet.

Bei einem vorgegebenem Graphen mit n Ecken nimmt man eine Ecke von Grad < 6 raus und färbt den verbliebenen Graphen mit dem Algorithmus mit 5 Farben. Das geht in f(n-1) Schritten. Dann prüft man (mit den Bezeichnungen wie im Artikel), ob es einen rot-blau-Weg gibt, das sollte in der Zeit O(n) gehen. Und dann färbt man um, das geht auch in der Zeit O(n).

Insgesamt ist also f(n) = f(n-1)+2O(n), also ist f(n) = O(n²), also nicht so schlecht.

Für die Vierfärbbarkeit gibt es sowas wohl nicht - sonst hätte man je einen echten Beweis.

Weiß jemand näheres darüber?

Gruß
Fabi

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 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]