Komplexität von Algorithmen, Satz 31
Channel: ThI Videos
Date: 31/03/2021

In diesem Video definieren wir Multigraphen und Eulerkreise, schauen uns kurz das Königsberger Brückenproblem an, betrachten Spannbäume sowie Schränken MinTSP weiter ein.
Diese neue MinMTSP-Variante besitzt einen 2-Approximationsalgorithmus (genannt TreeTSP), den wir analysieren.


0:00 Definition: Multigraph, Eulerpfad, Eulerkreis
2:54 Definition: gewichteter Graph, (minimaler) Spannbaum
4:18 Problem: MinMTSP
5:43 Satz 31
6:10 TreeTSP am Beispiel
8:06 TreeTSP formal und Beweis von Satz 31