MST beweisen

Aufrufe: 404     Aktiv: 17.01.2021 um 10:08
0

Hallo zusammen

Hab wirklich Mühe solche Aufgaben zu lösen. Wie geht man bei solchen Aufgaben vor?

Vielen Dank!

 

Schöne Grüsse

Sayuri

Diese Frage melden
gefragt

Student, Punkte: 205

 
Kommentar schreiben
1 Antwort
0

Hallo sayuri,

es steht ja da, finde ein Gegenbeispiel, so dass e weder im minimalen noch maximalen Spannbaum liegt. Dafür kann man sich ein einfaches Beispiel konstruieren.
Welche Kanten zwischen Knoten werden bei der Bildung des Spannbaums nicht berücksichtigt?

Hilft das? 

Diese Antwort melden
geantwortet

Punkte: 8.29K

 
Hmm...ein Gegenbeispiel, ist eine diagonale zwischen min und max ST?   ─   sayuri 15.01.2021 um 21:09
was ich meine ist eigentlich wenn du einen Graphen mit mehreren Zusammenhangskomponenten konstruiert hast, also angenommen zwei Knoten mit einer Kante dazwischen wobei diese Knoten weder von der senke aus erreichbar sind noch die quelle erreichen können, dann liegt diese Kante in keinem Spannbaum ... macht das Sinn o.O?   ─   maqu 15.01.2021 um 22:46
sorry, für die späte Antwort! Jupp, nun macht es Sinn!   ─   sayuri 17.01.2021 um 10:08

Kommentar schreiben