2. fejezet - Gráfelméleti alapfogalmak

2.1. 2.1. Digráf fogalma

A digráf fogalmához az egyszerűbb matematikai objektum, a gráf fogalmán keresztül juthatunk.

Gráf fogalma:

Véges sok pont és a pontok közötti kapcsolatokat kifejező élek összességét gráfnak nevezzük.

Irányított gráf fogalma:

Az olyan gráfot, amelynek élei irányítottak irányított gráfnak nevezzük.

Digráf fogalma:

Az olyan irányított gráfot, amely sem többszörös élt, sem hurokélt nem tartalmaz digráfnak nevezzük.

Az alábbi ábrán látható irányított gráfokban többszörös él és hurokél szerepel, így egyik sem tekinthető digráfnak:

Példaként tekintsük az alábbi ábrán látható digráfot, a következőkben ez lesz a minta digráfunk és ennek segítségével mutatjuk be a digráffal kapcsolatos fogalmakat:

Általában a digráf ponthalmazát N-el (Node), élhalmazát A-val (Arc) jelöljük. A digráf jelölésére az [N,A] szimbólumot használjuk. A pontokat általában a természetes számokkal jelöljük. Az éleket kerek zárójelbe írt pontpárral adjuk meg, az első helyen az él kezdőpontja, második helyen pedig az él végpontja szerepel.

A fenti példában szereplő digráf ponthalmaza és élhalmaza a következő:

Egy digráfot többféle módon is megadhatunk:

a) Ábrával

Ez a megadás a legtermészetesebb, az ábra alakja tetszőleges lehet, de ügyeljünk az áttekinthető ábrázolásra. Nem minden gráf rajzolható le úgy, hogy élei nem metszik egymást, csak az ún. síkbeli gráfokat lehet ilyen áttekinthető módon lerajzolni.

b) Az ponthalmaz és az élhalmaz tételes felsorolásával

Ez a megadási mód fentebb látható.

c) „Honnan-hova” táblázattal

Egy kétsoros táblázatban oszloponként felsoroljuk a digráf éleit. Az oszlop első eleme az él kezdőpontját (honnan), a második elem pedig az él végpontja (hova).

A minta digráf megadása „honnan-hova” táblázattal:

d) Szomszédossági mátrix segítségével

A szomszédossági mátrix egy pont-él mátrix, amelynek a sorai a digráf pontjait, oszlopai pedig a digráf éleit jelentik. Szokás ezt a mátrixot incidencia mátrixnak is nevezni. A mátrixot jelöljük S-el, elemei 1, -1, 0 számok és a mátrixelemeket az alábbiak szerint értelmezzük:

A minta digráf megadása ssomszédossági mátrix segítségével:

Megjegyzések:

Oszloponként vizsgálva a mátrixot, észrevehetjük, hogy minden oszlopban egyetlen egy 1-es és egyetlen egy (-1)-es van.

Soronként vizsgálva a mátrixot a következőket mondhatjuk:

A sorokban az 1-esek száma a sornak megfelelő pontból kifelé mutató élek darabszámát mutatja meg.

A sorokban a (-1)-esek száma a sornak megfelelő pontba befelé mutató élek darabszámát mutatja meg.

e) Struktúramátrix vagy struktúratáblázat segítségével

A struktúramátrix egy pont-pont mátrix, amelynek sorai és oszlopai is a digráf pontjait jelentik. Szokás ezt a mátrixot csúcsmátrixnak is nevezni. A mátrixot jelöljük C-vel, elemei 1, 0 számok és a mátrixelemeket az alábbiak szerint értelmezzük:

A minta digráf megadása struktúramátrix segítségével:

Észrevehetjük, hogy a mátrix négyzetes, a főátlójában zérus elemek állnak és az 1-esek száma a digráf éleinek a számát mutatja. Soronként és oszloponként vizsgálva a mátrixot a következőket mondhatjuk:

A sorokban az 1-esek száma a sornak megfelelő pontból kifelé mutató élek darabszámát mutatja meg.

Az oszlopokban az 1-esek száma az oszlopnak megfelelő pontba befelé mutató élek darabszámát mutatja meg.

A jobb szemléltetés miatt strukrúramátrix helyett inkább struktúratáblázattal adjuk meg a digráfot. A sorok és az oszlopok fejlécében felsoroljuk a digráf pontjait, a digráf éleit pedig úgy jellemezzük, hogy ahol él van a digráfban ott a táblázat megfelelő celláját megjelöljük valamilyen jellel (pl. a * szimbólummal), ahol nincs él ott üresen hagyjuk a táblázat celláját. A táblázat sorai az él kezdőpontját, az oszlopai pedig az él végpontját mutatják. A minta digráf megadása struktúratáblázat segítségével:

A struktúratáblázat főátlójában nem lehet * (mivel nincs hurokél), ezért a táblázat főátlójában egy -os egyenest szoktunk rajzolni, ezzel is segítjük a táblázatban történő könnyebb tájékozódást.

A digráfokon, majd később a hálózatokon az elvégzendő műveleteket mindig struktúratáblázaton valósítjuk meg. A mátrixos megadást a számítógépen történő megadáshoz ill. a matematikai kezeléshez szokás használni.

Megjegyzések :

  1. Egy gráfot egyszerűnek mondunk, ha a gráf nem tartalmaz sem többszörös élt, sem hurokélt. A digráf tehát egy egyszerű irányított gráf.

  2. Ha az ponthalmazból álló digráf minden élt tartalmaz, akkor azt mondjuk, hogy a digráf teljes és röviden -el jelöljük, éleinek száma: .