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 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).
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).
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.
A fenti példában leírt állapotot tehát gráf segítségével követjük, ami így néz ki:
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!
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
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:
Javasolj te is forrásanyagot hozzászólásként!
Néhány filmnek kell egy-két év, vagy egy-két évtized, hogy a szélesebb közönség is értékelni kezdje.…
A The Bricklayer egy középszerű akcióthriller, ami sokat profitál karizmatikus főszereplőjéből. (tovább…)
A Bérgyilkos klub, eredeti címén Assassin Club egy olyan feledhető és középszerű filmes trendet követ,…
Megérzés alapján A méhész producerei egy, a John Wick-franchise-zal vetélkedő univerzumot szeretnének beindítani. Ha ezt…
A One More Shot: Ostromállapot megőrizte az előző rész sajátos koncepcióját, és nagyjából a színvonalat…
A "Csendes Lány" egy igazán megrázó, érzelmi hullámvasúton végighaladó film, melynek főszereplője egy súlyosan elhanyagolt…
