A feszítőfák élszámai csak az input gráf csúcsszámától
függnek, azaz azonosak. Így minimalizálás helyett
maximálizálási kérdést vetve fel ugyanahhoz a problém'ahoz
jutunk. (A maximalizálás feladata a költség helyett a súly
terminológia használatát sugallja.) Azonban ekkor a feszítőfák
helyett kereshetünk a körmentes élhalmazok között. Azaz a
maximális súlyú körmentes élhalmaz keresése ekvivalens a
minimális költségú feszítőfa problémával. Ezen átfogalmazás
előnye, hogy a Kruskal-algoritmus ennek szellemében dolgozik. Egy
körmentes élhalmazt növel. Persze a módosított probléma
megoldásához a Kruskal-algoritmust is egy kissé módosítani kell:
a rendezési lépésben az éleket a súlyuk szerinti
csökkenő sorrendbe kell rakni.
Inicializálás: Legyen A az üreshalmaz, az eddig kiválasztott élek halmaza.
Algoritmusunk ezt növeli addig, amíg egy feszítőfa élhalmazává
nem válik.
Rendezési lépés:
Rakjuk sorba az éleket költségeik szerint, a nagyobb költségű
elemek kerüljenek előre. Beválasztási lépések:
Az első nem vizsgált élre nézzünk meg, hogy A-hoz hozzáadva
körmentes élhalmazhoz jutunk-e. Ha igen, akkor növeljük A-t.
Ha nem, akkor A maradjon.
Ha még van nem vizsgált él, akkor újra végezzük el a beválasztási
lépést. Ha az összes él vizsgált, akkor álljunk le.
Az aktuális A az algoritmus outputja.
Érezhető, hogy a körmentes élhalmazok közötti optimalizálásnál
általánosabb környezetben is elmondható
az algoritmus alapötlete.
Legyen M egy lefelé zárt, nem üres halmazrendszer V felett.
M elemeit megengedett halmazoknak nevezzük.
Azaz V egy véges halmaz, M V részhalmazait tartalmazza.
M nem üres, azaz van megengedett halmaz.
Továbbá minden megengedett halmaz részei is megengedettek.
Ha V-n adott egy súlyfüggvény, akkor ez a megengedett halmazokra
(sót V összes részhalmazára) kiterjeszthető:
Egy R részhalmaz súlya elemei súlyának összege.
A maximális súlyú megengedett halmaz keresésének problémája:
Adott V, M és s súlyfüggvény V-n. Határozzuk meg
a legnagyobb súlyú megengedett halmazt.
Példa:
Minimális költségű feszítőfa probléma=maximális súlyú körmentes élhalmaz.
V=E(G), ahol G egy összefüggő gráf, M elemei a körmentes élhalmazok.
Példa:
Hozzárendelési probléma:
V=E(G), ahol G egy páros gráf,
M elemei a párosítások.
Példa:
Maximális bevételt hozó szerződéskötések problémája: V
egy G páros gráf egyik színosztálya. M azon részhalmazai V-nek,
amelyek párosítással lefedhetők. A páros gráf egyik színosztályát
(V-t) munkák/szerződések alkotják, a másikat alkalmazottak. Az élek `egy
alkalmazott teljesíteni tudja a munkát'. A c súly a
V elemeihez a velük járó profitot rendeli. Egy munka/szerződés-halmaz
megengedett, ha el tudjuk látni, azaz mindegyikhez egy alkalmazottat
rendelhetünk úgy, hogy párjával össze legyen kötve.