 |
 |
 |
 |
 |
 |
Startseite » Forum » Kreis in Graph finden
Kreis in Graph finden
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie
 
|
  |
|---|
|
Hallo, erstmal folgende Aufgabe: Wie viel Knoten hat der kleinste Graph so dass für jeden Knoten gilt deg(v) und hat einen Kreis der Länge 9. Also ich hab mir folgendes Überlegt: Wenn ich einen Kreis der Länge 9 hab, bedeutet es er besteht aus 9 Kanten . Also werden mindestens 9 Knoten benötigt um den Kreis zu bilden. Da wäre ja dann der Petersen Graph Knoten) der passende Graph. Mit 9 Knoten hab ich keinen Graph gefunden bei dem alle Knoten Grad 3 haben. Gibt es hier irgendeine Möglichkeit einen zu finden ? Gruß Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
| Hierzu passend bei OnlineMathe: Kreiszahl (Mathematischer Grundbegriff) Kreis (Mathematischer Grundbegriff) Elementare Kreisteile (Mathematischer Grundbegriff) |
|
 |
|
Hallo, zählt man alle Kanten doppelt, so kommt man bei einem Graphen mit 9 Knoten auf , was augenscheinlich ein Widerspruch ist. Ergo kann es nur einen Graphen mit gerader Eckenzahl geben, der gewünschtes leistet. [Unfug gelöscht] Ja, der Petersen-Graph scheint mir geeignet. Ich weiß nicht, ob der folgende Graph mit den Eckpunkten 1, 2, ..., 10 isomorph ist: Die Kanten und seien enthalten (wobei mod 10 gerechnet werden möge). Mfg Michael |
|
|
|
> Da wäre ja dann der Petersen Graph (10 Knoten) DER passende Graph. Sollte es nicht eher heißen "... EIN passender Graph". Ich erkenne jetzt nicht unbedingt die Logik, dass es der Petersen-Graph sein MUSS. 10 Knoten ja (siehe MichaL), aber nicht notwendig Petersen. |
|
|
|
Hallo, so, ich musste mir den Petersen-Graphen erst einmal genauer anschauen. Er enthält offenbar keinen Hamiltonkreis. Der von mir angegebene schon. Ergo sind beide nicht isomorph. Mfg Michael |
 |
|
Ja, das war etwas blöd formuliert , ich meinte natürlich ein Graph mit Knoten. Ich habe den Petersen genannt, da ich ihn kenne. |
|
|
|
Danke für die Antwort. zählt man alle Kanten doppelt, so kommt man bei einem Graphen mit 9 Knoten auf 2∣E∣=∑v∈Vdeg(v)=9⋅3=27, was Ich hab den Beweis verstanden, Widerspruch da ungerade ist. Ich bin aber noch etwas verwirrt mit diesem “doppelt” was meinst du mit “alle Kanten doppelt”? |
|
|
|
Danke für die Antwort. zählt man alle Kanten doppelt, so kommt man bei einem Graphen mit 9 Knoten auf 2∣E∣=∑v∈Vdeg(v)=9⋅3=27, was Ich hab den Beweis verstanden, Widerspruch da ungerade ist. Ich bin aber noch etwas verwirrt mit diesem “doppelt” was meinst du mit “alle Kanten doppelt”? |
|
|
|
Hallo, nun, jede Kante hat zwei Ecken als Endpunkte. Zähle ich nun die Grade aller Knoten zusammen, habe ich damit jede Kante doppelt gezählt: für jeden Endpunkt einmal. Mfg Michael |
 |
|
Achsoo, ja klar. Vielen Dank an euch für die Hilfe. Gruß |
|
|
|
Hallo, hier eine Lösung, eine Art Hochhaus vom Nikolaus. Gemalt mit meinem Smartphone...  |
1568116
1568080