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 például 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.

Definíció

Definíció: Adott egy A halmaz, és egy rajta értelmezett $\rho \subseteq A\times A$ bináris (kétváltozós) reláció. Ekkor a $G=\left(A,\rho \right)$ párt, vagyis az A halmaz feletti relációs struktúrát az A halmaz feletti gráfnak nevezzük.

Megjegyezzük, hogy e definíció szerint a ρ reláció rendezett elempárokból áll, azaz a gráf irányított, viszont „többszörös” éleket nem tartalmaz, azaz egyszerű.

Ezen értelmezésen belül az irányítatlan gráf fogalma úgy értelmezhető, hogy megköveteljük a ρ reláció szimmetriáját, azaz hogy érvényes legyen $\forall x,y\in A:(x,y)\in \rho \Leftrightarrow (y,x)\in \rho$, és ekkor az irányítatlan gráf az irányított gráf speciális esete.Más, filozófiailag kevésbé problematikusnak látszó, de kényelmetlenebb lehetőség is van. Ld. még irányítatlan gráf.

Definíció: Az $A$ halmazt a $G=\left(A,\rho \right)$ gráf tartóhalmazának vagy csúcshalmazának mondjuk, és (az angol „vertex”=csúcs szó rövidítéseként) $V\left(G\right)$-vel jelöljük.

A gráf itt megadott fogalmának rengeteg, nemcsak a matematika, hanem a szociológia, számítástechnika stb. fejlődése által egyenesen kikényszerített általánosítása vagy változata létezik, lásd általánosítások, speciális esetek és változatok.

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 problémája, 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 érté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üggetlenü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áfokat 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éhez, 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

Különböző kontextusokban szükség lehet arra, hogy a „gráf” kifejezést különböző általánosabb értelmezésekben használjuk. Ha fontos a különbségtétel, az alábbiakban megadott terminusokkal pontosabban meghatározható, milyen jellegű gráfról van szó. A jelenleg elterjedt gráfelméleti munkákban, ha külön nem térnek ki rá, gráf alatt általában „irányítatlan, egyszerű, véges gráfot” értenek.

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 indul é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 irányított körmentes gráfnak vagy angol nevének rövidítése szerint DAG-nak (directed acyclic graph) 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”, például 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ó szimpliciális komplexusnak, ami 1-szimplexekből (élekből) és 0-szimplexekből (csúcspontokból) áll. Ilyen értelemben ezek a komplexusok a gráfok általánosításai, mert magasabb dimenziójú szimplexeket 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 (K), utak (P), körök (C):

					…
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 két csúcs akkor van összekötve, ha az eredeti gráfban a két élnek volt közös végpontja)
• 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

Gráftopológiai fogalmak

Szülő, utód, fok

Definíció: Az $x\in V\left(G\right)$ csúcsot az $y\in V\left(G\right)$ csúcs szülőjének, míg $y$-t az $x$ utódának vagy gyermekének nevezzük a G irányított gráfban, ha $\left(x,y\right)\in \rho$.

Az x csúcs utódainak halmazát $\Gamma \left(x\right)$ szokta jelölni:

$\Gamma \left(x\right):=\left\{y\in V\left(G\right):\left(x,y\right)\in \rho \right\}$

Az x csúcs szülőinek halmazát mi úgy jelöljük majd, ${\mbox{L}}\left(x\right)$:

${\mbox{L}}\left(x\right):=\left\{y\in V\left(G\right):\left(y,x\right)\in \rho \right\}$

Az utódok számát külfoknak (vagy talán még rosszabbul hangzó kifejezéssel kifoknak) nevezik;

$od\!g(x)={\underline {dg}}(x):=\left|\Gamma \left(x\right)\right|$ (külfok)

míg a szülők számát belfoknak (befok):

$id\!g(x)={\overline {dg}}(x):=\left|{\mbox{L}}\left(x\right)\right|$ (belfok)

Definíció: Egy irányított gráf valamely csúcsát alulról izoláltnak nevezzük, ha a gráf egyik nem hurkolt élének sem kezdőpontja, azaz belőle egy másik csúcshoz sem vezet él. Azaz: $x\in \rho$ izolált, ha $\forall y\in V\left(G\right)-\left\{x\right\}:\left(x,y\right)\not \in \rho$.

Definíció: Egy gráf valamely csúcsát felülről izoláltnak nevezzük, ha a gráf egyik nem hurkolt élének sem végpontja, azaz hozzá egyik másik csúcsból sem vezet él. Azaz: $y\in \rho$ izolált, ha $\forall x\in V\left(G\right)-\left\{y\right\}:\left(x,y\right)\not \in \rho$.

Hurok, elágazás

Definíció: Az $\left(x,x\right)$ alakú éleket, azaz melyek kezdő- és végpontja egybeesik, huroknak nevezzük. Ezt az $x\in V(G)$ pontbeli huroknak mondjuk.

Ha a ρ reláció reflexív, akkor minden pontban van hurok is.

Definíció: Azt mondjuk, az $x\in V\left(G\right)$ csúcsban a gráf elágazik, ha található két (különböző) él, melyek kezdőpontja épp x. Ekkor az x pontot elágazásnak nevezzük. Ez pontosan akkor teljesül, ha
$\exists y,z\in V\left(G\right):\left(y\neq z\wedge \left(x,y\right),\left(x,z\right)\in \rho \right)$
Az elágazás valódi, ha egyik él sem hurok.

Definíció: Azt mondjuk, az $x\in V\left(G\right)$ csúcsban a gráf néhány éle összefut, ha található két (különböző) él, melyek végpontja épp x. Ekkor az x pontot csomónak nevezzük. Ez pontosan akkor teljesül, ha
$\exists y,z\in V\left(G\right):\left(y\neq z\wedge \left(y,x\right),\left(z,x\right)\in \rho \right)$
A csomó elágazás valódi, ha egyik él sem hurok.

Az incidenciamátrixból jól leolvashatóak a gráf egyes topológiai jellemzői. Például ha a főátló egyik cellájában 1-es van, akkor a megfelelő elem hurkolt. Általában az a-adik sor b-edik eleme az (a,b) élnek felel meg (és nem megfordítva, az a-adik oszlop b-edik sorának eleme); e megállapodással egy sorban két egyes azt jelenti, hogy a megfelelő elem egy elágazás; míg egy oszlopban két egyes azt, hogy az oszlop megfelelő eleme csomó. Az összes él száma az incidenciamátrix elemeinek összege, egy adott sor(ban lévő 1-esek) összege a sor elemének külfoka, az oszlopokban álló egyesek összege a megfelelő elem belfoka stb.

Egyéb speciális részgráfok

Definíció: Sétának nevezzük a $G=\left(A,\rho \right)$ gráf éleinek olyan sorozatát, melyben minden él végpontja megegyezik a következő él kezdőpontjával – feltéve hogy létezik következő él (véges séta esetén persze van utolsó él, nincs minden élre következő él).

Azaz séta egy $\left(x_{i},y_{i}\right)_{i\in I=\left\{1,2,...,n\right\}}$ sorozat, ahol $\forall i\in I:\left((x_{i},y_{i})\in A\wedge y_{i}=x_{i+1}\right)$

A séta tartalmazhat elágazásokat és csomókat is. A legegyszerűbb példa egy ilyen sétára valamely a $G=\left(\left\{a,b,c,\right\},\left\{\left(a,b\right),\left(a,c\right),\left(b,a\right)\right\}\right)$ gráf 3 hosszúságú $\left(a,b\right),\left(b,a\right),\left(a,c\right)$ sétája.

Definíció: Vonalnak nevezünk egy csomókat és elágazásokat nem tartalmazó sétát.

Definíció: Útnak nevezünk egy önmagát nem metsző vonalat, azaz olyan vonalat, melyben ha két él metszi egymást, akkor azok a vonalban mint élsorozatban szomszédosak (ti. a sorozatban egymás után következnek).

Definíció: Körnek nevezünk egy olyan véges vonalat, melynek kezdő-és végpontja egybeesik.

Definíció: Egy gráfot összefüggőnek nevezünk, ha tetszőleges két pontja közt találunk utat.

Definíció: Egy gráfot erdőnek nevezünk, ha nem tartalmaz kört.

Definíció: Egy összefüggő gráfot fának nevezünk, ha erdő (nem tartalmaz kört).

További információk

• R. L. Graham - M. Grötschel - Lovász L.: Handbook of combinatorics. MIT Press, 1995.