„Algoritmuselmélet - ZH, 2013.04.03.” változatai közötti eltérés

@@ 96. sor: / 96. sor: @@
 ===5. Feladat===
-TODO
+Adjacencia-mátrixával adott n csúcsú, élsúlyozott, irányítatlan gráfként ismerjük egy ország úthálózatát (a csomópontok a városok, az élek a közvetlen összeköttetések a városok között). Az élek súlya a városok közti távolságot adja meg. (Feltehetjük, hogy a távolságok egészek.)
+Adjon egy O(n<sup>6</sup>) lépésszámú algoritmust, ami eldönti, hogy lehetséges-e úgy kiválasztani öt várost, hogy ezektől bármely más város legfeljebb 50 kilométerre van. ''(Ezekbe a városokba lenne érdemes hókoztrókat telepíteni.)''
 {{Rejtett
 |mutatott=<big>'''Megoldás'''</big>
 |szöveg=
+*A megoldáshoz először Floyd algoritmussal páronként meghatározzuk az összes város távolságát, ez O(n<sup>3</sup>).<br>
-TODO
+*A város irányítatlan gráfként van megadva, de ezen könnyen segíthetünk úgy, hogy a jelenlegi élek helyett felveszünk két irányítottat, azonos súllyal. Ez O(n<sup>2</sup>).<br>
+*Ezek után brute force módszerrel az összes csúcsötösre ellenőrizzük, hogy azok öten lefedik-e (legfeljebb 50 km-re vannak) az összes várost.<br>
+**n<sup>5</sup> városötös van, mindegyikre le kell ellenőrizni, hogy jók-e. Az ellenőrzés során végignézzük, az összes csúcsra (n db.), hogy el lehet-e érni. Ez tehát O(n<sup>5</sup>*n)=O(n<sup>6</sup>).<br>
+*Összességében ezért O(n<sup>6</sup>) lépésszámú az algoritmus.
 }}