Gráf

A Wikipédiából, a szabad enciklopédiából
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ó[szerkesztés | forrásszöveg szerkesztése]

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

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

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

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

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

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

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

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

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

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

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

Definíciók[szerkesztés | forrásszöveg szerkesztése]

Irányítatlan gráf[szerkesztés | forrásszöveg szerkesztése]

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

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 DAG-nak ('directed acyclic graph' = irányított körmentes gráf) hívjuk.

Vegyes gráf[szerkesztés | forrásszöveg szerkesztése]

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

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.
  • Egy irányítatlan gráf felfogható szimpliciális komplexusnak, ami 1-szimplexekbő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[szerkesztés | forrásszöveg szerkesztése]

Teljes gráfok (K), utak (P), körök (C):

Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg Complete graph K4.svg Complete graph K5.svg
  …
K1
K2
K3
K4
K5
Complete graph K2.svg Complete bipartite graph K2,1.svg Path graph P4.svg Path graph P5.svg
  …
P2
P3
P4
P5
Complete graph K3.svg Circle graph C4.svg Circle graph C5.svg
  …
C3
C4
C5

Teljes páros gráfok

Complete bipartite graph K1,1.svg Complete bipartite graph K2,1.svg Complete bipartite graph K3,1.svg
  …
K1,1
K1,2
K1,3
Complete bipartite graph K2,2.svg Complete bipartite graph K3,2.svg
  …
K2,1
K2,2
K2,3
Complete bipartite graph K3,3.svg
  …
K3,1
K3,2
K3,3

Alapvető gráfok:

Bonyolultabb gráfosztályok:

Híres gráfok:

Gráfokon értelmezett műveletek[szerkesztés | forrásszöveg szerkesztése]

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

Unáris műveletek[szerkesztés | forrásszöveg szerkesztése]

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

Gráftopológiai fogalmak[szerkesztés | forrásszöveg szerkesztése]

Szülő, utód, fok[szerkesztés | forrásszöveg szerkesztése]

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

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

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 nak nevezünk, ha erdő (nem tartalmaz kört).

Lásd még[szerkesztés | forrásszöveg szerkesztése]

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