Gráfelmélet

A Wikipédiából, a szabad enciklopédiából
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.

Alapfogalmak[szerkesztés | forrásszöveg szerkesztése]

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 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 pontok 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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

A Hamilton-kör egy, a gráf minden csúcsán pontosan egyszer áthaladó kör.[1] 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 | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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

Kromatikus szám[szerkesztés | forrásszöveg szerkesztése]

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.

négyszín-tétel, kromatikus polinom, Hadwiger-sejtés,

Út[szerkesztés | forrásszöveg szerkesztése]

É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[szerkesztés | forrásszöveg szerkesztése]

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

Ramsey-elmélet[szerkesztés | forrásszöveg szerkesztése]

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

A tétel[szerkesztés | forrásszöveg szerkesztése]

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ősHajnalPósa illetve NešetřilRödl igazolták.


Extremális gráfelmélet[szerkesztés | forrásszöveg szerkesztése]

Véletlen gráfok[szerkesztés | forrásszöveg szerkesztése]

Mikor van kör a gráfban?[szerkesztés | forrásszöveg szerkesztése]

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?[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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

Források[szerkesztés | forrásszöveg szerkesztése]

  1. Lovász László: Kombinatorikai problémák és feladatok. 21-27. old. Typotex Kiadó, 2008. ISBN 978-963-9664-93-7