Feladat: 2.5.
Az előző (
2.4.) feladat megoldásában láttuk, hogy a független ponthalmaz kiválasztásához használt ,,mohó algoritmus" - a fokszám felső korlátjára tett kikötés mellett - bizonyos értelemben a legjobbat adja, annyi független pontot választ ki, amennyinél többet általában nem tudunk garantálni. Mutassunk példát olyan gráfra, amelyiknél ez a ,,mohó algoritmus" nem feltétlenül a legnagyobb független ponthalmazt választja ki.
Segítség, útmutatás: 2.5
Használjuk ki, hogy a
2.4. feladat megoldásában használt ,,mohó algoritmus" kimenetele attól is függ, hogy milyen sorrendben jönnek sorra az egyes pontok. Nagyon egyszerű gráfokra érdemes gondolni!