Graph und Baum aufgabe

Question

Gegeben ist der Graph mit Knotenmenge $$[x_1,x_2,x_3,\ldots,x_6]$$ und mit Kantenmenge:

$$\{[x_1,x_2], [x_1,x_3], [x_1,x_4], [x_1,x_5], [x_1,x_6], [x_2,x_3], [x_2,x_6], [x_3,x_4], [x_4,x_5], [x_5,x_6]\}$$

1: Erstelle Adjezenzmatrix

2: Ist der Graph planar?

3: Gibt es einen Eulerschen Kreis oder Weg

4: Bestimme alle minimalen Spannbäume bezüglich der Gewichtsfunktion gegeben
durch:

$$w([x_1,x_2])=1, w([x_1,x_3])=2, w([x_1,x_4])=1, w([x_1,x_5])=3, w([x_1,x_6])=5$$

$$w([x_2,x_3])=2, w([x_2,x_6])=4, w([x_3,x_4])=2, w([x_4,x_5])=4, w([x_5,x_6])=5$$

Es ist planar? Die Kanten überkreuzen sich nicht?

Kann mir jemand erklären was ein Eulerscher Weg und Kreis ist, und was ist  ein Unterschied dazwischen?

4: Was soll ich hier machen?

Answer 1

Du kannst die minimale Spannbäume finden, indem du den Algorithmus von Kruskal anwendest.


Hier ist ein Link von Wikipedia: https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal