TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 179

Welche der nachstehenden Adjazenzmatrizen stellt einen Baum dar?

$A=\left(\begin{array}{cccccc}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{array}\right)$

$B=\left(\begin{array}{cccccc}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{array}\right)$

Lösungsvorschlag von mnemetz

Matrix A

$A=\left(\begin{array}{cccccc}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{array}\right)$

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

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

Matrix B

$B=\left(\begin{array}{cccccc}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{array}\right)$

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

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