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ógéptudomá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

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

Összefüggőség

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 élszá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),
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.

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

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

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

Kromatikus szám

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

Síkbarajzolhatóság

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

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.

Véletlen gráfok

Mikor van kör a gráfban?

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.

Mikor van út a gráfban?

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

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