Gráf (halmazelmélet)

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

A gráf lehet nyelvészeti és matematikai fogalom is (a különböző jelentéseket ld. a gráf címszó alatt). A matematikában e fogalomnak szemléletes, geometriai, az elemi matematikában használt értelmezése is adható (ld. a gráf (diszkrét matematika) c. szócikket), de a jelen cikk a formalista iskola eredményeire hagyatkozva igen absztrakt szemléletben tárgyalja a gráfokat.

Tartalomjegyzék

1 Definíció
2 Alapfogalmak
3 Halmazelméleti leírásuk: műveletek, relációk
4 Gráftopológiai fogalmak
5 Általánosítások, speciális esetek és változatok
6 Wikipédia: Lásd még

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

[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 $G 1, G 2$ gráfokat homomorfnak vagy hasonlónak nevezzük, ha létezik köztük „illeszkedéstartó” leképezés, azaz

$\exist \phi (x)\in A_{2}^{A_{1}}: \forall x,y\in A: (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(x):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 $G 1, G 2$ 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 fá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í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;

[szerkesztés] Wikipédia: Lásd még

gráf (diszkrét matematika);
relációs struktúra

A lap eredeti címe "http://hu.wikipedia.org../../../g/r/%C3%A1/Gr%C3%A1f_%28halmazelm%C3%A9let%29.html"

Kategória: Halmazelmélet

We provide Linux to the World