``Nagy'' független halmaz keresésére természetesen adódik a mohó módszer.
Mohó algoritmus:
Input: G egyszerű gráf.
Beállítások:
Legyen F az üres halmaz, A az inputgráf.
% F egy független halmaz, amleyet algoritmusunk folyamatosan bővíteni próbál.
% A az aktuális gráf, amelyet folyamatosan ritkítunk azokkal a csúcsokkal,
amelyek már nem lényegesek algoritmusunk szempontjából.
Választási lépés:
Válasszunk ki egy v csúcsot A gráfunkból.
Bővítési lépés:
F-hez adjuk hozzá a kiválasztott v csúcsot.
Csonkítási lépés:
A-ból dobjuk el v-t és szomszédait.
Ha A üres (nincs csúcspontja), akkor álljunk le, F az algoritmusunk outputja.
Ha A nem üres, akkor a választási lépéshez térjünk vissza.
Az algoritmus futása során a választási, bővítési, csonkítási lépések hármasa ismétlődik periodikusan. Egy ilyen hármast az algoritmus egy fázisának nevezzük. A következő lemma az algoritmus analízisét adja.
Lemma:
Legyen t a mohó algoritmus által kiszámított független ponthalmaz elemszáma.
t>= |V(G)|/(D(G)+1),
ahol D(G) a gráf maximális fokszáma.
Bizonyítás: t a fázisok száma. Minden fázsi során legfeljebb D(G)+1 csúcsot hagyunk el. Mivel a |V(G)| csúcsot ``kimerítjük'' ezért legálabb |V(G)|/(D(G)+1) fázisunknak kell lenni.
Az algoritmusunk gyengesége abban rejlik, hogy az F-be beválasztandó csúcs kiválasztásáról semmit sem mond, ``hasra ütéssel'' történik. Célunk minél több fázis elérése, azaz mindig minél kisebb csonkítás. Így természetes a heurisztika: mindig a legkisebb fokú csúcsot válasszuk.
Módosított mohó algoritmus:
Input: G egyszerű gráf.
Beállítások:
Legyen F az üres halmaz, A az inputgráf.
% F egy független halmaz, amleyet algoritmusunk folyamatosan bővíteni próbál.
% A az aktuális gráf, amelyet folyamatosan ritkítunk azokkal a csúcsokkal,
amelyek már nem lényegesek algoritmusunk szempontjából.
Választási lépés:
Válasszuk ki az egyik minimális fokú v csúcsot A gráfunkból.
Bővítési lépés:
F-hez adjuk hozzá a kiválasztott v csúcsot.
Csonkítási lépés:
A-ból dobjuk el v-t és szomszédait.
Ha A üres (nincs csúcspontja), akkor álljunk le, F az algoritmusunk outputja.
Ha A nem üres, akkor a választási lépéshez térjünk vissza.
Tétel:
Legyen t a módosított
mohó algoritmus által kiszámított független ponthalmaz elemszáma.
t>= |V(G)|/(d-(G)+1),
ahol d-(G) a gráf átlag fokszáma, azaz 2|E(G)|/|V(G)|.
Bizonyítás: Legyen v1, v2, v3, ... , vt-1, vt az output elemei, kiválasztásuk sorrendjében. Legyen d1, d2, d3, ... , dt-1, dt a kiválasztott csúcsok fokszáma kiválasztásukkor.
Azaz az i-edik fázis során egy csúcsot választunk ki, di+1
csúcsot dobunk el. Hány él elhagyása történik ekkor? Legyen A a
vi csúcs kiválasztásakor meglévő aktuális gráf. Legyen U a
vi csúcs és szomszédainak halmaza, azaz az i-edik fázisban
elhagyott csúcsok halmaza. Az U-beli csúcsok A-beli fokainak összege
legalább (di+1)di, hiszen összegünk egy
di+1 tagú összeg, amely minden tagja (vi
választása miatt) legalább di. Másrészt ez az összeg
megadja az U-n belüli élek számának dupláját és az U, illetve
V(A)-U közötti éleket egyszeresen számolva. Azaz az eredmény nem
haladja meg az elhagyott élek (az U-n belüli és U, illetve V(G)-U
közötti élek) számának dupláját. Akét eresmény összevetéséből kapjuk, hogy
az i-edik fázsiban elhagyott élek ei számára teljesül, hogy
ei>=(di+1)di/2=(di+12).
Fázisaink elfogyasztják G-t így di+1 számok összege |V(G)|, (di+12) számok összege legfeljebb |E(G)|. A Jensen-egyenlőtlenséget a (x2)=x(x-1)/2 konkáv függvényre alkalmazva kapjuk, hogy a (di+12) számok átlaga legalább annyit ad mint ha a di+1 számok átlagát helyettesítjük a (x2)=(x2+x)/2 konkáv függvénybe. A di+1 számok átlaga |V(G)|/t. Azaz |E(G)|/t >=|V(G)|/t (|V(G)|/t-1)/2. Rendezés adja a bizonyítandót.
A bizonyítás során fontos eredményt értünk el. Érdemes ezt külön megfogalmaznunk.
Lemma: Ha G-n futtatva a módosított mohó algoritmust t elemű független halmazhoz jutunk, akkor |V(G)|-t felírhatjuk t darab ei pozitív egész összegeként úgy, hogy a (ei2) számok összege legfeljebb |E(G)| legyen.