"Vorübung zur Graphentheorie"

Neue Frage »

ddp Auf diesen Beitrag antworten »
"Vorübung zur Graphentheorie"
Hallo, ich habe schon wieder ein Problem und zwar diese Aufgabe bereitet mir Kopf zerbrechen:

Zu einer Party werden 6 Personen eingeladen. Zeigen Sie:
Wenn es unter diesen 6 Personen keine 3 Personen gibt, von denen je zwei schon einmal miteinander Schach gespielt haben, dann gibt es 3 Personen, von denen keine zwei schon einmal miteinander Schach gespielt haben.

Meine zwei Probleme:
Aufgabenstellung richtig verstehen und wie/womit beweist man so etwas?

Liebe Grüße
Rare676 Auf diesen Beitrag antworten »

google mal nach dem Schubfachprinzip
 
 
sqrt4 Auf diesen Beitrag antworten »

Als Vorübung zur Graphentheorie könntest du ja mal die 6 Personen durch Knotenpunkte darstellen und falls 2 Personen schon mal miteinander gespielt haben, dann zeichnest du eine Kante zwischen den beiden zugehörigen Punkten.

Deine Aufgabe ist es zu beweisen, dass es ein Dreieck in deinem Bild gibt, bzw. falls es das nicht gibt, dann gibt 3 Punkte, die paarweise nicht verbunden
AD Auf diesen Beitrag antworten »

Ich kenne das Problem in der Formulierung:

Zitat:
In einem vollständigen Graphen mit 6 Knoten sei jede der 15 Kanten entweder mit rot oder blau gefärbt. Man zeige, dass es dann im Graph ein einfarbiges Dreieck gibt.

Wie leicht ersichtlich ist das zu dem von sqrt4 bzw. dem Originalproblem äquivalent.
ddp Auf diesen Beitrag antworten »

okay vielen dank Wink
ddp Auf diesen Beitrag antworten »

mist, ich dachte jetzt ist es mir klar, ist es aber nicht so recht...

wenn ich sechs knotenpunkte gezeichnet habe und jede mit einem anderen knoten verbunden habe, komm ich ja auch 15 kanten...

wie geht es denn dann weiter? woher weiss ich welche ich einfärben muss bzw nicht?
AD Auf diesen Beitrag antworten »

Zitat:
Original von ddp
woher weiss ich welche ich einfärben muss bzw nicht?

Gar nicht! Die Aussage ist für alle nur denkbaren Färbungsmöglichkeiten nachzuweisen.
ddp Auf diesen Beitrag antworten »

könntest du mir das mal bitte für einen konkreten fall vorführen, weil ich verstehe es nicht so ganz

ich hoffe das verstößt nicht gegen eure prinzipien Gott
AD Auf diesen Beitrag antworten »

Am Anfang dieses Beitrages hatte ich das schon mal erläutert. Musst du natürlich losgelöst von der dort besprochenen, viel komplexeren Aufgabe betrachten.
ddp Auf diesen Beitrag antworten »

sorry, davon verstehe ich irgendwie nicht so viel...

bin (leider) "nur" ein informatiker und habe normalerweise mit solchem mathe nicht so viel am hut unglücklich

ich habe jetzt hier mit bleistift und einem zettel die 6 knoten gezeichnet, welche die personen modellieren...

dann versuche ich den ersten teil der aussage umzusetzen:
Wenn es unter diesen 6 Personen keine 3 Personen gibt, von denen je zwei schon einmal miteinander Schach gespielt haben

daran scheitere ich aber schon, weil ich mir das nicht an dem modell was wir hier haben vorstellen kann
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »