Gráfelmélet kedvcsináló kezdőknek

A gráfelmélet a matematika egyik legizgalmasabb és talán a legegyszerűbben megérthető területe. Gyakorlati alkalmazása azonban nagy bonyolultságú rendszerek megértését képes segíteni. A cikk célja hogy a területtel most ismerkedők egy kis inspirációt kapjanak.

A gráfelmélet története napjainkig

A gráfelmélet a svájci Euler nevéhez kapcsolódik, és egészen 1736-ig nyúlik vissza a története. A kezdeti gráfelméleti kutatások nem voltak kifejezetten komolynak mondhatók, akkor még nem igazán volt gyakorlati haszna az alkalmazásának. Mindenesetre remek rejtvények készültek az elmélet segítségével.

Az idő múlásával azonban egyre több felhasználási módja keletkezett a matematikai elméletnek. A 19. százdban már elektromos hálózatok, illetve molekuláris hálózatok körében is alkalmaztak gráfokat.

Napjainkban a gráfelmélet már sokkal átfogóbb tudományterület. Segítségével olyan összetett problémákat oldanak meg, mint a csővezeték-rendszerek áramlási problémái, vagy a logisztikai kihívások, útvonaltervezés. Tipikus, internetes alkalmazása a weboldalak linkhálózatának feltérképezése is, amit többek között a Google keresőmotorja is felhasznál (azonban ennek pontos módját sajnos nem ismerjük).

Mi a gráf?

Nemes egyszerűséggel a gráfok olyan pontokból és azokat összekötő vonalakból álló alakzatok, melyek valamilyen információt hordoznak (ez nem a matematikai megfogalmazás, inkább csak a saját értelmezésem).

Mire jó a gráfelmélet?

A legegyszerűbb példa, melyet Oystein Ore- A gráfok és alkalmazásaik című könyvében találunk a következő:

Az iskolai futballcsapat más iskolák csapataival együtt bajnokságon vesz részt. Összesen hat csapat indul, mindegyiküket egy betűvel jelöljük, így lesznek A, B, C, D, E és F csapatok. A verseny első néhány hetében már néhányan játszottak egymással de még közel sem mindenki mindenkivel. A meccseket itt gráfokkal jelölhetjük.

Gráf feladatok megoldással

a) Értelmezd a Gráfot

A fenti példában leírt állapotot tehát gráf segítségével követjük, ami így néz ki:

Gráf feladatok megoldással

Feladat! Írd le hogy melyik csapat kivel játszott már!

Egy kis segítség – A D betűjelű csapat játszott a legtöbb ellenféllel!

b) Szögpontok és élek

A gráfok tehát pontokból és vonalakból állnak. Viszont ezek nem túl elegáns megnevezések. A pontokat szögpontnak, a vonalakat pedig éleknek nevezzük.

Feladat! Határozd meg hány éle és szögpontja van a fenti gráfnak

c) Rajzolj te is gráfot

A gráfelmélet legalapvetőbb részével eddigre készen vagy, most használd ki ezt a tudást. A feladat az előbbi focis példa alapján:

A versenyidény az utolsó részéhez érkezett. Rajzold meg a gráfot a csapatokról a következő információk alapján:

  • Az E csapat kivételével minden csapat játszott már legalább 3 másikkal.
  • A D csapat már játszott mindenkivel
  • Az A csapat nem játszott a F-el és az E-vel
  • Az F csapat pontosan 4 csapattal játszott

Források a gráfelméleti tudásom mélyítéséhez

 

Javasolj te is forrásanyagot hozzászólásként!

 

Vélemény, hozzászólás?

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük

Ez a weboldal az Akismet szolgáltatását használja a spam kiszűrésére. Tudjunk meg többet arról, hogyan dolgozzák fel a hozzászólásunk adatait..