eulersche linie, hamiltonschen kreis

28.11.2006, 22:38

informatikmaus

Auf diesen Beitrag antworten »

eulersche linie, hamiltonschen kreis

die aufgabe lautet:

Der Graph G bestehe aus zwei Zusammenhangskomponenten G_1, G_2, wobei G1 ein vollständiger Graph mit n Knoten und G2 ein Baum mit ebenfalls n Knoten ist (mit n >= 1). Der Graph H entstehe aus G dadurch, dass man weitere Kanten folgendermaÿen zu G hinzufügt: Man verbinde jeden Knoten von G1 mit jedem Knoten von G2 durch eine Kante.

b) Man zeige, dass H keine Eulersche Linie besitzt.

c) Man zeige, dass H im Fall n >= 2 immer einen Hamiltonschen Kreis besitzt.

wie gehe ich diese aufgabe an? ich weiss dass mir der knotengrad helfen könnte aber kann ich den bestimmen?

verwirrt

verwirrt

dies ist die letzte aufgabe an der ich einfach nicht weiter komme, für hilfe und ideen bin ich sehr dankbar.

29.11.2006, 17:36

Abakus

Auf diesen Beitrag antworten »

RE: eulersche linie, hamiltonschen kreis
Den Hamiltonschen Kreis in c) musst du konstruktiv angeben (Zick-Zack-Lauf zwischen den Graphen ist eine Idee). Mit etwas Probieren, wie du alle Ecken verbindest, ist der aufzufinden.

Zur Eulersch in b) solltest du einige Überlegungen zu Knotengraden anstellen (welcher Zusammenhang besteht da zu Eulersch ?). Zeige, dass es mindestens einen Knoten mit ungeradem Grad gibt.

Grüße Abakus smile

smile

29.11.2006, 20:34

informatikmaus

Auf diesen Beitrag antworten »

RE: eulersche linie, hamiltonschen kreis
zu b) ich habe ja gar keinen graphen an dem es es ausprobieren kann. ich muss es ja allgemein for H zeigen...

zu c) ich weiss dasmir knotengrade helfen können, aber wie zeige ich das es einen konoten mit ungeredem grad gibt?

was zu machen ist weiss ich, ich habe nun das problem es umzusetzen und komme alleine nicht weiter unglücklich

unglücklich

29.11.2006, 20:59

Abakus

Auf diesen Beitrag antworten »

RE: eulersche linie, hamiltonschen kreis

Zitat:

Original von informatikmaus
zu b) ich habe ja gar keinen graphen an dem es es ausprobieren kann. ich muss es ja allgemein for H zeigen...

Du hast einen sehr speziellen Graphen, der hat ja bestimmte Eigenschaften. Was weißt du über die Knotengrade der ehemaligen Knoten aus $\begin{eqnarray*} G_1 \text{ oder } G_2 \end{eqnarray*}$ ?

Formuliere auch erstmal, was dir das überhaupt hilft bzw. wie der Zusammenhang zwischen eulersch und Knotengraden aussieht.

Zitat:

zu c) ich weiss dasmir knotengrade helfen können, aber wie zeige ich das es einen konoten mit ungeredem grad gibt?

Das sollst du bei Teil b) zeigen. Hier ist die Idee ein "Zickzack-Weg".

Grüße Abakus smile

smile

29.11.2006, 21:14

informatikmaus

Auf diesen Beitrag antworten »

ok, G_1 ist ein vollständiger graph, ich weiss aber nichts über die knotengrade in ihm. G_2 ist ein Baum, und ein baum kann mehrere ungerade knotengrae haben. ich weiss also auch nicht wie viele.

ein graph ist dann eulersch, wenn der grad aller knoten gerade ist.

ich müsste nur zeigen, dass dies nicht stimmt.

aber wie? ich weiss ja nicht wie viele gerade knoten der baum hatte, die nach dem verbinden ungerade geworden sind? aber ich weiss ja eben nicht ob er überhaupt einen geraden grad an ainem knoten hatte, sie könnten ja auch alle ungerade sein???

29.11.2006, 21:28

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von informatikmaus
ok, G_1 ist ein vollständiger graph, ich weiss aber nichts über die knotengrade in ihm.

Was bedeutet es, wenn $\begin{eqnarray*} G_1 \end{eqnarray*}$ vollständig ist ? Wieviele Kanten gehen demnach von jedem Knoten aus ?

Zitat:

G_2 ist ein Baum, und ein baum kann mehrere ungerade knotengrae haben. ich weiss also auch nicht wie viele.

Ja, stimmt. Du kannst aber sagen, wieviele Kanten $\begin{eqnarray*} G_2 \end{eqnarray*}$ insgesamt hat.

Zitat:

ein graph ist dann eulersch, wenn der grad aller knoten gerade ist.

ich müsste nur zeigen, dass dies nicht stimmt.

Genau. Das ist die Grundlage, auf der der Beweis aufgebaut wird.

Betrachte nun einen beliebigen Knoten aus $\begin{eqnarray*} G_1 \end{eqnarray*}$ im neu gebildeten Graphen. Du weißt, wieviele Kanten von dem Knoten in $\begin{eqnarray*} G_1 \end{eqnarray*}$ ausgehen, jetzt kommt eine bestimmte Anzahl durch die Verbindungen zu $\begin{eqnarray*} G_2 \end{eqnarray*}$ hinzu. Wieviele sind es insgesamt ?

Grüße Abakus smile

smile

Anzeige

29.11.2006, 21:37

informatikmaus

Auf diesen Beitrag antworten »

Betrachte nun einen beliebigen Knoten aus $\begin{eqnarray*} G_1 \end{eqnarray*}$ im neu gebildeten Graphen. Du weißt, wieviele Kanten von dem Knoten in $\begin{eqnarray*} G_1 \end{eqnarray*}$ ausgehen, jetzt kommt eine bestimmte Anzahl durch die Verbindungen zu $\begin{eqnarray*} G_2 \end{eqnarray*}$ hinzu. Wieviele sind es insgesamt ?

... der graph H zusammengesetzt aus G_1 und G_2 hat

3n^2+n-2 alles durch 2 Kanten.

kann ich hier sehen ob die anzahl gerade, ungerade ist?

29.11.2006, 21:44

Abakus

Auf diesen Beitrag antworten »

Ja, soviele Kanten gibt es insgesamt. Ich wollte jetzt jedoch nur auf einen speziellen Knoten in $\begin{eqnarray*} G_1 \end{eqnarray*}$ hinaus, nennen wir den mal $\begin{eqnarray*} a \end{eqnarray*}$ .

Wieviele Kanten gehen von $\begin{eqnarray*} a \end{eqnarray*}$ in $\begin{eqnarray*} G_1 \end{eqnarray*}$ aus und wieviele Kanten kommen neu dazu, weil $\begin{eqnarray*} a \end{eqnarray*}$ mit allen Knoten von $\begin{eqnarray*} G_2 \end{eqnarray*}$ verbunden wird ?

Grüße Abakus smile

smile

29.11.2006, 22:00

informatikmaus

Auf diesen Beitrag antworten »

ok...

G_1 hat n(n-1) alles durch 2 Kanten

und G_2 hat n-1 Kanten, die dann dazu kommen ...

29.11.2006, 22:06

Abakus

Auf diesen Beitrag antworten »

Also die Kantenanzahlen der beiden Graphen hast du jetzt. Die Kanten, die durch die Verbindung dazu kommen, entstehen daraus, dass jeder Knoten des einen Graphen mit jedem Knoten des anderen verbunden wird. Wieviele Kanten durch diese Verbindung dazu kommen, weißt du auch.

Aber ich möchte nun einen festen Knoten $\begin{eqnarray*} a \in G_1 \end{eqnarray*}$ betrachten. Was passiert bei diesem Knoten ?

Grüße Abakus smile

smile

29.11.2006, 22:21

informatikmaus

Auf diesen Beitrag antworten »

ein bestimmter knoten bekommt eine Kante und (n-1) Kanten dazu

29.11.2006, 22:29

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von informatikmaus
ein bestimmter knoten bekommt eine Kante und (n-1) Kanten dazu

Also $\begin{eqnarray*} G_1 \end{eqnarray*}$ ist erstmal vollständig, d.h. von $\begin{eqnarray*} a \end{eqnarray*}$ gehen (n-1) Kanten aus, die $\begin{eqnarray*} a \end{eqnarray*}$ mit den anderen Knoten von $\begin{eqnarray*} G_1 \end{eqnarray*}$ verbinden.
Jetzt wird $\begin{eqnarray*} a \end{eqnarray*}$ noch mit jedem der n Knoten aus $\begin{eqnarray*} G_2 \end{eqnarray*}$ verbunden, macht weitere n Kanten.

Jetzt musst du noch zusammenzählen und erhälst dann den Grad von $\begin{eqnarray*} a \end{eqnarray*}$ . Wenn der ungerade wäre, würde das ja passen ?

Grüße Abakus smile

smile

29.11.2006, 22:38

informatikmaus

Auf diesen Beitrag antworten »

das wären dann 2n-1 ... richtig? und das ist ja immer ungerade richtig?

29.11.2006, 23:01

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von informatikmaus
das wären dann 2n-1 ... richtig? und das ist ja immer ungerade richtig?

Genau

Freude

. Damit hast du den einen Teil.

Jetzt noch zu dem "Zick-Zack"-Weg in c). Wegen der Vollständigkeit von $\begin{eqnarray*} G_1 \end{eqnarray*}$ gibt es dort einen Hamiltonschen Kreis. Jetzt kannst du jede Kante in diesem Kreis durch 2 Kanten ersetzen (schwierig es verbal zu beschreiben).

Du hast den Weg $\begin{eqnarray*} a_1 a_2 a_3 ... \end{eqnarray*}$ . Daraus machst du jetzt: $\begin{eqnarray*} a_1 b_1 a_2 b_2 a_3 ... \end{eqnarray*}$ .

Die $\begin{eqnarray*} b_i \end{eqnarray*}$ sind dabei die Knoten von $\begin{eqnarray*} G_2 \end{eqnarray*}$ . Wieso solche Kanten existieren, musst du dann überlegen.

Grüße Abakus smile

smile

29.11.2006, 23:10

informatikmaus

Auf diesen Beitrag antworten »

ok G_1 und G_2 sind ja zwei zusammenhangskomponenten und somit schon verbunden, also können wir von a_1 zu b_1 gehen, und weil in H jeder punkt von G_1 mit jeden punkt von G_2 durch eine kante verbunden wurde gehen wir auf dieser kante von b_1 zu a_2 und von a_2 wieder zu b_2 ...

ist der gedanke richtig? und wie schreibe ich sowas mathematisch auf?

29.11.2006, 23:21

Abakus

Auf diesen Beitrag antworten »

Ja, das ist die Idee. Eure Notation von Wegen kenne ich nicht, die müsstest du wissen. Einige machen eckige Klammern oder was es da sonst noch gibt.

Jedenfalls musst du dir einen solchen Hamilton-Weg in $\begin{eqnarray*} G_1 \end{eqnarray*}$ konkret hernehmen und den erweiterst du dann mit den Knoten aus $\begin{eqnarray*} G_2 \end{eqnarray*}$ .

H ist selbst zusammenhängend, d.h. es gibt nur eine Zusammenhangskomponente von H. Die Begründung, wieso du von jedem Knoten von $\begin{eqnarray*} G_1 \end{eqnarray*}$ nach jedem von $\begin{eqnarray*} G_2 \end{eqnarray*}$ kommst, ist, dass die verbunden worden sind.

Grüße Abakus smile

smile

29.11.2006, 23:40

informatikmaus

Auf diesen Beitrag antworten »

das ist mein problem. wir haben das nie wirklich mit einem weg gemacht, wir haben immer nur über den hamitonschen kreis geredet. und andere diffinitionen verwendet.

ich denke ich werde diese aufgabe auslassen und mir morgen in der übungsgruppe anschauen was ich da hätte genau zeigen müssen.

vielen dank für deine hilfe. mir ist jetzt sehr viel klar geworden smile

smile

30.11.2006, 00:00

Abakus

Auf diesen Beitrag antworten »

Indem du einen Hamiltonschen Kreis konkret angibst, zeigst du, dass es mindestens einen gibt.

Wenn ihr keine richtige Notation hattet, nimm $\begin{eqnarray*} [a_1, a_2, ..., a_n, a_1] \end{eqnarray*}$ als Notation für einen solchen Hamiltonkreis (du gibst die Kantenfolge damit an). Jetzt die $\begin{eqnarray*} b_i \end{eqnarray*}$ 's dazwischen schreiben mit einer Begründung und fertig.

Grüße Abakus smile

smile

30.11.2006, 00:05

informatikmaus

Auf diesen Beitrag antworten »

ok werde das mal so versuchen. macht ja alles sinn.

also $\begin{eqnarray*} [a_1, b_1 a_2, b_2 ..., a_n, b_n a_1, b_1] \end{eqnarray*}$ ?

30.11.2006, 00:21

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von informatikmaus
also $\begin{eqnarray*} [a_1, b_1 a_2, b_2 ..., a_n, b_n a_1, b_1] \end{eqnarray*}$ ?

Ja, bis auf das letzte $\begin{eqnarray*} b_1 \end{eqnarray*}$ , das ist zuviel. Bei $\begin{eqnarray*} a_1 \end{eqnarray*}$ (das letzte jetzt) hast du deine Rundreise ja bereits beendet.

Grüße Abakus smile

smile

30.11.2006, 00:28

informatikmaus

Auf diesen Beitrag antworten »

ok danke

smile

ich wünsche dir noch eine gute nacht.

vielen vielen dank Gott

Gott

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »