Beitragvon Peter Nos » 24. November 2010, 23:27
Hallo Weltherrscher,
ich stehe immer noch auf dem Schlauch.
Wikipedia sagt in ihrer unendlichen Weisheit:
"Ein Graph ist genau dann bipartit, wenn er keinen Kreis ungerader Länge enthält."
Wenn nun die Karten Knoten darstellen sollen, sind alle Karten mit allen anderen verbunden, da es ja immer genau ein gleiches Element gibt. Alle Knoten sind benachbart! Immerhin würden die Karten damit einen einfachen Graph bilden. (Es gibt keine gleichen Symbole auf einer Karte, also keine Schleifen und auch keine Mehrfachkanten, da eben immer nur ein Symbol zweier Karten gleich ist.) In diesem recht dichten Verbindungsgewirr finde ich aber ziemlich viele Kreise ungerader Länge. ;-)
Aus meiner Erinnerung ist der Begriff "Bipartit" überhaupt nur sinnvoll, wenn sich der Graf in genau zwei disjunkte Teilmengen zerlegen lässt.
> Diese kann man dadurch konstruieren, das man aus 2 gleichen
> Mengen A und B die für gleiche Elemente eine Verbindung haben
> (bipartiter Graph)
> die Elemente so auf die Karten verteilt, das keine 2 gleiche
> Elemente auf einer Karte auftauchen.
Was sind jetzt die Mengen A und B?
Beispiel: Ein Minikunterbunt mit den Zahlen 1,2,3 und 3 Karten:
Die Karten lauten dann:
Karte1: 1,2
Karte2: 2,3
Karte3: 3,1
Annahme: die Karten die Knoten, also z.B:
Menge A enthält Karte 1 und Karte 2
Menge B enthält Karte 3
Es sind aber nach Konstruktion aber Karte 1 und Karte 2 benachbart --> Widerspruch. Gleiches gilt für jede andere Kombination.
Und einen Kreis ungerader Länge gibt es auch: Karte 1 -> Karte 2 -> Karte 3 -> Karte 1.
("Oh - that was easy said man, and proofed with the same argument that black is white and got killed at the next zebra crossing" - Hitchhiker's Guide to the Galaxy, Band 1.)
Ich bleib dabei: Einen offensichtlichen bipartiten Graphen finde ich nicht in Kunterbunt.
Weiterhin viele Grüße,
p.
(Layoute gerade mit Hochdruck die nächste Fairplay und habe deswegen genügend Zeit mich an meine Vorlesung über Kombinatorik und diskrete Mathematik zu erinnern - lang ist es her vielleicht zu lang.)