Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Zeigen dass ein Graph planar ist & Polyederformel

Zeigen dass ein Graph planar ist & Polyederformel

Universität / Fachhochschule

Graphentheorie

Tags: Adjazenzmatrix, Gradmatrix, Graph, Graphentheorie, planar, planare Graphen, Polyederformel

anonymous

12:24 Uhr, 07.04.2015

Folgende Aufgaben:
"Stellen Sie für den durch das nebenstehende Diagram gegebenen Graphen

G = (V, E)

die Adjazenzmatrix und die Gradmatrix auf. Zeigen Sie, dass der Graph planar ist, und geben Sie die Eulersche Polyederformel für

G

an. Gibt es für

G

zwei Zeichnungen, die nicht zueinander kombinatorisch isomorph sind?"

Ich fände es schön, wenn mir jemand Stück für Stück durch die Aufgabe helfen würde. Das Diagram hab ich angehangen.

Ich habe soweit folgende Matrizen aufgestellt:
Adjazenz:

(\begin{matrix} 0 & 1 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \end{matrix})

Grad:

((3, 0, 0, 0, 0, 0), (0, 5, 0, 0, 0,0), (0, 0, 3, 0, 0, 0), (0, 0, 0, 3, 0, 0), (0, 0, 0, 0, 1, 0), (0, 0, 0, 0, 0, 3))

Ich denke die werden soweit stimmen? Ansonsten könnt ihr mich gerne korrigieren.

Bei der nächsten Teilaufgabe stecke ich dann fest. Wie kann ich hier beweisen, dass der Graph planar ist? Ich hatte mich bisschen informiert, aber werde nicht wirklich schlau daraus. Irgendwo stand dass man den Graphen so zeichnen können muss, dass sich keine Kanten überschneiden. Ist das damit bewiesen? Das klingt nicht sehr mathematisch für mich. Hab denoch mal eine Zeichnung von meinem Versuch angehangen. Hilfe?

: (

Zu der Polyederformel habe ich folgendes gefunden:

n - m + l = 2 (n

steht für Ecken,

m

für Kanten und

l

für Flächen). Wenn es nun heißt ich soll die Polyederformel angeben. Ist das in diesem Fall dann einfach

6 - 9 + 5 = 2

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

anonymous

08:11 Uhr, 14.04.2015

Hat niemand eine Hilfestellung?

anonymous

16:46 Uhr, 22.04.2015

Planarer Graph.

Reduzieren für die Lesbarkeit und dem Verständis.

(\begin{array}{rcl} . & A & B & C & D & E & F \\ A & . & 1 & 1 & 0 & 0 & 1 \\ B & . & . & 1 & 1 & 1 & 1 \\ C & . & . & . & 1 & 0 & 0 \\ D & . & . & . & . & 0 & 1 \\ E & . & . & . & . & . & 0 \\ F & . & . & . & . & . & . \end{array})

AB AC AF
BC BD BE BF
CD
DF

Reduktion Endknoten E.

(\begin{array}{rcl} . & A & B & C & D & F \\ A & . & 1 & 1 & 0 & 1 \\ B & . & . & 1 & 1 & 1 \\ C & . & . & . & 1 & 0 \\ D & . & . & . & . & 1 \\ F & . & . & . & . & . \end{array})

AB AC AF
BC BD BF
CD
DF

-------------
-..-----------
-..-....A----B----C
-..-....------------..-
-..-....-................-
-..-....-................-
-..----F------------D
--------------------

anonymous

13:43 Uhr, 23.04.2015

Könntest du mir bitte erklären wieso du diese Schritte gemacht hast und was mir das im Gesamten jetzt aussagt und auf welche Fragestellung sich das überhaupt bezieht (habe ja mehrere Teilaufgaben)? Eine reine Hintereinanderausführung von (aus meiner Sicht zufälligen) Schritten ist nicht wirklich verständlich

: (

anonymous

15:08 Uhr, 23.04.2015

Diese Schritte zeigen, dass der Graph planar ist.
(" Zeigen Sie, dass der Graph planar ist,..")

12:24, 07.04.2015
Die Adjazenz ist symmetrisch,
was bedeutet,
das eine Hälfte davon und eine Hauptdiagonale entfallen kann.

16:46, 22.04.2015
1.Matrix, vereinfachte Adjazenz.
Die Vereinfachung dient einer leichteren Lesbarkeit.

Die Kanten des Graphen werden anders dargestellt:
AB Kante zwischen A nach B,
..

Bei dieser Schreibweise hat sich E als Endknoten gezeigt.
Der kann für die weitere Betrachtung entfallen.

2.Matrix, vereinfachte Adjazenz ohne Endknoten.

Die Zeichung A----B---C ..
sollte die Planarität anschaulich zeigen.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1229810

1226703

	Status: nicht eingeloggt	Noch nicht registriert?