TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 287

Aus VoWi
Zur Navigation springen Zur Suche springen

Welche der nachstehenden Adjazenzmatrizen stellt einen Baum dar?

A = \begin{pmatrix}
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 \\
\end{pmatrix}

B = \begin{pmatrix}
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 \\
\end{pmatrix}

Lösungsvorschlag von mnemetz[Bearbeiten]

Anmerkung: Die hier dargestellten Graphen enthalten Fehler. Beide Matrizen stellen ungerichtete Graphen da, im Gegensatz zu den hier dargestellten gerichteten Graphen.

Matrix A[Bearbeiten]

A = \begin{pmatrix}
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 1 & 1 \\
0 & 1 & 0 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 \\
\end{pmatrix}

Wir müssen überprüfen, ob der durch die Adjazenzmatrix repräsentierte Graph zusammenhängend ist.

Bsp179 1.png

Der Graph ist zusammenhängend, jedoch existiert ein Kreis => der vorliegende Graph ist kein Baum!

Anmerkung: Um festzustellen, dass A kein Baum ist, kann man eine spur schneller verfahren, indem man sieht, dass die Anzahl der Kanten = der Anzahl der Knoten ist. Damit ist eine Vorraussetzung für einen Baum verletzt: \alpha _0(T) = \alpha _1(T) + 1

Matrix B[Bearbeiten]

B = \begin{pmatrix}
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & 0 \\
\end{pmatrix}

Wir müssen überprüfen, ob der durch die Adjazenzmatrix repräsentierte Graph zusammenhängend ist.

Bsp179 2.png

Der Graph ist zusammenhängend, also stellt die Adjazenzmatrix einen Baum dar!

  edit: - von b geht eine Kante nach c zuruck 
        - f->c und nicht umgekehrt

anmerkung: für alle, die das auch verwirrend finden: es steht glaub ich nirgends, dass der Graph gerichtet ist, also sind die Kanten von und zu a/f,... eigentlich nur eine ungerichtete Kante. Ansonsten wäre das ja auch schon ein Kreis (bzw. Zyklus)