drzewo rozpinające

tece · Post autor: **tece** » 13 kwie 2008, o 14:19

czy ścieżka pomiędzy parą wierzchołków w minimalnym drzewie rozpinającym jest najkrótszą ścieżką pomiędzy tymi wierzchołkami w całym grafie? podaj dowód lub kontrprzykład

z góry dziękuję za pomoc

UNIX_admin · Post autor: **UNIX_admin** » 14 kwie 2008, o 09:12

oczywiscie nie. rozpatrz np graf bedacy cyklem.

PS. nie bardzo wiem co rozumiesz pod pojeciem minimalne drzewo rozpinajace, wiec moze chodzi co wagi, a nie dlugosci sciezek

tece · Post autor: **tece** » 14 kwie 2008, o 09:42

zadanie bylo tak sformulowane ale chyba masz racje ze chodzi o wagi bo przeciez MST znajdujemy np. algorytmem Prima w ktorym wlasnie wagi bierze sie pod uwage. moglbys podac jakis przyklad grafu bedacego cyklem jako kontrprzyklad dla tego zadania?

[ Dodano: 14 Kwietnia 2008, 17:54 ]
ok juz wymyslilem
dziekuje za pomoc