Gráfelmélet

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez
Gráf

A gráfelmélet a matematika, ezen belül a kombinatorika egyik fontos ága. Kialakításához jelentős mértékben hozzájárultak a magyar kombinatorikai iskola tagjai: Kőnig Dénes, Egerváry Jenő, Erdős Pál, Gallai Tibor, Rényi Alfréd, Lovász László, Pósa Lajos.

A gráfelmélet – a lineáris algebra és a differenciálegyenletek elmélete mellett – a matematika széles körben alkalmazott ágai közé tartozik. Fontos alkalmazásai vannak a számítástudományban és az elektrotechnikában, de esetenként egyéb, váratlanabb helyeken is felmerülhet az alkalmazása (mint pl. a pszichiátria[1]).

Alapfogalmak[szerkesztés]

Irányított gráf

A gráfelmélet alapfogalma a gráf, olyan struktúra, ami csúcsokból vagy szögpontokból és élekből áll, minden él két (esetleg egybeeső) csúcs között fut. Irányított gráfok esetén ezek a csúcspárok rendezettek. Többnyire azonban gráfon irányítatlan gráfot értenek; ha a gráf irányított, azt külön jelzik. Két csúcs szomszédos, hogyha van köztük él, azaz elemei ugyanannak az élnek. Egy él összeköt két pontot, ha a pontok elemei az élnek.

Legtöbbször egyszerű gráfokkal foglalkozunk, azaz olyanokkal, amelyekben nincs hurokél (egy csúcsot önmagával összekötő él) és nincsenek párhuzamos élek sem, tehát azonos csúcsok között haladó különböző élek.

Egy G gráf részgráfja olyan gráf, ami G bizonyos csúcsaiból és azok között bizonyos éleiből áll. Ha G egyes csúcsai között haladó összes élt vesszük, akkor feszített részgráfról beszélünk.

Egy csúcspont fokszáma a rá illeszkedő élek száma. Ha ez nulla, tehát az adott csúcsra nem illeszkedik él, akkor a csúcs izolált. Véges gráfok esetén a fokszámokat összeadva páros számot kapunk, hiszen ekkor minden élt kétszer számoltunk. Ezért a páratlan fokú pontok száma mindig páros. Ha a fokszám minden csúcsra azonos, a gráf reguláris. Ha ez a közös fokszám k, akkor a gráf k-adfokú reguláris vagy k-reguláris.

Az út élek egymáshoz csatlakozó sorozata, amely egy csúcsot legfeljebb egyszer tartalmaz. A kör élek egymáshoz csatlakozó sorozata, ami záródik, tehát az utolsó és az első élnek van közös végpontja, és nincs ismétlődő csúcs. Ha csak élek ismétlődését zárjuk ki, akkor ciklusról beszélünk.

A gráfok csúcsai, élei kaphatnak különböző racionális számokat is, különböző jelentésekkel: kapacitás, súly, illetve költség.

A Petri-hálók gráfok, kétféle csúccsal.

A gráfokhoz hasonló konstrukciók a hipergráfok, melyekben az élek mérete nincs korlátozva.

Összefüggőség[szerkesztés]

Egy gráfot összefüggőnek nevezünk, ha bármely két különböző csúcsa között halad út. Egy tetszőleges gráf esetén vezessük be a következő relációt a csúcsok között: az a, b csúcsokra , ha vagy pedig halad út a és b között. Könnyen láthatóan ekvivalenciareláció. Ennek az ekvivalenciarelációnak az osztályai a gráf komponensei vagy összefüggő komponensei.

Euler-kör, Hamilton-kör[szerkesztés]

A Hamilton-kör egy, a gráf minden csúcsán pontosan egyszer áthaladó kör.[2] Létezésére vannak elégséges feltételek (Dirac-feltétel, Pósa-feltétel, Ore-feltétel, Chvátal-feltétel), de, mivel a „Van-e adott gráfban Hamilton-kör?” feladat NP-teljes, pontos feltétel megtalálása nem remélhető.

Az Euler-kör pedig egy, a gráf minden élén pontosan egyszer áthaladó kör(tehát a csúcsokon többször áthaladhatunk). Euler-feltétele irányítatlan gráfra: Akkor és csak akkor megoldható, ha a gráf minden pontja páros fokszámú. Euler-feltétele irányított gráfra kiterjesztve: Akkor és csak akkor megoldható, ha minden pont kimenő fokszáma megegyezik a bemenő fokszámmal. Euler-feltétele vegyes gráfra kiterjesztve: Akkor és csak akkor megoldható, ha minden pontra igaz: irányítatlan élszám–|kimenő fokszám–bemenő fokszám| nemnegatív és páros.

Fák[szerkesztés]

Fáknak nevezzük az összefüggő, körnélküli gráfokat. Minden összefüggő gráfnak van részgráfja, ami fa, ezek a feszítő fák. Egy n csúcsú G gráf esetén az alábbi három tulajdonságnál bármely kettőből következik a harmadik:

  1. G összefüggő,
  2. G körmentes (a körmentes gráfot erdő-nek hívják),
  3. G-nek n-1 éle van.

Az algoritmusok elméletében fontos feladat a minimális feszítő fa megtalálása, ekkor minden élhez egy pozitív valós szám (az él súlya) van hozzárendelve és olyan feszítő fát keresünk, amiben az élek össz-súlya a lehető legkisebb.

A Cayley-tétel szerint adott n csúcson pontosan fa van.

Ha egy gráf összes összefüggőségi komponense fa, akkor az erdő. Ekvivalensen, a körmentes gráfok erdők.

Irányított gráfok esetén a fák szerepét irányított körmentes gráfok, illetve fenyők veszik át.

Többszörösen összefüggő gráfok[szerkesztés]

Egy G gráf k-szorosan összefüggő (vagy k-összefüggő), ha legalább k+1 csúcsa van és k-nál kevesebb csúcsát elhagyva még mindig összefüggő marad. Egy gráf k-szorosan élösszefüggő, ha k-nál kevesebb élét elhagyva még összefüggő marad.

Menger-tétele szerint egy véges gráf pontosan akkor k-összefüggő. ha legalább k+1 csúcsa van és bármely két csúcs között megy k pontdiszjunkt út. Hasonlóan, egy véges gráf pontosan akkor k-szorosan élösszefüggő, ha bármely két csúcsa között halad k éldiszjunkt út.

Egy gráf pontosan akkor kétszeresen élösszefüggő, ha összefüggő és minden éle benne van egy körben.

Egy véges G gráf akkor és csak akkor kétszeresen élösszefüggő, ha van gráfoknak olyan sorozata, hogy az egypontú, élmentes gráf, , és minden úgy keletkezik -ből, hogy egy utat adunk hozzá, aminek csak (esetleg egybeeső) végpontjai vannak -ben. Az út állhat egyetlen élből is (fülfelbontás).

Párosítások, gráfok faktorai[szerkesztés]

Hall-tétel, Tutte-tétel, Edmonds–Gallai-felbontás

Kromatikus szám[szerkesztés]

A gráfok csúcsai és élei színezhetők, azaz osztályokba oszthatók. Az egyes csoportokat jelölhetik a színek, vagy számok.

Egy gráf jó színezése a szögpontjainak bármilyen olyan színezése, amiben összekötött csúcsok különböző színeket kapnak. Egy G gráf kromatikus száma a G jó színezéseihez szükséges színek minimális száma, jelben: .

Ha a G gráf véges, akkor, a szögpontok száma szerinti indukcióval, könnyen igazolható, hogy , ahol a maximális fokszám. Brooks tétele szerint ez -ra javítható, hacsak G valamelyik komponense nem a teljes gráf, vagy ( esetén) páratlan kör.

Egy gráf kromatikus száma lehet nagy, anélkül, hogy nagy klikkek lennének benne: Tutte 1947-ben publikálta azt a tételt, hogy minden n-re van n-kromatikus, háromszögnélküli gráf. Erre egy másik konstrukciót Mycielski adott. Erdős 1959-ben igazolta, hogy, ha s és k természetes számok, akkor van k-kromatikus gráf, amiben nincs s-nél rövidebb kör. Bizonyítása valószínűségi jellegű, nem konstruktív volt, ez volt a véletlen gráfok elméletének az egyik első nagy eredménye. Az első konstruktív példát Lovász adta. Később számos további konstruktív és nemkonstruktív példát adott Jaroslav Nešetřil és Vojtěch Rödl.

Út[szerkesztés]

Élek olyan egymáshoz csatlakozó sorozata, melyben sem él, sem pont nem fordulhat elő egynél többször.

példa

Páros gráf[szerkesztés]

Egy gráf páros, ha nincs benne páratlan hosszúságú kör. Ekvivalensen, a gráf csúcsai két halmazba oszthatók úgy, hogy az összes él a két halmaz között fut; ami pontosan azt jelenti, hogy kromatikus száma nem nagyobb, mint kettő.

Jegyezzük meg, hogy mivel a fák körmentesek, azért a fák is páros gráfok.

Síkbarajzolhatóság[szerkesztés]

gráf duálisa, Kuratowski tétele, felületre rajzolhatóság

További osztályok[szerkesztés]

Ramsey-elmélet[szerkesztés]

A Ramsey-tétel gráfokra vonatkozó speciális esete a következő:

A tétel[szerkesztés]

Ha és természetes számok, akkor van olyan (legkisebb) természetes szám, hogy a következő igaz: ha egy gráfnak csúcsa van, akkor van benne teljes k-as vagy független l-es. Továbbá

Úgy is fogalmazhatunk, hogy ha egy csúcsú teljes gráf éleit kékkel és zölddel színezzük, akkor vagy van kék színben teljes k-as, vagy van zöld színben teljes l-es.

A fenti Ramsey-tétel általánosításaként sejtette Erdős és Hajnal a következő állítást: ha G és H véges gráfok, akkor van olyan véges gráf amire igaz, hogy ha az éleit pirossal és kékkel színezzük akkor vagy van feszített G aminek minden éle piros, vagy van feszített H aminek minden éle kék. Ezt a nehéz tételt egymástól függetlenül Deuber, ErdősHajnalPósa illetve NešetřilRödl igazolták.


Részterületek[szerkesztés]

  • Algoritmikus gráfelmélet: A gráfokon működő algoritmusokkal foglalkozik. Például Dijsktra-algoritmus.
  • Kémiai gráfelmélet: Az egyik legkorábbi alkalmazás, ami molekulákat vizsgál gráfelméleti szempontból.
  • Extremális gráfelmélet: Egy adott osztályba tartozó gráfok közül melyek minimalizálnak vagy maximalizálnak egy bizonyos gráfparamétert? Egy fontos eredménye a Turán-tétel.
  • Geometriai, illetve topologikus gráfelmélet: Gráfokat ágyaznak bele geometriai és topologikus alakzatokba. Például meghatározza a síkba rajzolhatóság feltételeit.
  • Hálózatkutatás: Tapasztalati úton vizsgál különböző gráfokat, melyek különböző alkalmazási területekről származnak, mint szociológia, közgazdaság, biológia és epidemiológia. Például a betegségek terjedése és a szociális kapcsolatok. Sok hálózat kicsi világ tulajdonságú, azaz bármely két pontja között rövid az út a pontok számához képest.
  • Spektrális, más néven algebrai gráfelmélet: A gráfok szomszédsági és Laplace-mátrixának sajátértékei, sajátvektorai és karakterisztikus polinomjai és a gráftulajdonságok kapcsolatát kutatja. A nem irányított gráfok sajátértékei valósak, mivel szomszédsági mátrixuk szimmetrikus. A gráfok szomszédsági mátrixánek sajátértékei alkotják a gráf spektrumát, ami független a gráf csúcsainak sorrendjétől a mátrixban.

Kereshetők részgráfok, különböző tulajdonságok, vagy különböző paraméterek határozhatók meg, mint pontszám, élszám, minimális fokszám, a legrövidebb kör hossza, csúcsösszefüggőségi szám, élösszefüggőségi szám, ívösszefüggőségi szám, kromatikus szám, csúcsfedési szám, függetlenségi szám, vagy klikkszám. Két gráf lehet izomorf vagy automorf; ezeket bizonyos szempontból azonosnak tekintik.

A különböző tulajdonságok kapcsolatban állnak egymással. Például a csúcsösszefüggőségi szám nem lehet nagyobb, mint az élösszefüggőségi szám; ez pedig szintén nem nagyobb, mint a gráf minimális foka. Síkgráfokban a kromatikus szám nem nagyobb, mint négy; lásd négyszíntétel.

A felsorolt gráftulajdonságok egy része relatív gyorsan meghatározható, a csúcsok számának másodfokú függvényével növekvő időben. Más tulajdonságokra nem ismert hasonlóan gyors algoritmus, évtizedekbe kerülne kisebb gráfoknál is. Itt jön képbe a heurisztika, amivel értelmes közelítő megoldások nyerhetők.

Véletlen gráfok[szerkesztés]

Tétel: Ha egy egyszerű véges gráf minden pontjának foka legalább 2 akkor van kör a gráfban.

Bizonyítás: Tetszőleges pontból elindulva mivel nem futhatunk zsákutcába és véges a gráf , nem tudunk mindig újabb és újabb pontokhoz, tehát egyszer vissza fogunk jutni olyan pontba ahol már jártunk. Ekkor megtettünk egy kört.

Általánosítás: Ha egy egyszerű véges gráf minden pontjának foka legalább k, akkor van legalább k+1 pontot tartalmazó kör.

Tétel: Ha egy 2n pontú gráf minden pontjának foka legalább n, akkor a gráf összefüggő.

Tétel: Ha egy összefüggő gráf egyik olyan élét elhagyjuk, amely valamely körnek éle, akkor a gráf továbbra is összefüggő marad.

Hivatkozások[szerkesztés]

  • Hajnal Péter: Gráfelmélet, Polygon, Szeged, 1997

Források[szerkesztés]

  1. Researchers Could Help Predict People At Risk Of Schizophrenia Using New Scanning Methods
  2. Lovász László: Kombinatorikai problémák és feladatok. 21-27. old. Typotex Kiadó, 2008. ISBN 978-963-9664-93-7