TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 292

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

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösungsvorschlag von Friday

-- Friday 01.06.2020 11:22 (CEST)

Es wird zwar nicht explizit erwähnt, dass es sich hierbei um ungerichtete Graphen handelt, jedoch ist ein Baum laut Definition 2.23 ein schlichter ungerichteter Graph der keine Kreise positiver Länge enthält. Somit macht es nur Sinn die Adjazenzmatrizen als ungerichtete Graphen zu behandeln.

Matrix A

Graph der Matrix A

Der Graph ist zwar zusammenhängend, enthält jedoch den Kreis {f, b, d, e, c} und ist somit kein Baum.

Matrix B

Graph der Matrix B

Der Graph ist zusammenhängend und enthält keine Kreise, somit Stellt die Adjezenzmatrix einen Baum da.

Lösungsvorschlag von mnemetz

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

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!

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

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

  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)