2. FEJEZET: A ,,mohó algoritmus''
A fejezet még fejlesztés alatt áll.
A fejezet témájához kapcsolódik Surányi László:
Algoritmusok a középiskolában: a mohó algoritmus című cikke [
175].
Feladat: 2.1. (M)
Egy baráti összejövetelen
n házaspár vett részt,
n>2. Bármely három házaspár közül vagy a három asszony, vagy a három férj ismerte egymást.
Elhelyezhetők-e a házaspárok két teremben úgy, hogy az egyik teremben az asszonyok, a másik teremben a férfiak mind ismerik egymást? (Arany Dániel-verseny, 1982H)
Feladat: 2.2. (SM)
Bevezetjük a következő definíciókat:
Definíció. Egy algoritmust
optimálisnak nevezünk, ha minden esetben talál egy keresett tulajdonságú és optimális (minimális vagy maximális) elemszámú ponthalmazt.
Szubotpimálisnak nevezzük, ha optimális elemszámút nem talál, de a feladat méretétől független konstansszorosát talál.
Bizonyítsuk be, hogy a
K.II.13.23. feladat megoldásában használt - egyébként végső soron ,,mohó algoritmusnak" tekinthető - algoritmus szuboptimális.
Feladat: 2.3. (SM)
Mutassuk meg, hogy az alábbi, egy gráf maximális elemszámú független élrendszerét kereső algoritmus nem optimális, de szuboptimális.
Független éleket kereső algoritmus.
Kezdetben
V és
K üres,
G a gráf összes élét tartalmazza.
A CIKLUS a következő: kiválasztunk
G-ből egy élt elhagyjuk
G-ből és áttesszük
V-be. Az összes olyan élt, amelynek van közös végpontja ezzel az éllel, a ,,kukába" dobjuk, azaz
K-ba tesszük. Ha marad még él a gráfban, előlről kezdjük a ciklust, ha nem, akkor a kiválasztott élek a gráf egy független élrendszerét alkotják.
Feladat: 2.4. (SM)
Legalább mekkora független ponthalmazt tudunk garantálni egy
n pontú egyszerű gráfban, amelyben minden pont foka legfeljebb
d?
Vagyis: melyik az a legnagyobb
m szám, amelyre igaz, hogy ha egy
n pontú egyszerű gráfban minden pont foka legfeljebb
d, akkor van benne
m pontú független ponthalmaz?
Feladat: 2.5. (SM)
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.
Feladat: 2.6. (SM)
Módosítsuk a
2.4. feladat megoldásában használt ,,mohó algoritmust" annyiban, hogy a maradó gráfból mindig a(z egyik) legkisebb fokú pontot vesszük. Az új algoritmus tehát a következő:
Módosított független ponthalmazt kereső algoritmus.
Kezdetben legyen
V is,
K is az üres halmaz,
G az adott gráf.
A CIKLUS a következő: Ha
G üres, akkor az eljárásnak vége,
V a talált független ponthalmaz. Ha
G nem üres, akkor válasszuk ki
G egy minimális fokú
x pontját és vegyük hozzá
V-hez, a(z aktuális
G-beli) szomszédait tegyük hozzá
K-hoz (a többi már ott van, mert
V független ponthalmaz és
G és
V között nem fut él). Az új
G-t pedig úgy kapjuk, hogy
G-ből elhagyjuk
x-et és szomszédait. Ezután előlről kezdjük a ciklust.
Az eljárás nyilván véget ér, ha
G véges gráf, és az is világos, hogy
V a gráf egy független ponthalmazát adja meg. Az előző -
2.5. - feladat megoldásában adott ellenpélda most nem működik.
Igaz-e, hogy ez a módosított algoritmus mindig egy maximális pontszámú független ponthalmazt talál meg?
Feladat: 2.7. (SM)
Döntsük el a
2.6. feladatban definiált algoritmusról, hogy szuboptimális-e.
Feladat: 2.8. (SM)
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.
Feladat: 2.9.
A minimális lefedő élrendszert kereső algoritmusunkat (l. a
2.8. feladatot) megpróbálhatjuk úgy javítani, hogy ha ,,felesleges" éleket is kiválasztott, akkor azokat elhagyjuk. Vagyis az ottani algoritmust kibővítjük egy lépéssel:
Sorra vesszük
E éleit, és ha találunk egy
e élt, amelynek mindkét végpontját lefedi
E többi éle, akkor ezt az
e élt elhagyjuk
E-ből. Ha nem találunk ilyet, akkor befejezzük az eljárást.
Optimális-e az így kiegészített algoritmus?
Feladat: 2.10. (M)
Egy véges gráfban minden pont foka
≤d. Bizonyítsuk be, hogy a gráf
d+1 színnel jólszínezhető.
Kiszínezhető-e mindig
d színnel is?
Igaz-e az állítás (megszámlálhatóan) végtelen gráfra is?