Gráf (halmazelmélet)

A Wikipédiából, a szabad lexikonból.

Ezen szócikk összedolgozandó a(z) Gráf (diszkrét matematika) szócikkel,
azután az egyik lap törlendő.

A gráf a gráfelmélet és a számításelmélet 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 í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 a két iránynak irányított élek felelnek meg.

Tartalomjegyzék

[szerkesztés] Definíciók

A gráf általános definíciója megengedi, hogy tetszőleges szándékolt jelentést tulajdonítsunk a csúcsoknak és éleknek. Sok, valós életben felmerülő probléma könnyen átfogalmazható a „gráfok nyelvére” és oldható meg gráfelméleti megfontolások alapján. Az, hogy a probléma reprezentációjához milyen gráftípust használunk, függ a probléma jellegétől.

[szerkesztés] 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.

[szerkesztés] 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, u a v közvetlen őse.

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.

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.

[szerkesztés] Csúcshalmaz

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

[szerkesztés] Alapfogalmak

[szerkesztés] Csúcsok, élek

Az A halmaz elemeit a gráf csúcsainak, a ρ halmaz elemeit, tehát (a,b) alakú párokat, ahol a,b\in A, a gráf éleinek nevezzük.

Ha \left( a,b \right) \in \rho a G= \left( A,\rho\right) tetszőleges éle, akkor azt is mondjuk, az a, b csúcsok illeszkednek az (a,b) élre, a-t az él kezdőpontjának, b-t a végpontjának mondjuk. Teljesen inkorrekt, mégis általában félreértés nélkül használható ez esetben az \left( a,b\right)\in G terminológia is, azaz mondhatjuk, hogy az él eleme a gráfnak.

[szerkesztés] Incidenciafüggvény, incidenciamátrix

Az I_G\left( x,y\right):A\times A\rightarrow\left( 0,1\right) kétváltozós (azaz A\times A-n értelmezett) függvényt a gráf illeszkedési függvényének vagy incidenciafüggvényének nevezzük, ha teljesül:

I_G(x,y)=\left\{\begin{matrix} 0, & \mbox{ha }(x,y)\not\in\rho; \\ 1, & \mbox{ha }(x,y)\in\rho \end{matrix}\right.

Vagyis a G incidenciafüggvénye nem más, mint az élek halmazának A×A felett értelmezett karakterisztikus függvénye.

Ha ezt (véges) mátrix alakban adjuk meg, amennyiben lehetséges, akkor ez utóbbi mátrixot illeszkedési mátrixnak vagy incidenciamátrixnak nevezzük.

Példa: a G= \left( \left\{ a,b,c \right\} , \left\{ (a,b), (a,c), (b,b) \right\} \right) gráf incidenciamátrixa (az első zárójelbe tett sor és oszlop nem a mátrix részei, csak azt jelzik, mely sor mely oszlop melyik elemet reprezentálja a mátrixban):

            \begin{pmatrix} a & b & c \end{pmatrix}
\begin{pmatrix} a \\ b \\ c \end{pmatrix} \begin{pmatrix} 0 & 1 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix}

[szerkesztés] Részgráf

Ha adottak ugyanazon A halmaz felett értelmezett G_1=\left( A, \rho _1\right) és G_1=\left( A, \rho _1\right) gráfok, akkor amennyiben \rho _1\subseteq \rho _2, akkor az elsőt a második részgráfjának nevezzük.
Jele G_1\subseteq G_2.

Egy gráf tehát részgráfja a másiknak, ha az első minden éle a másiknak is éle. Az értelmezésből következik, hogy e reláció antiszimmetrikus, azaz

\left( G_{1}\subseteq G_{2}\right) \wedge \left( G_{2}\subseteq G_1\right) \Rightarrow \left( G_{1}=G_{2} \right).

[szerkesztés] Halmazelméleti leírásuk: műveletek, relációk

[szerkesztés] Halmazműveletek

A szokásos halmazműveletek (unió, metszet, különbség) is értelmezhetőek a gráfokon is (bár ennek viszonylag ritkán van jelentősége), a következőképp:
Legyen G_{1}=\left(A_{1}, \rho _{1} \right) és G_{2}=\left(A_{2}, \rho _{2} \right)

Ekkor

G_{1} \cup G_{2}=\left( A_{1} \cup A_{2},\rho_{1} \cup \rho_{2} \right)

és

G_{1} \cap G_{2}=\left( A_{1} \cup A_{2},\rho_{1} \cap \rho_{2} \right)

és

G_{1} - G_{2}=\left( A_{1} \cup A_{2},\rho_{1} - \rho_{2} \right);




ha pedig adott gráfok egy \left( G_{i} \right) _{i\in I}= \left(  A_{i}, \rho _{i} \right) _{i\in I} rendszere, akkor

\cup_{i\in I} G_{i} = \left( \cup_{i\in I} A_{i}, \cup_{i\in I} \rho _{i} \right)

és

\cap_{i\in I} G_{i} = \left( \cup_{i\in I} A_{i}, \cap_{i\in I} \rho _{i} \right)


Ellenőrizhető, hogy érvényesek a szokásos kommutativitási, asszociativitási, disztributivitási stb. törvények.

[szerkesztés] Homomorfizmus, izomorfizmus

A G1,G2 gráfokat homomorfnak vagy hasonlónak nevezzük, ha létezik köztük „illeszkedéstartó” leképezés, azaz

\exist \phi:A_{1}\rightarrow A_2\; \forall x,y\in A_1: (x,y)\in \rho _{1} \Leftrightarrow \left( \phi (x), \phi (y) \right) \in \rho _{2}


E reláció ekvivalenciareláció gráfok bármely halmaza felett. Jele G_{1} \sim G_{2}.

Megjegyezzük, hogy a két gráf akkor és csak akkor homomorf, ha mint relációs struktúrák homomorfak (ld. ott).

Ha a homomorfizmus definícióját kielégítő \phi:A_{1}\rightarrow A_{2} leképezések közt létezik kölcsönösen egyértelmű, azaz bijektív függvény is, akkor a két gráf izomorf. Jele

G_{1} \cong G_{2}


Szemléletesen ez olyasmit jelent, hogy a két gráf szerkezete ugyanaz (pontosan ugyanolyan ábra készíthető mindkettőről), csak csúcsaikat és éleiket más betűkkel jelöltük.

Az izomorfizmus is ekvivalenciareláció gráfok tetszőleges halmaza felett.

[szerkesztés] Direkt szorzat

A G1,G2 gráfok direkt szorzata relációs struktúrákként vett direkt szorzatukkal egyezik meg, ld. ott.

[szerkesztés] Gráftopológiai fogalmak

[szerkesztés] 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.

[szerkesztés] 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 \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. Pl. 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.


[szerkesztés] 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 út 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).

[szerkesztés] Általánosítások, speciális esetek és változatok

  • irányított gráfok;
  • irányított körmentes gráfok, DAG;
  • irányítatlan gráfok;
  • reflexív és irreflexív gráfok
  • végtelen gráfok;
  • általánosított vagy multigráfok;
  • jelölt gráfok, általánosabban pedig színezett gráfok: élszínezett és csúcsszínezett gráfok;
  • súlyozás vagy értékelés: súlyozott és élsúlyozott gráfok
  • és/vagy gráfok;
  • hipergráfok;
  • véletlen gráfok;
  • fuzzy gráfok;
  • intervallumgráfok;
  • relációs struktúra