Gráf (diszkrét matematika)
A Wikipédiából, a szabad lexikonból.
| Ezen szócikk összedolgozandó a(z) Gráf (halmazelmélet) szócikkel, azután az egyik lap törlendő. |
| Ezen szócikk összedolgozandó a(z) Gráf (csonk) szócikkel, azután az egyik lap törlendő. |
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 |
[szerkesztés] Definíció
Definíció: Adott egy A halmaz, és egy rajta értelmezett
bináris (kétváltozós) reláció. Ekkor a
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
, é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
gráf tartóhalmazának vagy csúcshalmazának mondjuk, és (az angol „vertex”=csúcs szó rövidítéseként)
-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 gráf éleinek nevezzük.
Ha
a
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
terminológia is, azaz mondhatjuk, hogy az él eleme a gráfnak.
[szerkesztés] Incidenciafüggvény, incidenciamátrix
Az
kétváltozós (azaz
-n értelmezett) függvényt a gráf illeszkedési függvényének vagy incidenciafüggvényének nevezzük, ha teljesül:

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


[szerkesztés] Részgráf
Ha adottak ugyanazon A halmaz felett értelmezett
és
gráfok, akkor amennyiben
, akkor az elsőt a második részgráfjának nevezzük.
Jele
.
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
.[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
és 
Ekkor

és

és
;
ha pedig adott gráfok egy
rendszere, akkor

és

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

E reláció ekvivalenciareláció gráfok bármely halmaza felett. Jele
.
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ő
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

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
csúcsot az
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
.
Az x csúcs utódainak halmazát
szokta jelölni:

Az x csúcs szülőinek halmazát mi úgy jelöljük majd,
:

Az utódok számát külfoknak (vagy talán még rosszabbul hangzó kifejezéssel kifoknak) nevezik;
(külfok)míg a szülők számát belfoknak (befok):
(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:
izolált, ha
.
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:
izolált, ha
.
[szerkesztés] Hurok, elágazás
Definíció: Az
alakú éleket, azaz melyek kezdő- és végpontja egybeesik, huroknak nevezzük. Ezt az
pontbeli huroknak mondjuk.
Ha a ρ reláció reflexív, akkor minden pontban van hurok is.
Definíció: Azt mondjuk, az
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

Az elágazás valódi, ha egyik él sem hurok.
Definíció: Azt mondjuk, az
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

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
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
sorozat, ahol 
A séta tartalmazhat elágazásokat és csomókat is. A legegyszerűbb példa egy ilyen sétára valamely a
gráf 3 hosszúságú
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í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


Based on work by