"Vorübung zur Graphentheorie" |
| 10.06.2008, 18:13 | ddp | Auf diesen Beitrag antworten » | ||
| "Vorübung zur Graphentheorie" 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 |
||||
| 10.06.2008, 18:25 | Rare676 | Auf diesen Beitrag antworten » | ||
google mal nach dem Schubfachprinzip |
||||
| 10.06.2008, 18:31 | 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 |
||||
| 10.06.2008, 20:33 | AD | Auf diesen Beitrag antworten » | ||
Ich kenne das Problem in der Formulierung:
Wie leicht ersichtlich ist das zu dem von sqrt4 bzw. dem Originalproblem äquivalent. |
||||
| 11.06.2008, 19:12 | ddp | Auf diesen Beitrag antworten » | ||
okay vielen dank 
|
||||
| 11.06.2008, 19:32 | 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? |
||||
| Anzeige | ||||
|
|
||||
| 11.06.2008, 19:37 | AD | Auf diesen Beitrag antworten » | ||
Gar nicht! Die Aussage ist für alle nur denkbaren Färbungsmöglichkeiten nachzuweisen. |
||||
| 11.06.2008, 19:44 | 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 
|
||||
| 11.06.2008, 19:50 | 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. |
||||
| 11.06.2008, 19:59 | 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 
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 |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
