Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Graphen zeichnen bei gegebener Valenzsequenz

Graphen zeichnen bei gegebener Valenzsequenz

Universität / Fachhochschule

Graphentheorie

Tags: Graphentheorie

jaydog aktiv_icon

19:36 Uhr, 23.08.2018

Hallo zusammen,

ich habe bei einer Aufgabe die folgende Valenzsequenz gegeben:

(7,5,4,4,4,3,1,1,1)

Ich habe bereits gezeigt, dass es sich hier um einen einfachen Graph handelt.
Nun soll ich den Graphen allerdings noch zeichnen. Wie geht man hier am besten vor?
Muss ich Havel und Hakimi rückwärts Schritt für Schritt durchgehen bis zum Ende und erhalte dann den Graphen? Oder gibt es einen einfacheren Trick?

Wenn man einfach drauf los zeichnet, findet man natürlich sehr schwer einen passenden Graphen.

Danke und Gruß

ermanus aktiv_icon

20:53 Uhr, 23.08.2018

Ich schlage dir folgende Methode vor:
Die Knoten mögen

1, \cdot, 9

heißen.
betrachte folgende Ausgangstabelle der Valenzen:

\begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ - & - & - & - & - & - & - & - & - & - \\ Z 1 : & 7 & 5 & 4 & 4 & 4 & 3 & 1 & 1 & 1 \end{array}

Nun zeichnest du den ersten Knoten

1

.
Von diesem Knoten müssen

7

Kanten zu anderen Knoten gehen.
Da die Knotengrade absteigend sortiert sind, kann man annehmen,
dass das die Knoten

2, 3, 4, 5, 6, 7, 8

sind.
Also zeichnet man sie und verbindet Knoten 1 mit diesen.
Man hat nun die 7 ersten Kanten verarbeitet und jeweils eine Kante
der Folgeknoten

2, 3, 4, 5, 6, 7, 8

.

Dies berücksichtigen wir in unserer Valenztabelle:

\begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ - & - & - & - & - & - & - & - & - & - \\ Z 1 : & 7 & 5 & 4 & 4 & 4 & 3 & 1 & 1 & 1 \\ Z 2 : & 4 & 3 & 3 & 3 & 2 & 0 & 0 & 1 \end{array}

.

Nun verbinden wir den Knoten 2 (der ja noch 4 Valenzen frei hat)
mit den 4 Folgeknoten

3, 4, 5, 6

.

Wir ziehen die verarbeiteten 4 Valenzen in unserer Tabelle ab und bekommen:

\begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ - & - & - & - & - & - & - & - & - & - \\ Z 1 : & 7 & 5 & 4 & 4 & 4 & 3 & 1 & 1 & 1 \\ Z 2 : & 4 & 3 & 3 & 3 & 2 & 0 & 0 & 1 \\ Z 3 : & 2 & 2 & 2 & 1 & 0 & 0 & 1 \end{array}

Nun verbinden wir Knoten 3 mit den beiden Nachfolgern 4 und 5:

\begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ - & - & - & - & - & - & - & - & - & - \\ Z 1 : & 7 & 5 & 4 & 4 & 4 & 3 & 1 & 1 & 1 \\ Z 2 : & 4 & 3 & 3 & 3 & 2 & 0 & 0 & 1 \\ Z 3 : & 2 & 2 & 2 & 1 & 0 & 0 & 1 \\ Z 4 : & 1 & 1 & 1 & 0 & 0 & 1 \end{array}

Schließlich verbinden wir z.B. 4 und 5 mit einander und 6 und 9 mit einander:

Fertig!

Gruß ermanus

jaydog aktiv_icon

21:55 Uhr, 23.08.2018

Super, das erscheint mir eine schnelle Lösungsvariante und spart zu dem Zeit.
Vielen Dank für deine Mühe und die ausführliche Antwort.

1 A

Schönen Abend noch,
Gruß

1436823

1436814

	Status: nicht eingeloggt	Noch nicht registriert?