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
irányított gráf:
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
gráf csúcshalmazának (vagy tartóhalmazának) mondjuk, és (az angol „vertex”=csúcs szó rövidítéseként)
-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 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