Nájdenie stromu krku s minimálnou hrúbkou fľaše - algoritmus, strom, teória grafov, minimálna veľkosť stromu

Ahoj, tak ja robím nejaké test prep a potrebujem zistiť časti b a c. Viem, že časť a je pravda a môžem to dokázať, ale nájdenie algoritmov pre časť b a c je v súčasnosti obchádzané mnou.

Vyriešte nasledovné pre minimálny strom prekážokkde sa okraj s maximálnymi nákladmi označuje ako prekážka. a) Existuje minimálne prekážka rozkladanie stromu G minimálny strom stromu G? Dokážte svoj nárok.

(b) Pre danú cenu c dajte algoritmus O (n + m) -time zistiť, či náklady na úzke miesta v minimálnom úzkych miestach G nie je väčšie ako c.

(c) Nájdite algoritmus na nájdenie minimálnej prekážky spanning stromu G.

ďakujem vopred každému, kto mi môže pomôcť

odpovede:

2 pre odpoveď č. 1

pre (B):

Vymažte každú hranu G to stojí viac ako C, potom skontrolujte, či je ľavý graf stále pripojený.

pre (C):

Vykonajte binárne vyhľadávanie C, pomocou algoritmu, ktorý vyriešil (b) ako delenie.

Dôkaz (B):

Povedzme, že graf, ktorý sme dostali po odstránení okrajov, stáli viac ako C z G je G " , potom:

1. ak G " je pripojený, potom musí existovať spanning strom T v G ", Vzhľadom k tomu, žiadny okraj v G " náklady viac ako C, môžeme s istotou povedať, že žiadny okraj v T náklady viac ako C, teda T je pre strom G " a tiež G ktorého hrdlo fľaše je najviac C
2. ak G " nie je pripojený, potom nie je žiadny spanning strom v G " vôbec. Pretože poznáme každý okraj G- G " náklady viac ako C, a vieme, že každý spanning stromu G bude obsahovať aspoň jeden okraj G- G ", preto vieme, že tam nie je okraj spanning stromu G ktorých hrdlo fľaše <= C

A samozrejme zisťuje, či je pripojený graf, náklady O (n + m)

Dôkaz (C):

Povedz, algoritmus, ktorý sme použili (B) je F (G, c) .

Potom to máme

ak F (G, c) = pravdivý pre niektoré C, potom F (G, c ") = pravdivý pre všetkých c " ktoré majú c "> = c

ak F (G, c) = nepravdivý pre niektoré C, potom F (G, c ") = nepravdivý pre všetkých c " ktoré majú c "<= c

Takže môžeme binárne vyhľadávať C :)

---

1 pre odpoveď č. 2

Ans. a)False,every minimum bottleneck spanning tree of graph G is not a minimum spanning tree of G.

b)To check whether the value of minimum bottleneck spanning tree is atmost c,you can apply depth first search by selecting any vertex from the set of vertices in graph G.

***Algorithm:***


check_atmostvalue(Graph G,int c)
{

for each vertex v belongs to V[G] do {
visited[v]=false;
}

DFS(v,c); //v is any randomly choosen vertex in Graph G
for each vertex v belongs to V[G] do {
if(visited[v]==false) then
return false;
}
return true;
}



DFS(v,c)
{
visited[v]=true;

for each w adjacent to v do {
if(visited[w]=false and weight(v,w)<=c) then
DFS(w,c);
}
visited[w]=true;
}


This algorithm works in O(V+E) in the worst case as running timr for depth first search DFS is O(V+E).

---

0 pre odpoveď č. 3

Tento problém možno vyriešiť jednoduchým nájdením MST grafu. Toto vychádza z nasledujúceho tvrdenia:
MST je MBST pre pripojený graf.
Pre MST vyberte maximálnu hranu e v MSTa okraj e rozdeľuje MST na dve sady S a T. Potom z vlastností rezu musí byť hranou e minimálna hmotnosť medzi týmito okrajmi, ktoré spájajú S a T.
Potom pre MBST, musí existovať nejaké okraje e ", ktoré spojujú S a T. Potom w (e") nesmie byť menšia ako w (e). Takže vieme, že MST musí byť MBST.

Existuje však ďalší spôsob, ako určiťminimálne prekážky. Nie je potrebné počítať s MBST.V tvojej otázke skutočne predpokladáte monototnosť minimálnej prekážky.Preto môžeme použiť binárne vyhľadávanie v kombinácii s algoritmom pripojenia na nájdenie minimálnej krčnej fľaše.Mám tu vidieť použitie monocity v ostatné prípady som trochu ohromený, že podobná technika môže byť použitá tu!

---