Твърдение: Ако всички ръбове в графиката са различни, тогава има уникално най-кратко дърво на пътя. Или дайте убедителен аргумент, че твърдението е вярно, или дайте противопоказания.
Отговори:
1 за отговор № 1Ако имате MST тогава има уникален път отна всеки две върхове, което прави най-кратката траектория безсмислена. Предполагам, че имате предвид, че резултатът е MST. Това обаче не е вярно. Най-късите дървета на пътеките са различни от минималните дървета за същата графика и дори за същия корен. Най-късото дърво на пътя, вкоренено в върха v обикновено е резултат от прилагането на алгоритъма на Dijkstra v.
По принцип уникалността на дърветата над графиките етрудно да се повярва, освен ако не са били дадени строги изисквания (например новите тегла стават равни на старите +1). @rici даде противоположна проба с политрий структура. Ето още един пример за противоположни графики. Двете дървета са най-краткотрайните пътеки на дърветата A, Забележи, че:
- Докато и двата са най-кратките пътни дървета, общите им разходи се различават.
- И двата са дървета, но нито една от тях не е минимална.
3 за отговор № 2
Ако разбирам въпроса, правилно:
