Haben ein Baum mit minimaler Spannweite und ein Baum mit kürzestem Pfad immer mindestens eine Kante gemeinsam?
Ich studiere Graphentheorie und habe eine Frage zum Zusammenhang zwischen Minimum Spanning Tree und Shortest Path Tree.
LassenG Sei ein ungerichteter, zusammenhängender Graph, in dem alle Kanten gewichtet sindmit unterschiedlichen Kosten. LassenT sei ein MST vonG und lassTs Sei ein Baum mit dem kürzesten Pfad für einen Knotens. SindT undTs garantiert mindestens eine Kante zu teilen?
Ich glaube, das ist nicht immer wahr, aber ich kann kein Gegenbeispiel finden. Hat jemand einen Vorschlag, wie man ein Gegenbeispiel findet?