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

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

Matrix A

$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.

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

Matrix B

$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.

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