5-regulärer Graph mit 9 Knoten. |
| 13.06.2021, 11:34 | Eistee88 | Auf diesen Beitrag antworten » |
| 5-regulärer Graph mit 9 Knoten. Hallo, ich studiere Informatik und habe in meiner aktuellen Hausaufgabe im Modul Diskrete Strukturen folgenden Aufgabe, welche ich nicht ganz durchblicke: In einer Gruppe von neun Personen ist angeblich jede Person genau fünf der anderen Personen der Gruppe früher schon einmal begegnet. Beweisen Sie, dass dies nicht möglich ist. Meine Ideen: Ich habe erkannt, dass es sich hierbei um einen 5-regulären Graph mit 9 Knoten handelt. Mein erster Versuch war, über die maximale Anzahl von Knoten in einem k-regulären Graphen einen Widerspruch zu erzeugen, was mir aber nicht geglückt ist. Übersehe ich hier das Offensichtliche? Vielleicht kann mir ja einer von euch helfen 
|
||
| 13.06.2021, 11:53 | Huggy | Auf diesen Beitrag antworten » |
| RE: 5-regulärer Graph mit 9 Knoten. Von jedem der 9 Knoten gehen genau 5 Kanten aus, wobei jede Kante zu 2 Knoten gehört. Wieviele Kanten müsste der Graph dann haben? |
||
| 13.06.2021, 12:15 | Eistee88 | Auf diesen Beitrag antworten » |
| RE: 5-regulärer Graph mit 9 Knoten. Ich habe das jetzt mal aufgezeichnet und bin zum Entschluss gekommen, dass es keinen solchen Graphen gibt(?) Ich kann zwischen 9 Knoten 22 Kanten ziehen, aber ein letzter Knoten hat nur 4 Kanten und kann keine fünfte bekommen, weil alle anderen schon 5 haben. Wie kann ich das in einen vernünftigen Beweis verpacken, sodass mich der Übungsleiter auch versteht? |
||
| 13.06.2021, 12:24 | Ulrich Ruhnau | Auf diesen Beitrag antworten » |
| RE: 5-regulärer Graph mit 9 Knoten. Die Anzahl der Kanten wäre was leider keine ganze Zahl ist. Weil die Anzahl aber ganzzahlig sein muß, ist das ein Widerspruch. |
||
| 13.06.2021, 12:26 | Eistee88 | Auf diesen Beitrag antworten » |
| RE: 5-regulärer Graph mit 9 Knoten. Wenn das schon als Widerspruch genügt, bin ich ja auf der sicheren Seite 
|
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
