hallo kann mir wer bei der klausuraufgabe vom 12.2.2003
Nr 4 helfen?? blicke da nich wirklcih durch…

Gegebensei ein Graph Gn für n =< 2 mit der Knotenmenge aller n-Tupel (x1,x2,…,xn) mit xi aus der Menge M={0,-1,1}, die an genau einer Stelle einen Eintrag /=0 haben. Zwei Knoten sind genau dann mit einer kante verbunden, wenn der Eintrag /= 0 an verschiedenen stellen ist.

a) wieviele knoten hat Gn?
b) hat Gn eine eulersche Linie?
c) wieviele Kanten hat Gn?


ich scheitere leider schon daran dass ich mir das gar nich vorstellen kann wie das aussieht… und das tut mir ein großes problem machen..
kann mir vielleicht wer helfen?
danke
…

Gegebensei ein Graph Gn für n =< 2 mit der Knotenmenge aller n-Tupel (x1,x2,…,xn) mit xi aus der Menge M={0,-1,1}, die an genau einer Stelle einen Eintrag /=0 haben. Zwei Knoten sind genau dann mit einer kante verbunden, wenn der Eintrag /= 0 an verschiedenen stellen ist.

n >= 2 wars, oder? Ansonsten waers trivial.

ich scheitere leider schon daran dass ich mir das gar nich vorstellen kann wie das aussieht… und das tut mir ein großes problem machen..

Beispielsweise besteht der Graph G_3 aus:
(0,0,1) (0,0,-1)
(0,1,0) (0,-1,0)
(1,0,0) (-1,0,0)
Davon ist im Prinzip jeder mit jedem verbunden, AUSSER denen, die in der gleichen Zeile stehen.

a) wieviele knoten hat Gn?

2n

b) hat Gn eine eulersche Linie?

Was war das noch?

c) wieviele Kanten hat Gn?

Wir haben 2n Knoten. Von denen ist jeder mit jedem Knoten verbunden, ausser mit sich selber und mit seinem Partner. Also 2n * (2n-2) ? Nein, denn jede Kante hat ja 2 Enden, also muss das noch halbiert werden, es gibt also 2n(n-1) Kanten.

Zeichne einfach mal den Graphen z.B. fuer n=4. Ist dann zwar nur ein Beispiel ohne Allgemeingueltigkeit, aber hilft beim Klarmachen.

Fuer n=3 (Ich bin mal faul :-) sind die Knoten der Vorschrift nach 3-Tupel aus der Menge {0,1,-1}. Und zwar all jene, die an genau einer Stelle (von den drei Stellen des Tupels) ungleich 0 ist.

Also die Menge der Knoten fuer n=3:
V = {(0,0,1),(0,0,-1),(0,1,0),(0,-1,0),(1,0,0),(-1,0,0)}

Welche werden nun verbunden? Genau die, die an unterschiedlicher Stelle (von den 3 Stellen des 3-Tupels) ihren 0-ungleichen Eintrag haben. Also z.B. (0,0,1) ist verbunden mit (0,1,0),(0,-1,0),(1,0,0),(-1,0,0). Hat also Grad = 4.

Male es dir auf fuer Beispiele, bis du wenigstens den Aufbau verstanden hast. Ich habe in der Klausur auch recht lange an der sprachlichen Beschreibung herumgeraetselt, bis ich es hatte. Dann war die Beantwortung der Fragen allerdings sehr einfach.

edit: Argh, der war schneller :-)
edit2: Eine Eulersche Linie hat ein Graph genau dann, wenn der Grad jedes Knotens gerade ist. Steht im roten Skript.

danke!!!