Gráf

Címkézett gráf 6 csúccsal és 7 éllel

Irányított gráf

A gráf a matematikai gráfelmélet és a számítógéptudomány egyik alapvető fogalma. A gráf dolgok (csomópontok, csúcsok) és rajtuk értelmezett összeköttetések (élek) halmaza. Egy gráfot megadhatunk csúcsainak és éleinek felsorolásával, vagy szemléletesebben egy diagram formájában, ahol a pontok felelnek meg a gráf csúcsainak, az őket összekötő ívek pedig az éleknek. A két megadási mód ekvivalens, azaz a gráf pusztán egy struktúra, semmilyen megjelenítési információt nem tartalmaz, így különböző diagramok is tartozhatnak ugyanahhoz a gráfhoz.

Alapértelmezésben a gráf irányítatlan, azaz nem teszünk különbséget „A-ból B-be”, illetve „B-ből A-ba” menő élek között. Ezzel szemben az irányított gráfokban (angolosan: digráf) a két iránynak irányított élek felelnek meg.

Szintén alapértelmezésben, a gráf csúcsai címkézettek, azaz meg lehet különböztetni őket. Bizonyos problémák azonban könnyebben kezelhetők, ha nem különböztetjük meg a csúcspontokat. Persze egy-egy csúcspont így is megkülönböztethető maradhat egyéb jellemzőik alapján, mint pl. a vele szomszédos csúcsok száma. Hasonlóan, a gráf élei alapértelmezésben címkézettek, de előfordulhat hogy ezt nem követeljük meg. Az olyan gráfok amikben sem a csúcspontok, sem az élek nem címkézettek, címkézetlen gráfok. Megjegyzés: a „címkézés” szó más kontextusban is elfordul a gráfoknál, itt most az élek-csúcsok megkülönböztetésére szolgáló címkékkel foglalkoztunk.

Motiváció

A gráf általános definíciója megengedi, hogy tetszőleges szándékolt jelentést tulajdonítsunk a csúcsoknak és éleknek, ez lehetővé tette elterjedését a matematikán kívül is (számítógéptudomány, szociológia stb.). Rengeteg érdekes és szép gráfelméleti tétel és algoritmus született egy-egy valós életbeli problémára adott válaszként. Általában absztrakt gráfokkal foglalkozunk, azaz megfeledkezünk a hozzá társított jelentésről, ezt tükrözi a szóhasználat is.

Alapfogalmak

A gráf két élét szomszédosnak nevezzük, ha van egy közös csúcspontjuk. Hasonlóan, két csúcspont szomszédos, ha van egy közös élük, másként fogalmazva egy éllel vannak összekötve. Egy séta szomszédos csúcsok és élek váltakozó sorozata. Az önmagát nem metsző sétát útnak hívunk, ha első és utolsó csúcsa különbözik, illetve körnek, ha ez a két csúcs megegyezik. Egy gráf összefüggő, ha (élei esetleges irányításáról megfeledkezve) bármely két csúcs között van út.

Az ún. súlyozott gráfban (ami lehet irányított gráf is), minden élhez hozzárendelünk egy értéket, ami az él költsége, súlya vagy hossza az alkalmazástól függően. Az ilyen gráfok sok helyen előfordulnak, például optimalizálási feladatokban, mint az utazó ügynök probléma.

Példák gráfok alkalmazására

Nevezetes séták

Tudunk-e olyan sétát tenni a gráf élein, hogy

• minden élen pontosan egyszer megyünk végig? (lásd: Königsbergi hidak, Euler kör)
• minden csúcsot pontosan egyszer érintünk? (lásd: Hamilton út)

Bár a két kérdés hasonlónak tűnik, az első megválaszolására van gyors (lineáris idejű) algoritmus (néha a diagram alapján ránézésre is eldönthető), míg a második az egyik ismert legnehezebb probléma (NP-teljes).

Legrövidebb utak

Súlyozott gráfban:

Melyik a legrövidebb (legkisebb összsúlyú) út A-ból B-be?

Például, ha egy valódi úthálózatban, ahol a csúcsok a csomópontok, az élek az útszakaszok, és A-ból B-be szeretnénk eljutni, de a különböző lehetséges utak nem egyformán kedvezőek, van rövidebb (gyorsabb, olcsóbb), akkor az élekhez az éleknek megfelelő hosszt (időtartamot, árat) rendelve, a válasz a számunkra legkedvezőbb út.

Súlyozott gráf a minimális feszítő fájával (piros)

Minimális feszítő fa

Súlyozott gráfban:

Válasszunk ki néhány élet úgy, hogy a gráf még összefüggő maradjon, de az élek összsúlya minimális legyen!

Egy létesítendő (víz-, csatorna-, számítógép-) hálózattal szemben az az elvárás, hogy ha nem is közvetlenül, de minden csomópontot kössön össze és olcsó legyen kiépíteni. A feladatot leírhatjuk egy súlyozott gráffal, melynek csúcsai a csomópontok, egy él felel meg egy lehetséges hálózati szakasznak, a kiépítési költségével súlyozva. Könnyen belátható, hogy ha a szakaszok nincsenek ingyen, akkor az így kapott legolcsóbb hálózat(ok)ban nem lesz kör (hiszen a kör egyik élét büntetlenül elhagyhatnánk). Az ilyen (összefüggő, körmentes) gráfokat hívják fáknak.

Egy legalább 7 egység végrehajtási idejű terv a kritikus úttal (piros)

Irányított gráf, benne irányított kör (piros)

Feladatütemezés

Nemnegatív étékekkel súlyozott irányított gráfban:

Milyen hosszú a leghosszabb út A-ból B-be?

Egy projekt megszervezésénél, a különböző munkafázisokat általában nem lehet egymástól függetelenül végrehajtani. Tegyük fel, hogy a betartandó szabályok csak arra vonatkoznak, hogy egyes munkafázisok meg kell előzzenek másokat adott idővel. Természetesen adódik a kérdés, hogy lehetséges-e egyáltalán az összes szabály betartása, és ha igen mikor ér leghamarabb véget a projekt? A problémához készíthetünk egy súlyozott, irányított gráfot, melyben a csúcsok a munkafázisoknak, az irányított élek a betartandó szabályoknak felelnek meg. (Például egy építkezési szabálynak megfelelő él a gráfban: {alap betonozás} –(8)→ {falazás}, azaz a két esemény között legalább 8 napnak kell eltelnie.) Ha ebben a gráfban van irányított kör az biztosan patthelyzethez vezet, hiszen ekkor néhány munkafázis közvetve a saját befejeződésére várna, ekkor nincs olyan végrehajtási sorrend, mely a szabályoknak eleget tenne. Megmutatható, hogy ha a gráf körmentes, akkor a feladat mindig megoldható. Hogy legkorábban mikorra készül el a projekt, azt egy leghosszabb út(ak) hossza árulja el, amelyeket hívnak kritikus utaknak is. A leggyorsabb befejezéshez tartozó ütemezés megtalálására van gyors (polinom idejű) algoritmus, melynek általánosabb szabályokra is felkészített változatait sok üzleti szoftver (projektmenedzsment) is tartalmazza. (lásd: PERT módszer)

Párosítás (piros) páros gráfban

Párosítások

Irányítatlan gráfban egy él két csúcsot állít párba.

Legfeljebb hány csúcsot tudunk egyszerre párba állítani, ha minden csúcs legfeljebb egy párhoz tartozhat?

Ez a kérdés például akkor is, ha egy csapat tagjainak akarunk egy-egy önálló feladatot kiosztani, úgy hogy a lehető legtöbb feladat legyen kiosztva. A gráf csúcsai a feladatok és az emberek, és egy élet akkor húzunk be, ha az illető el tudja végezni a feladatot. Vegyük észre, hogy a gráf csúcsai két olyan tartományra oszlanak (emberek és feladatok), amelyeken belül nem megy él. Az ilyen gráfok páros gráfnak hívjuk. (lásd: Párosítás páros gráfban)

3 színnel színezett egyszerű gráf, kevesebb szín használata már azonos színű szomszédokat eredményezne

Színezések

Egyszerű gráfban:

Legkevesebb hány szín kell a csúcsok kiszínezéséshez, ha a szomszédosak nem lehetnek egyszínűek?

Ezzel a feladattal szembesülünk például egy politikai térkép színezésénél. A csúcsok az országok, az élek a közös határral rendelkező országok között futnak. A természetes térképekből ilyen módon kapott gráfoknak megvan az a szép tulajdonságuk, hogy lerajzolhatóak élkeresztezések nélkül a síkba. (→síkgráf) Egy diák figyelt fel rá, hogy akármilyen bonyolult térképet is választ, négy szín mindig elegendő volt a megfelelő színezéshez. Nagyon sokáig nyitott probléma volt, hogy ez mindig lehetséges-e, de végül megszületett a négyszín-tétel. A csúcsok minél kevesebb színnel színezése általános gráfokban továbbra is nehéz feladat.

További problémák

• Hálózati folyamok

Definíciók

Irányítatlan gráf

A G irányítatlan gráfot a G=(V, E) rendezett párral jellemezzük, ahol

• V a csúcsok halmaza (melyről általában feltesszük, hogy véges) és
• E az irányítatlan éleknek megfelelő csúcsok rendezetlen párjainak halmaza.

Az e={u, v} élről azt mondjuk, hogy u és v között fut, összeköti u-t és v-t.

Irányított gráf

A ${\overrightarrow {G}}=(V,{\overrightarrow {E}})$ irányított gráf:

• ${\overrightarrow {E}}$ az irányított élek végpontjai rendezett párjának halmaza

Az e=(u, v) élről azt mondjuk, hogy u-ból és v-be megy, v az u közvetlen leszármazottja (gyereke), u a v közvetlen őse (szülője).

Ha egy irányított gráf nem tartalmaz irányított kört, akkor DAG-nak ('directed acyclic graph' = irányított körmentes gráf) hívjuk.

Vegyes gráf

A vegyes gráfot a G:= (V,E,A) hármassal lehet meghatározni, ahol V a csúcsok halmaza, E és A pedig az irányított éleknek megfelelő csúcsok rendezett, illetve az irányítatlan éleknek megfelelő csúcsok rendezetlen párjainak halmazai.

Általánosítások

Multigráf, benne hurokél (kék) és többszörös élek (piros)

• A hurokél olyan él, amelynek mindkét végpontja megegyezik.
• A gráfokban megengedhetünk többszörös- vagy párhuzamos éleket, melyek végpontjai megegyeznek. Ehhez az élek halmazát multihalmazra, vagy más többszöri előfordulást lehetővé tevő struktúrára kell cserélnünk. Az olyan gráfot, amiben a többszörös élek (és esetleg a hurokélek) megengedettek, multigráfnak vagy pszeudográfnak hívjuk.
• Az olyan gráfokat amelyekben sem többszörös élek, sem hurokélek nincsenek egyszerű gráfnak hívjuk. Ekkor E valódi halmaz és $E\subset {V \choose 2}$.
• Néha olyan gráfokat is megengednek, amiben olyan élek is vannak, amiknek csak egy végük van „fél-él”, vagy egy csúcshoz sem kapcsolódnak „szabad él”, pl. az előjeles gráfoknál.

• Hipergráf - a hipergráfban egy él kettőnél több csúcspontot is összeköthet.
• Végtelen gráf

• Egy irányítatlan gráf felfogható simplicial complexnek (szimpliciális komplexus), ami 1-simplexekből (élekből) és 0-simplexekből (csúcspontokból) áll. Ilyen értelemben ezek a complexek a gráfok általánosításai, mert magasabb dimenziójú simplexeket is tartalmazhatnak.
• Minden gráfból felírható egy matroid (pontosabban: grafikus matroid), de általában a gráfot nem lehet visszaállítani a matroidjából, ezért a matroidok nem valódi általánosításai a gráfoknak.

Lényeges gráfok

Teljes gráfok

					...
K1	K2	K3	K4	K5
					...
	P2	P3	P4	P5
					...
		C3	C4	C5

Teljes páros gráfok

			...
K1,1	K1,2	K1,3
			...
K2,1	K2,2	K2,3
			...
K3,1	K3,2	K3,3

Alapvető gráfok:

• Teljes gráfok ($K_{n}$)
• Utak ($P_{n}$)
• Körök ($C_{n}$)
• Páros gráfok ($G=(A,B;E)$)
• Teljes páros gráfok ($K_{n,m}$)
• Fák
• Erdők

Bonyolultabb gráfosztályok:

• Síkgráfok
• Perfekt gráfok
• Reguláris gráfok

Híres gráfok:

• Petersen gráf
• Grötzsch gráf
• Kuratowski gráfok
• Mycielski gráfok
• Fibonacci fák

Gráfokon értelmezett műveletek

Több olyan művelet ismert, ami gráfokon értelmezett és gráfokat eredményez.

Unáris műveletek

• Élgráf (az a gráf, amiben a csúcspontok az eredeti gráf élei, és viszont)
• Duális gráf
• Komplementer gráf

Bináris műveletek

• Gráfok Descartes-szorzata
• Gráfok tenzorszorzata
• Gráfok erős szorzata
• Gráfok lexikografikus szorzata
• Gráfok zig-zag szorzata