Kantenzahl, Hamiltonkreis und Vorhandensein einer Eulerschen Linie |
| 23.02.2013, 15:27 | Nspace | Auf diesen Beitrag antworten » |
| Kantenzahl, Hamiltonkreis und Vorhandensein einer Eulerschen Linie Die letzte Frage vor meiner Klausur die sich mir stellt ist diese Aufgabe. Da diese Aufgabe wiederum in 3 Teilaufgaben gegliedert ist, ist es hoffentlich ok, wenn ich sie zusammen stelle. Es sei n >= 2. Der ungerichtete Graph H bestehe aus zwei Zusammenhangskomponenten H1 und H2. Der Teilgraph H1 sei ein vollständiger Graph mit n Knoten, der Teilgraph H2 sei ein Baum mit insgesamt 2n Knoten. Der Graph G entsteht aus H dadurch, dass man weitere Kanten wie folgt zu H hinzufügt: Man verbindet jeden Knoten von H1 mit jedem Knoten von H2 durch eine Kante. a) Wie viele Kanten besitzt der Graph G? b) Besitzt der Graph G einen Hamiltonkreis? Falls ja, so ist eine Konstruktionsvorschrift für einen Hamiltonkreis anzugeben. Falls nein, wieso nicht? c) Begründe, weshalb der Graph G im Allgemeinen keine Eulersche Linie besitzt. Meine Ideen: a) H1 besitzt (n über 2) = (n * (n - 1)) / 2 = (n^2 / 2) - (n / 2) Kanten. H2 besitzt (weil es ein Baum ist) also 2n - 1 Kanten. Durch hinzufügen kommen nochmal n * 2n = 2n^2 Kanten hinzu. Also insgesamt: (n^2 / 2) - (n / 2) + 2n - 1 + 2n^2 = (5 / 2)n^2 + (3 / 2)n - 1. b) Wenn der Baum z.B. die Form eines Sterns hat, dann besitzt H keinen Hamiltonkreis. c) Hier wird's knifflig. Ich würde sagen: H2 ist ein Baum und somit besitzt er Knoten mit Grad 1 (die Blätter). Damit haben diese in H den Grad n + 1 (da ja n Kanten von H1 da angesetzt werden). Wenn nun n gerade ist, ist n + 1 ungerade, weswegen im Allgemeinen keine Eulersche Linie existieren kann. |
||
| 23.02.2013, 17:04 | Nspace | Auf diesen Beitrag antworten » |
Also am ehesten interessiert mich Teilaufgabe c. Wenn mir da jemand sagen könnt,e ob ich richtig liege oder nicht, wäre ich absolut zufrieden gestellt. Der Rest sollte ja eig. passen. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
|
