Gráf -

A „Gráf” lehetséges további jelentéseiről lásd: Gráf (egyértelműsítő lap).

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

Bővebben: Gráfelméleti fogalomtár

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 út probléma

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.

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.

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á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):

					…
K₁	K₂	K₃	K₄	K₅
					…
	P₂	P₃	P₄	P₅
					…
		C₃	C₄	C₅

Teljes páros gráfok

			…
K_1,1	K_1,2	K_1,3
			…
K_2,1	K_2,2	K_2,3
			…
K_3,1	K_3,2	K_3,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:

Híres gráfok:

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\}

Source: Gráf