Új szócikk írása

Szöveg:

<p><font size="2">- rendeljünk egy gráf éleihez súlyokat, nemnegatív valós számokat<br /></font><font size="2">- jelöljük <em>s(e)</em>-vel az e-hez rendelt súlyt<br /></font><font size="2">- adjunk algoritmust, amely megkeresi a minimális súlyú feszítőerdőt G-ben</font></p><p><font size="2">- <u>algoritmus [Kruskal]</u>: </font></p><br /><blockquote dir="ltr" style="margin-right: 0px"><p><font size="2">- az éleket egyesével választjuk ki a következők szerint<br /></font><font size="2">- először válasszuk ki a gráfból a legkisebb súlyú élek egyikét<br /></font><font size="2">- tegyük fel, hogy már kiválasztottunk néhány élet<br /></font><font size="2">- ekkor válasszuk a legkisebb súlyú olyan élek egyikét, amely nem alkot kört az eddig már </font><font size="2">kiválasztottakkal<br /></font><font size="2">- ha ilyen nincs, megállunk, ha van, akkor ezt az eljárást ismételjük</font></p></blockquote><p><font size="2">- a Kruskal algoritmus nyilván egy mohó algoritmus a legkisebb súlyú feszítőerdő megkeresésére</font></p><p><font size="2">- a mohó algoritmus azonban más feladatok, pl. a legkisebb súlyú kör megkeresésére vagy páros gráfban a max. </font><font size="2">párosítás megkeresése esetén nem feltétlenül ad jó megoldást</font></p>

Neved: