Feladat: 2.8.
Legyen
G egy izolált pont nélküli gráf. Ki akarunk választani minimális számú élt, amelyek együttesen lefedik a gráf összes pontját, tehát keresünk egy minimális lefedő élrendszert. A következő ,,mohó algoritmust" alkalmazzuk:
Minimális lefedő élrendszert kereső algoritmus.
Kezdetben
E - a lefedő élek rendszere - üres,
V - a lefedendő pontok halmaza - a gráf összes pontja.
A CIKLUS a következő: Keresünk egy olyan élt, amely
V két pontja között fut. Azaz sorra vesszük
V pontjait, amíg nem találunk kettőt, amelyeket él köt össze. Ha van ilyen, hozzávesszük
E-hez és két végpontját elhagyjuk
V-ből. Ha
V pontjai között már nem fut él, akkor kiválasztjuk
V soron jövő pontját, keresünk egy belőle induló élt (ilyen van, mert nincs izolált pont a gráfban), ezt hozzávesszük
E-hez, a pontot pedig elhagyjuk
V-ből.
Ha ezzel
V kiürül, akkor vége az eljárásnak. Ha nem, akkor előlről kezdjük a CIKLUSt.
a) Mutassunk példát arra, hogy ez az algoritmus nem optimális.
b) Bizonyítsuk be, hogy az algoritmus szuboptimális.
Segítség, útmutatás: 2.8
a) Keressünk kis gráfot, amelyre az algoritmus nem optimális.
b) Amikor az algoritmus olyan
V ponthalmazhoz jut, amelyben nem fut él, akkor ezeket egyesével fedi le - ám ezeket a pontokat a minimális lefedő élrendszer is köteles egyesével lefedni, hiszen
V pontjai között nem fut él.