Különóra

Matematika

Mi az a gráfelmélet?

Gráfok: pontok és vonalak katyvaszának tűnnek, ám rengeteg matematikai, informatikai, sőt, pszichológiai problémát képesek vagyunk megoldani segítségükkel. Elsőre elég elméleti feladatnak tűnhet a gráfok használata, ám a közösségi média és az internet maga is leírható velük. De hogy jönnek ide egy oroszországi város hídjai?

Gráfnak nevezzük pontoknak és éleknek a halmazát, ahol az élek pontokat kötnek össze, illetve az élekre pontok illeszkednek úgy, hogy minden élre legalább egy, legfeljebb két pont illeszkedik. Ez elsőre elég bonyolultan hangzik, de mindjárt megmagyarázzuk, hogyan is kell elképzelni a dolgot.

A gráfok problémájának története egy 19. századi elméletre vezethető vissza: Königsbergben (ma Kalinyingrád) hét híd ívelt át a várost átszelő folyón úgy, hogy ezek a folyó két szigetét is érintették. A helyiek azzal a kérdéssel fordultak Leonhard Euler matamatikushoz, hogy lehetséges-e végigmenni a város összes hídján úgy, hogy mindegyiken csak egyszer haladjanak át, és egyúttal visszaérjünk a kiindulópontba.

Euler a problémát a gráfok nyelvén oldotta meg, a szárazföldeket pontokra, hidakat pedig élekre egyszerűsítette le. Bebizonyította, hogy a hidakat lehetetlenség úgy bejárni, hogy a kiindulópontba érkezzünk vissza, és mindegyiken csak egyszer haladjunk át. A hidakon pontosan egyszer végighaladó séta akkor lenne lehetséges, ha minden csomópont fokszáma páros lenne, ám mivel ebben az esetben a fokszámok összege páratlan szám, így a séta nem lehetséges.

Mi az a gráfelmélet?

 

Ezt a példát tartjuk a történelem első gráfelméleti problémájának. Azóta sok fejlemény történt a gráfelmélettel kapcsolatban, a matematikusok több tételt, elnevezést és fogalmat is létrehoztak, ebben pedig magyar matematikusoknak is nagy érdeme van. Az első tétel szerint: bármely gráfban a fokszámok összege az élek számának kétszerese. 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ámok összeadásával lehetséges. Ebből következik a második tétel, miszerint bármely gráfban a páratlan fokszámú pontok száma páros.

Mi az a gráfelmélet?

A gráfoknak különböző elnevezései vannak. Ha két pontot több él is összeköt, azt párhuzamos élnek nevezzük. Amikor egy pontba egy él visszacsatolódik, azt hurokélnek nevezzük. Teljes gráfnak hívjuk azt, amikor minden pont össze van kötve egymással. Az egy struktúrájú gráfokat összefüggő gráfnak, míg a szétválasztott struktúrájú gráfokat nem összefüggő gráfoknak nevezzük.