graphentheorie - längste wege |
| 31.01.2011, 20:40 | jimmy1234567890 | Auf diesen Beitrag antworten » |
| graphentheorie - längste wege Hi! Mein Problem ist das hier: G ist ein Graph mit n Knoten, die alle mindestens den Grad 2 haben. Lg ist die Länge eines längsten Graohs in G und Sg die Länge eines kürzesten Kreises in G. Gezeigt werden soll: Kann mir jemand helfen? Danke Meine Ideen: ich wüsste wie ich das zeigen könnte, wenn n/2 abgerundet rauskommen müsste: mein erster Fall wäre: Lg ist >= n/2 (abgerundet), dann wäre ich fertig im zweiten Fall dann: Lg ist < n/2 (abgerundet), dann darf G nicht zusammenhängend sein, sondern muss sich in Teile aufteilen, deren maximale Länge Lg < n/2 ist. Damit ist die Länge des größten Kreis auch < n/2, die des kleinsten Kreises erst recht und n-Sg ist dann >= n/2 abgerundet... Für den Fall, dass aufgerundet werden muss ist mir das ganze aber leider nicht klar! Edit: LaTeX korrigiert. LateX-Tags bitte mit / schließen. Vorschau verwenden! Gruß, Reksilat. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
