„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
| 194. sor: | 194. sor: | ||
# Most az AB élt adjuk hozzá, ez alapján <math>y \ge 1</math>. | # Most az AB élt adjuk hozzá, ez alapján <math>y \ge 1</math>. | ||
# Most a BC élt adjuk hozzá, ez alapján <math>y \ge 3</math>, így végül <math>y \ge 3</math>. | # Most a BC élt adjuk hozzá, ez alapján <math>y \ge 3</math>, így végül <math>y \ge 3</math>. | ||
$$$ Észrevétel/kérdés $$$ | |||
Nem vagyok nagy algel tudós, de miért ne lehetne y>=1? Tudomásom szerint, a Prim az mindig a legkisebb olyan élt veszi be ami olyan csúcsba visz ami eddig nem volt a halmazba. Ha pedig nincs igazam, akkor meg y>=2 mivel (AE) súlya 2 és akkor azt kellene, (ha csak a sulyok szerint növekvőt nézzük. | |||
$$$$$$ | |||
'''b)''' Kruskal algoritmus - Éleket nagyság szerint sorrendbe rakjuk, és növekvő sorrendben felvesszük a fához az éleket, vigyázva, hogy ne csináljunk kört. | '''b)''' Kruskal algoritmus - Éleket nagyság szerint sorrendbe rakjuk, és növekvő sorrendben felvesszük a fához az éleket, vigyázva, hogy ne csináljunk kört. | ||