Gráfok

Gráfok, avagy hogyan haladjunk át Königsberg hídjain? Königsberg városa (mai nevén Kalinyingrád, Oroszország) a Pregel folyó partján és szigetein épült. A 18. században a városnak hét hídja volt. A város lakói találós kérdésként vetették fel azt a problémát, hogy lehet-e úgy sétát tervezni, hogy ha valaki elindul otthonról, és pontosan egyszer átmegy a város mindegyik hídján, akkor visszatér az otthonába. A problémát Leonard Euler (1707–1783) svájci matematikus oldotta meg 1736-ban írt tanulmányában.
Alapfogalmak: A gráf pontokból és élekből álló halmaz, ahol az élek pontokat kötnek össze, és minden élre legalább egy, legfeljebb két pont illeszkedik. A gráfokat legszemléletesebben sokszögekkel ábrázolhatjuk, ahol a sokszög csúcsai a gráf pontjai, a csúcsokat összekötő szakaszok – oldalélek és átlók – a gráf élei. Két pontot összeköthet egy vagy több él is. Ha két pontot egynél több él köt össze, akkor azokat párhuzamos éleknek nevezzük. Ha egy élre egy pont illeszkedik, azaz egy él két végpontja azonos, akkor azt az élt hurokélnek nevezzük. Ha egy gráfban nincsenek párhuzamos élek és nincs hurokél sem, akkor az egy egyszerű gráf. Ha egy gráfnak minden pontjából pontosan egy él vezet a gráf összes többi pontjához, akkor az teljes gráf. Egy gráfot összefüggő gráfnak nevezünk akkor, ha bármely pontjából bármely pontjába eljuthatunk valamilyen úton. Nézzük az alábbi két példát! Az első összefüggő gráf, a második nem összefüggő gráf.
Lássunk két konkrét példát, és mondjuk el a rájuk jellemző tulajdonságokat! 1. példa: Nem teljes gráf, mert nem vezet minden pontból pontosan egy él minden pontba. Nem is egyszerű gráf, mert van benne hurokél. Összefüggő gráf, mert minden pontjából eljutunk minden pontba. 2. példa: Teljes gráf, mert minden pontból pontosan egy él vezet minden pontba. Egyszerű gráf, mert nincsenek benne párhuzamos élek, és nincs benne hurokél. Összefüggő gráf, mert minden pontjából eljutunk minden pontba. Jellemzéseinket az egyszerűbb áttekinthetőség érdekében táblázatba is foglalhatjuk, ahol további tulajdonságokat is megadhatunk, pl. pontok, élek száma
A gráfok vizsgálata során megállapíthatjuk, hogy egy-egy pontba hány él fut be. A gráf egy-egy pontjába összefutó élek számát a pont fokszámának nevezzük. A fokszámokra vonatkozóan különböző megfigyeléseket, megállapításokat tehetünk. Ezeket a következő tételekben foglaljuk össze. 1. tétel: Bármely gráfban a fokszámok összege az élek számának kétszerese. Az 1. tételből logikusan következik a 2. tétel, hiszen ha a fokszámok összege páros, akkor az csak vagy páros számok, vagy páros számok és páros számú páratlan szám összeadásával lehetséges. Ezért a 2. tétel így hangzik: Bármely gráfban a páratlan fokszámú pontok száma páros. Ahhoz, hogy a bevezetőben megfogalmazott problémát meg tudjuk oldani, ismerkedjünk meg még néhány gráfokkal kapcsolatos fogalommal és állítással! Útnak nevezzük a gráf egymáshoz csatlakozó éleinek olyan sorát, amely egyetlen ponton sem halad át egynél többször. Vonalnak nevezzük a gráf egymáshoz csatlakozó éleinek olyan sorát, amelyben egyetlen él sem szerepel egynél többször. Körnek nevezzük a kezdőpontjába visszavezető utat, azaz olyan élsorozatot, amely a kezdőpontjába tér vissza, valamint minden pont és minden él csak egyszer szerepel benne. A vonalak közül azokat, amelyeknek kezdő és végpontja azonos, és amelyekben a gráfnak minden éle szerepel, Euler-vonalaknak nevezzük. Erre a 3. tétel állítása igaz: Egy összefüggő gráfnak akkor és csak akkor van Euler-vonala, ha a gráf minden pontjának fokszáma páros szám.
Ezzel el is jutottunk a feladatunk megoldásához. Ábrázoljuk a város hídjait és a szárazföldet gráffal! Jelentsék az ábra pontjai a szárazföldet (A, B, C és D pont, azaz a négy zöld terület egy-egy pont), az őket összekötő élek pedig a hidakat! Természetesen a hidak hossza, a szárazföld területe a feladat szempontjából elhanyagolható. Olyan sétát tervezünk, ahol minden hídon, azaz élen csak egyszer haladhatunk át, és visszajutunk a kiindulási pontba. Tehát Euler-vonalat keresünk. Már csak azt kell megállapítanunk, hogy az elkészített ábránk egyes pontjainak fokszáma mennyi. Figyelmesen dolgozva eljutunk a megoldáshoz, azaz hogy minden pont fokszáma páratlan: három db 3 és egy db 5 fokszámú pont van, így a kívánt séta nem valósítható meg. Ebben állt Euler zsenialitása.