Gyakorlati alkalmazás

A gráfokkal kapcsolatban sok fogalmat, elnevezést vezettünk be. Mindezek a gráfelmélet alapfogalmai. Ezek ismeretében is megoldhatunk néhány egyszerű feladatot, vagy ezeket is felhasználhatjuk összefüggések szemléltetésére, de ezekből még nem láthatjuk a gráfelmélet igazi jelentőségét.

Sokféle gazdasági feladat megoldása matematikai problémaként fogalmazható meg. Közöttük vannak olyanok is, amelyek gráfelméleti kérdésekhez vezetnek. Ilyen a következő:

Több község, például öt község között telefonhálózatot (vagy vízvezeték-hálózatot stb.) akarunk kiépíteni. A hálózatot minimális költséggel szeretnénk kialakítani.

Megtervezéséhez kiszámíthatjuk, hogy bármely két község közötti vezetéképítés mennyibe kerülne. Ezt szemléltetjük az ábrán látható gráffal. Az élek melletti számok a költségek arányát mutatják. A teljes gráf tartalmaz kört is. Tudjuk, ha egy körnek elhagyjuk valamelyik élét, akkor az új gráf összefüggő. A legnagyobb költségű élét elhagyjuk, és megnézzük, hogy az új gráfban van-e kör. Ha van, akkor megint elhagyjuk az abban legmagasabb költségű élt ... stb.

Hálózatépítés Bizonyítható, hogy az így kapott minimális költségű gráffa. (A minimális költségű fa megkeresése nem annyira egyszerű , mint ebből a pár sorból látszik, de a problémát ezzel felvázoltuk.)

Ez a példa mutatja, hogy a gráfelméleti ismeretek nagyon jól használhatók a gazdasági életben (is). Mivel gyakorlati felhasználásához kevés ismeretünk van, ezzel a problémakörrel nem foglalkozunk tovább, de azt észre kell vennünk, hogy az új problémák megoldásai új fogalmak bevezetését, új módszerek keresését kívánhatják.

Az első gráfelméleti munkának Euler 1736-ban írt tanulmányát tekinthetjük, amiről az példában olvashattunk. Az önálló tudományággá fejlődését azonban Kirchhoff nevéhez kapcsoljuk, 1847-ben megjelent munkája kapcsán. Gráfokkal kapcsolatban ettől kezdve egyre több dolgozat jelent meg. Kőnig Dénes(1884 -1944) 1936-ban megjelent könyve volt az első tudományos színvonalú gráfelméleti munka, amely két évtizeden keresztül az egyetlennek is mondható.

A kezdeti időben úgy tűnt, hogy a gráfok csupán rejtvények, játékos kérdések megválaszolására jók. A XIX. században Kirchhoff és Cayley munkái mutatták meg, hogy többről van szó. Kirchhoff elektromos hálózatokkal, Cayley kémiai vizsgálatokkal hozta kapcsolatba a gráfokat.

A térképek színezése is gráfelméleti kérdésként fogalmazható meg. Az áttekinthetőség miatt színezzük a térképeket; a közös határvonallal rendelkező országokat különböző színűre. Célszerű minél kevesebb színt használni. Mennyi lehet a minimális szín, amellyel egy gömbön vagy síkon lévő térkép színezhető? (Az országok összefüggőek.) Azt sikerült bizonyítani, hogy öt szín mindig elegendő, de elég-e négy szín? Sokáig csak sejtés volt, hogy elegendő. Nagyon sok hibás bizonyítás született erre. Volt olyan is a XIX. században, amelyikről csak egy évtized után derült ki, hogy nem jó. A kérdésre 1976-ban végleges válasz született, a sejtésből tétel lett.