Die Mathe-Redaktion - 22.01.2020 04:11 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAward-Abstimmung ab 1.1.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 584 Gäste und 1 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von ZetaX Naphthalin
Olympiade-Aufgaben » Kombinatorik » Jeder gerade Graph ist 3-färbbar.
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Jeder gerade Graph ist 3-färbbar.
ZetaX
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 24.01.2005
Mitteilungen: 2804
Aus: Wenzenbach
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2009-09-13


Hallo.

fed-Code einblenden

[Quelle: 6. QEDMO, Aufgabe 2, vormals Übungsaufgabe im Schwätz ;-) ]

Viele Grüße,
fed-Code einblenden



  Profil  Quote  Link auf diesen Beitrag Link
Octopus
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 26.09.2006
Mitteilungen: 472
Aus: Bayern, Pleiskirchen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2009-09-14


Hi,

wie ist das jetzt? Soll man mit dem posten einer Lösung noch einen Tag warten? Oder länger? Bestimme einfach irgendeine Frist.  smile

Viele Grüße,
Octopus



  Profil  Quote  Link auf diesen Beitrag Link
ZetaX
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 24.01.2005
Mitteilungen: 2804
Aus: Wenzenbach
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2009-09-14


Die Frist habe ich ja zur Diskussion gestellt  wink
Sagen wir 48 Stunden reichen erstmal (d.h. ab etwa morgen Mitternacht). Fragen und Ideen sind natürlich immer erwünscht (auch schon jetzt), wer sich mit seiner Lösung sehr sicher ist darf auch etwas länger als bis morgen warten.



  Profil  Quote  Link auf diesen Beitrag Link
chryso
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.02.2009
Mitteilungen: 10529
Aus: Österreich
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2009-09-14


Noch eine Frage:
Im Titel hast du den Begriff "gerader Graph".
Was ist ein gerader Graph?


2009-09-14 01:19 - ZetaX in Beitrag No. 2 schreibt:
(d.h. ab etwa morgen Mitternacht).

Was ist bei dir morgen? Der Tag nach dem diesnächtlichen Schlaf? Oder der 15.9.?
Was ist Mitternacht? 24:00 oder 0:00?

Nicht eindeutig deine Zeitangabe! wink

Lass uns ein wenig Zeit!

LG Chryso



  Profil  Quote  Link auf diesen Beitrag Link
Gockel
Senior Letzter Besuch: im letzten Monat
Dabei seit: 22.12.2003
Mitteilungen: 25545
Aus: Jena
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2009-09-14


Hi chryso.

Gemein ist das, was im Eingangspost beschrieben wurde: Nimm eine endliche Menge von Geraden in der Ebene, die in allgemeiner Lage sind (d.h. eben, dass sich keine drei in einem Punkt schneiden). Die Schnittpunkte sind die Knotenmenge des fraglichen Graphen. Je zwei Knoten sind verbunden, wenn sie auf einer der Geraden "benachbart" sind, d.h. wenn es keine weiteren Knoten zwischen ihnen auf dieser Geraden gibt.
Die Behauptung ist, dass jeder Graph, der auf diese Weise entsteht, 3-färbbar ist.

mfg Gockel.



  Profil  Quote  Link auf diesen Beitrag Link
chryso
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.02.2009
Mitteilungen: 10529
Aus: Österreich
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2009-09-14


@Gockel
Die Angabe habe ich verstanden!

Ich wollte nur wissen, was ein 'gerader Graph' ist, ein Begriff, der (nur) im Titel vorkommt.

Was ist hier 'gerade'?
Der Grad der Knoten? Wohl nicht die Anzahl. Die Geraden ;-) ?

Es muss auch nichts 'gerade' sein, nur möchte ich wissen, was man unter einem 'geraden Graphen' versteht.


LG Chryso



  Profil  Quote  Link auf diesen Beitrag Link
Gockel
Senior Letzter Besuch: im letzten Monat
Dabei seit: 22.12.2003
Mitteilungen: 25545
Aus: Jena
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2009-09-14


Ein gerader Graph ist das, was in der Aufgabe steht. "Gerade" wie in "alle Kanten sind gerade Linien".

mfg Gockel.



  Profil  Quote  Link auf diesen Beitrag Link
chryso
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.02.2009
Mitteilungen: 10529
Aus: Österreich
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2009-09-16


Da ZetaX schrieb, dass man ab Mitternacht Lösungsansätze posten kann/soll, hier eine meiner zwei Ideen für diese Aufgabe:

Beweis mit vollständiger Induktion nach n (Anzahl der Geraden)


1) n=1,2,3 Basis /passt (Wie mir eine Lehrerein einmal sagte, verlange sie, dass man drei Basen untersuche. wink )

2) Graph sei gefärbt für n Gerade.
(n+1). Gerade (g) teilt die Ebene in zwei Halbebenen
Auf der 1. Halbebene behalte ich die Färbungen, auf der 2. färbe ich um:

fed-Code einblenden

LG Chryso



  Profil  Quote  Link auf diesen Beitrag Link
Toaster
Senior Letzter Besuch: im letzten Monat
Dabei seit: 03.01.2003
Mitteilungen: 271
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2009-09-16


Hallo chryso,

ich verstehe deinen Beweis nicht. Kannst du bitte etwas genauer beschreiben, warum das so funktionieren soll?

Angenommen du hast ein Dreieck, welches mit den Farben 1,2,3 gefärbt ist. Jetzt kommt die Gerade g hinzu und schneidet den Knoten mit der Farbe 1 ab (dieser liege in der Halbebene 2, in der du umfärbst, also erhält dieser Knoten jetzt die Farbe t=2). Jetzt sollen beide Schnittpunkte von g mit dem Dreieck mit Farbe t-1=1 gefärbt werden? Das gäbe ja sofort einen Konflikt.

Auch Punkt (c) ist mir nicht klar, denn es kann sein, dass bereits 3 Nachbarn eines solchen Knotens gefärbt wurden, dann könnte eine vierte Farbe notwendig werden, oder?

Viele Grüsse,
Torsten



  Profil  Quote  Link auf diesen Beitrag Link
chryso
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.02.2009
Mitteilungen: 10529
Aus: Österreich
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2009-09-16


Ja, da ist ein Fehler drinnen.  frown
Das ist mir inzwischen schon eingefallen.

Hier muss ich noch etwas ändern. Meine erste Überlegung war nämlich anders. Nur, als ich es hierher tippte, habe ich es in Zeitnot so zusammengeschrieben und einen falschen Gedankengang dabei.
Trotzdem glaube ich, dass diese Beweisidee ausbaubar ist.

----------

Nun gebe ich einmal meinen zweiten Ansatz zum Besten.

Einfärben nach Gewichten:

1) Ich gewichte die Knoten durch. Und zwar folgendermaßen:
a) Ein beliebiger Knoten bekommt den Wert 1
b) Alle Nachbarknoten den Wert 2
c) Alle Nachbarknoten eines Knotens mit Gewicht k , die noch nicht gewichtet sind, bekommen das Gewicht (k+1)
d) Die Färbung erfolgt der Reihe nach.
Jeweils die Knoten mit demselben Gewicht k.
Man lässt einen Zeiger mit Mittelpunkt_1 kreisen. (Ich beginne, falls vorhanden, mit einem 'Dreieck' mit den Gewichten (k-1),k,k)
Sobald der Zeiger einen Knoten mit Gewicht k berührt, wird er regelkonform gefärbt. Das ist möglich, da der Knoten nur an maximal zwei bereits gefärbte Knoten grenzt. Auch der 'letzte' Knoten mit Gewicht k grenzt an maximal zwei gefärbte Nachbarknoten, da ich - falls vorhanden - mit einem 'Dreieck' begonnen habe und nicht zwei 'Dreiecke nebeneinander liegen können.

Etc. Bis alle Knoten gefärbt sind.

LG Chryso





  Profil  Quote  Link auf diesen Beitrag Link
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2009-09-16


OBdA enthalte der Graph keine Gerade, die exakt von Norden nach Süden verläuft. Gehe nun von Osten nach Westen über die Knoten des Graphen, und färbe diese jeweils mit einer Farbe, die den (maximal zwei) zuvor gefärben Nachbarn nicht zugewiesen wurde.

Das wars doch schon, oder?

-- Valentin



  Profil  Quote  Link auf diesen Beitrag Link
Gockel
Senior Letzter Besuch: im letzten Monat
Dabei seit: 22.12.2003
Mitteilungen: 25545
Aus: Jena
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2009-09-16


Ja, das war's schon.

mfg Gockel.



  Profil  Quote  Link auf diesen Beitrag Link
Octopus
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 26.09.2006
Mitteilungen: 472
Aus: Bayern, Pleiskirchen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2009-09-16


Hi,

ja so gehts. Ich habe mir etwas ähnliches überlegt.

Wir zeigen eine etwas stärkere Aussage:
Seien endlich viele Strecken in der Ebene gegeben, von denen sich keine drei in einem Punkt schneiden. Man zeige: die Schnittpunkte dieser Strecken können mit 3 Farben so gefärbt werden, dass keine zwei gleichgefärbten Punkte auf einer der Streckenen benachbart sind. (Zwei Schnittpunkte heißen benachbart, wenn sie beide auf einer der endlich vielen Strecken liegen und auf ihrer Verbindungsstrecke kein weiterer solcher Schnittpunkt liegt.)

Beweis: Induktion nach der Zahl der Schnittpunkte. Für einen Schnittpunkt ist alles klar. Falls die Aussage für n Schnittpunkte gilt und wir eine Konstellation mit n+1 Schnittpunkten vor uns haben, so nehmen wir einen Schnittpunkt P mit maximalem Abstand vom Ursprung. P hat dann höchstens zwei Nachbarn. Nach Induktionsvorraussetzung färben wir die restlichen Punkte und können P problemlos eine dritte Frabe zuordnen.

Viele Grüße,
Octopus



  Profil  Quote  Link auf diesen Beitrag Link
chryso
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 07.02.2009
Mitteilungen: 10529
Aus: Österreich
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2009-09-17


Das ist natürlich noch einfacher.
Aber es entspricht ungefähr meiner zweiten Methode.

Als ich meine erste Idee 'retten' wollte, dachte ich, dass man die Knoten der (n+1).Gerade und der zweiten Halbebene so sukzessive einfärben kann. Da es aber meiner zweiten Methode entsprach, wollte ich mir das nicht weiter überlegen.

Schade! Das mit dem Umfärben wäre irgendwie nett gewesen.



  Profil  Quote  Link auf diesen Beitrag Link
ZetaX hat die Antworten auf ihre/seine Frage gesehen.
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-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]