Gráfelmélet

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).

Alapfogalmak

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

Gráf elvágó ponttal és híddal

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 $a\sim b$, ha $a=b$ vagy pedig halad út a és b között. Könnyen láthatóan $\sim$ ekvivalenciareláció. Ennek az ekvivalenciarelációnak az osztályai a gráf komponensei vagy összefüggő komponensei.

Euler-kör, Hamilton-kör

A Hamilton-kör egy, a gráf minden csúcsán pontosan egyszer áthaladó kör. 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él-szám–|kimenő fokszám–bemenő fokszám| nemnegatív és páros.

Fák

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, az összefüggő erdőt fának),
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 $n^{n-2}$ 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

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 $G_{0},\dots ,G_{k}$ sorozata, hogy $G_{0}$ az egypontú, élmentes gráf, $G_{k}=G$, és minden $G_{i+1}$ úgy keletkezik $G_{i}$-ből, hogy egy utat adunk hozzá, aminek csak (esetleg egybeeső) végpontjai vannak $G_{i}$-ben. Az út állhat egyetlen élből is (fülfelbontás). Egy n csúcsú teljes gráf ${\frac {n(n-1)}{2}}-(n-2)={\frac {n^{2}-3n+4}{2}}$-szörösen összefüggő. Ezt úgy láthatjuk be, hogy kivonjuk a teljes gráf élszámából azt az állapotot, amikor már éppen eggyel több élt vettünk ki a gráfból, mint amennyi kellene ahhoz, hogy összefüggő maradjon, tehát amikor egy él hozzáadásával feszítőfát kapnánk. N csúcsú gráfra $n-1$ élű a feszítőfa, így $n-2$-t kell kivonnunk a teljes gráf élszámából.

Párosítások, gráfok faktorai

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

Kromatikus szám

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: $\chi (G)$.

Ha a G gráf véges, akkor, a szögpontok száma szerinti indukcióval, könnyen igazolható, hogy $\chi (G)\leq D(G)+1$, ahol $D(G)$ a maximális fokszám. Brooks tétele szerint ez $\chi (G)\leq D(G)$-ra javítható, hacsak G valamelyik komponense nem a $K_{D(G)+1}$ teljes gráf, vagy ($D(G)=2$ 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

É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

Páros gráf

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

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

További osztályok

• Merev körű gráfok
• Perfekt gráfok
• Mágikus gráfok

Ramsey-elmélet

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

A tétel

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

$R(k,l)\leq {{k+l-2} \choose {k-1}}.$

Úgy is fogalmazhatunk, hogy ha egy $R(k,l)$ 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ős–Hajnal–Pósa illetve Nešetřil–Rödl igazolták.

Részterületek

• 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

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.

Főbb problémák

Színezés

Gráfok színezése

Ismert probléma, hogy egy térkép hány színnel színezhető ki. Feltétel, hogy a képen a szomszédos tartományok különböző színűek legyenek. Hallgatólagos feltétel az exklávék hiánya, mivel akkor megmutatható, hogy a szükséges színek száma nem korlátozható. Megjegyzendő még, hogy nem tekintünk két tartományt szomszédosnak, ha egyetlen pontban érintkeznek, mivel akkor szintén nem lehet korlátozni a szükséges színek számát. A tartományok szomszédsági relációja így síkgráfként ábrázolható. A négyszíntétel kimondja, hogy ehhez négy szín elegendő. Általában NP-teljes probléma eldönteni, hogy egy gráf kevesebb színnel színezhető-e. Feltéve, hogy igaz az P ≠ NP sejtés, nem is lehetséges hatékony algoritmus ennek eldöntésére.

Keresési probléma

Az algoritmikus gráfelmélet egy fontos problémája két hely közötti legrövidebb út megtalálása. A probléma modellezhető gráffal. A helyeket ponttal jelöljük, és éllel kötjük össze, ha van a két hely között összeköttetés. Az élekhez hozzákapcsoljuk az utak hosszát. Ezután a feladat hatékonyan megoldható például a Dijkstra-algoritmussal.

Gráfok bejárhatósága

Algoritmikusan nehéz feladat (NP-teljes) megtalálni a legrövidebb körutat (lásd az utazó ügynök probléma), melynek az összes helyet érintenie kell. Mivel a lehetséges utak száma a helyek számának faktoriálisával arányos, az összeset kipróbáló naiv algoritmus csak kis méretű feladatokra alkalmas. A közelítő algoritmusok jó körutat találnak, ami azonban nem mindig optimális. Például a Christofides-heurisztika olyan körutat talál, melynek hossza legfeljebb az optimális 1,5-szerese.

Egy Euler-kör megtalálása egyszerű, a Hierholzer-eljárás lineáris időben talál egyet, vagy kimutatja, hogy nincs. Ezzel szemben egy Hamilton-kör megtalálása NP-nehéz. A postásprobléma egy olyan legrövidebb ciklust keres, ami minden élt legalább egyszer bejár.

Összefüggőség

Az összefüggőségi probléma arra keresi a választ, hogy a gráf hányszorosan összefüggő, azaz bármely két pontja között hány út megy. Alkalmazási területe ellátási hálózatok vizsgálata a kieséssel fenyegetett útvonalakra.

Klikkprobléma

Gráf klikkekkel

A klikkprobléma klikkfedést keres, azaz a gráfot (maximális) klikkekkel próbálja lefedni. Egy klikk olyan részgráf, ami teljes gráf.

Folyamok és vágások

Ellátási hálózatok maximális kapacitását célozza. A feladat hatékonyan megoldható például Ford-Fulkerson-algoritmussal.

Párosítási probléma

Párosítás

A párosítási probléma páros gráfban minél nagyobb független élhalmazt keres. Egy élhalmaz független, ha éleinek nincs közös pontja. Hozzárendelési problémák oldhatók meg vele. Hatékony megoldási módszerek visszavezetik folyamfeladatra.

További problémák

További ismert problémák:

• Stabil halmaz keresése
• Gráf megjelenítése
• Gráfnyelvek és gráftranszformációk

Hivatkozások

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

Források

• Martin Aigner: Graphentheorie: eine Entwicklung aus dem 4-Farben-Problem. 1984 (269 Seiten).
• Daniel Bonchev, D. H. Rouvray: Chemical Graph Theory: Introduction and Fundamentals. Abacus, New York NY 1990/1991, ISBN 0-85626-454-7.
• J. Sedlacek: Einführung in die Graphentheorie. B. G. Teubner, Leipzig 1968, 1972.
• M. Nitzsche: Graphen für Einsteiger (Rund um das Haus vom Nikolaus). Vieweg, Wiesbaden 2004, ISBN 3-528-03215-4.
• R. Diestel: Graphentheorie. 3. Auflage. Springer, Heidelberg 2005, ISBN 3-540-67656-2 (online-download).
• Peter Gritzmann, René Brandenberg: Das Geheimnis des kürzesten Weges. Ein mathematisches Abenteuer. 2. Auflage. Springer, Berlin/Heidelberg 2003, ISBN 3-540-00045-3.
• Peter Tittmann: Graphentheorie. Eine anwendungsorientierte Einführung. 3. Auflage. Hanser, München 2019, ISBN 978-3-446-46052-2.

Fordítás

• Ez a szócikk részben vagy egészben a Graphentheorie című német Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.