Schmieder László: Gráfalgoritmusok 1.

A gráfok sok hétköznapi probléma szemléltetésére és vizsgálatára alkalmasak. Ezekben a feladatokban a gráfok csúcsai például egy elemet, helyet, állapotot jelölnek, míg a gráf élei az egyes elemek közötti kapcsolatot, az állapotok közötti átmenetet mutatják. ábrázolhatjuk például gráffal egy terület úthálózatát, ahol a csúcsok a városoknak és a közlekedési csomópontoknak felelnek meg, míg az utak az éleknek. Alkalmazhatjuk a gráfokat a sakkjáték menetének leírására is: a kezdőállásból elérhető összes állásnak megfeleltetünk egy-egy csúcsot, míg a szabályos lépéseknek a csúcsok közötti irányított éleket.

A KöMaL idei informatika pontversenyében kitűzött I/S. 1. feladat is megoldható egy gráfban útvonal keresésével. A feladatban az a kérdés, hogy egy fémlap A és B csatlakozási pontja között vezető marad-e azok után, hogy belőle körlap alakú területeket eltávolítottunk. A megoldáshoz készítsünk egy gráfot, amelynek csúcsai a körök középpontjai, valamint a lemezen kívül a csatlakozási pontokat nem tartalmazó oldalak mellett egy-egy pont. A gráfban legyen él azon csúcsok között, amelyek körei érintik vagy metszik egymást, illetve a körök és a lemezen kívüli pontok között, ha a kör érinti vagy metszi a fémlemez megfelelő oldalát. Ha van útvonal a gráfban a felső és alsó fémlapon kívüli csúcsok között, akkor nem lehet összeköttetés a fémlap A és B oldala között - és megfordítva.

A kérdés eldöntése tehát azt igényli, hogy keressünk utat a gráf két lemezen kívüli csúcsa között. Ha kézzel, ceruzával kellene megoldani a feladatot egy papírra rajzolt gráfnál, akkor feltehetőleg megoldanánk a problémát; egy kisebb gráfon ránézésre, egy nagyobb gráfon némi ügyességgel. Ha az útkeresést egy számítógép végzi (mert pl. rendkívül nagy és bonyolult a gráf), akkor egy olyan műveletsorozatot kell megadnunk a számára, amely tetszőleges gráfon elvezet a kiinduló csúcstól a célba, vagy megadja, hogy a cél nem elérhető. Ez utóbbi választ persze csak akkor adhatja, ha a kiinduló csúcsból elérhető összes csúcsot már megvizsgálta, és azok között nem volt a cél.

A folytatás a lapban olvasható.