Matematika | Tanulmányok, esszék » Gráfok és fák

Gráfok és fák 1. GRÁFOK Gráf: geometriai alakzat, csúcsok + élek összességeként ábrázoljuk. A körökkel ábrázolt csúcsokat összekötő vonalakat éleknek nevezzük, ezek összessége a gráf. Abban az esetben, ha az éleknek irányuk van, irányított gráfnak nevezzük. Az irányított gráfban ha az él a csúcsból vezet b-be, akkor a-t az él kezdőpontjának, b-t az él végpontjának nevezzük. Azokat a gráfokat, amelyekben irányított és irányítatlan él is szerepel, vegyes gráfnak hívjuk. Irányítatlan gráf: Irányított gráf: a Vegyes gráf: a b b oc c d d e o e Fajtái: - izolált csúcs: ha egy csúcsból nem indul él és bele sem megy (se be, se ki), - teljes gráf: ha egy gráfban bármely két csúcs éllel van összekötve (bármely két csúcs összekötött), - üres gráf: ha egy gráfban csak izolált csúcsok vannak (csak izolált csúcsok vannak benne), - hurok: az olyan él, amely egy csúcsból önmagába vezet (önmagába

megy vissza az él), - terminális csúcs: azok a csúcsok, amelyből nem vezet él egy másik csúcshoz (nem megy ki él), Gráfok lehetnek: - Izomorf gráf: két gráf izomorf, ha létezik egy olyan kölcsönösen egyértelmű leképezés a csúcspontok között, amely megtartja a csúcspontok közötti éleket és azok irányait (az alakzat különböző, a gráf ugyanaz). - Multigráf: olyan gráf, amelyben két csúcspont között több él vezet (párhuzamos), többszörös élek mennek egyik csúcsból a másikba (két csomópont között több él). - Súlyozott gráf: a többszörös élre írt szám az él súlyának tekinthető. Az élre nem csak egész számot írhatunk fel (az élekhez számokat rendelünk). - Részgráf: a G’=(V’, E’) gráfot a G=(V,E) gráf részgráfjának nevezzük, ha V’V és E’E (egy gráf része). Gráfok jellemzői: - Csúcsok fokszáma: hány él jön ki belőle. Pld G irányítatlan gráf esetében annak egy a csúcsában

végződő élei illeszkednek a-ra. Ezek száma a q(a) A q(a) a csúcs fokszáma A fokszámok összege páros szám. - Ciklikus rang: a  = N-n+1 számot (ahol N az élek, n a csúcsok száma) az irányított vagy irányítatlan gráf ciklikus rangjának – ciklomatikus számának – nevezzük. - Út: egymáshoz fűzött élek sorozata, távolság. Az utat alkotó élek számát az út hosszának hívjuk Irányított gráf esetén úton irányított élek egymáshoz fűzött sorozatát értjük. Lehet: - egyszerű út: a gráfban minden él különböző - elemi út: az az út, amelyben minden csúcs különböző. - Kör: az olyan út, amelynek első és utolsó csúcsa azonos, azaz önmagába visszatérő út. Lehet: - egyszerű kör: ha az út egyszerű - elemi kör: ha minden csúcson egyszer megy át. - Csúcs elérhetősége: két csúcs elérhető, ha létezik közöttük út. A legrövidebb út hosszát a két csúcs távolságának nevezzük. - Összefüggő gráf: ha

bármelyik csúcsából bármelyik másikba eljuthatunk egy úton keresztül. - Digráf: erősen összefüggőnek nevezzük, ha irányított úton bármelyik csúcsából bármelyik másikba eljuthatunk egy úton keresztül. - Gráf bázisa: a csúcsok olyan minimális részhalmazát, amelyből minden csúcs úttal érhető el. 1 2. FÁK Fa meghatározása: olyan körmentes irányított gráf, amelynek van olyan csúcsa, amelybe nem megy él és az összes többi csúcsba pontosan egy él megy be (irányított fa). Fa részei: - levél: terminális csúcsok - elágazási csúcs: csúcsok a terminális csúcsok kivételével - gyökérelem: az a csúcs, amelybe nem megy él. Fa szintje: távolság a gyökérelemtől. 0 szint a gyökérelem, a többi csúcs szintjét a gyökérelemtől való távolsága adja meg. Rendezett fák: azok a fát, amelyben az egyes szintekhez tartozó csomópontokhoz rendezést rendelünk hozzá. Ha a csúcsokat egy-egy szinten balról jobbra rendezzük,

akkor a fát kanonikusan címzettnek mondjuk. Részfák: Minden csúcs egy részfa gyökere. Egy adott csúcshoz tartozó részfák számát az adott csúcs fokának nevezzük. Ha töröljük a gyökérelemet és a belőle induló – az 1-es szinthez menő – éleket , akkor diszjunkt részfákat kapunk. A diszjunkt részfák egy halmaza alkotja az erdőt Egy adott csúcsból elérhető bármelyik csúcs az utód, az ebből a csúcsból 1 hosszúsági úton elérhető a fiú. Bináris fák: azok a fák, amelyekben minden csúcsból legfeljebb két él megy ki. Ha pontosan két él megy ki, akkor teljes bináris fa jön létre. 3. GRÁFOK ALKALMAZÁSAI Alkalmazások: A königsbergi-hidak: Leonhard Eutler svájci matematikus felvetése: egy A,B,C,D terület bármelyikéből indulva, mind a hét königsbergi hídon egyszer és csak egyszer áthaladva vissza lehet-e jutni az induló pontra. A feladatnak nincs megoldása Közműhálózatok: Három épület, melyet három szolgáltató

lát el (víz, gáz- és villanyvezeték). Lehet-e olyan vezetékrendszert létesíteni, hogy a vezetékek ne keresztezzék egymást. Elektromos hálózatok: Elektromos elemek összekötése a hálózatban. Logikai kifejezések ábrázolása: Logikai kifejezések normálformáihoz gráfok hozzárendelése. Diszjunktív normálforma – mint gráf. Alkalmazások az operációkutatásban: az operációkutatás egy része gráfokkal is leírható és értelmezhető. Ezek lehetnek: a) szállítási feladat: csomópontok között szállítunk b) projekttervezés: tevékenységek egymásutánja Gráfok a játékelméletben: kétszemélyes játékok. Automaták megadása gráfokkal: egy adott állapotban egy jelet olvasva átmennek egy másik állapotba. Az állapotoknak a csúcsokat, a beolvasott jeleket az éleknek megfeleltetve jól le tudjuk írni az automata működését gráffal. Számítástechnikai alkalmazások: - Aritmetikai kifejezések ábrázolása gráffal. - Adatszerkezet

(listaszerkezet) ábrázolása. - Program ábrázolása gráffal: a) egyszerű utasítássorozat (szekvencia) b) elágazás (feltételtől függő kiválasztás) c) ciklus - Adatbázisok: a) hierarchikus adatbázisok: azok az adatbázisok, amelyeket fával adunk meg), b) hálós adatmodellek (azok az adatmodellek, amelyekben az adatbázis szerkezete egy általános gráffal adható meg). 2