Gráfelmélet A-tól Z-ig

Gráfnak nevezünk olyan (továbbiakban (f,E,V)) hármasokat, ahol E az élek halmaza (edge), V a csúcsok halmaza (vertex), f pedig egy ún. illeszkedési leképezés, ami E-ből {V,V}-be képez. A gráfokat a gyakorlatban rajzzal szemléltetjük, ahol az egyes pontok a csúcsokat, az őket összekötő vonalak az éleket jelentik. Ha egy csúcsot egy él (ún. hurokél) önmagával köt össze, egy hurok keletkezik. Két csúcs között több él is futhat, ezek a többszörös élek. Ha egy gráfban egyáltalán nincsenek élek, üres gráf. Ha egy csúcshoz nincs kötve egy él sem, izolált csúcs. Két csúcs szomszédos, ha él köti össze őket. Hasonlóképp két él is lehet szomszédos, ha létezik csúcs, melyre mindkettő illeszkedik. A gráfok lehetnek végesek vagy végtelenek az E és V halmazok számosságától függően. Egy csúcsnak a fokszáma a rá illeszkedő élek száma azzal a kikötéssel, hogy a hurokéleket kétszer kell számolni. Ha egy olyan speciális gráfot veszünk, melyben a fokszámok megegyeznek, n-reguláris gráfról beszélünk. Ha például minden csúcs fokszáma 3, a gráf 3-reguláris. Abból, hogy minden élnek két végpontja van következik, hogy a fokszámok összege páros, és az élek számának kétszerese. Teljes gráf egy gráf, ha az összes lehetséges él szerepel benne úgy, hogy egyszerű gráf maradjon. Egyszerű gráf akkor, ha nem tartalmaz se hurkot, se többszörös élet, és véges. Egy n csúcsú teljes gráfnak n alatt a 2 éle van. Egy páros gráf úgy áll elő, hogy a csúcsok halmazát két diszjunkt (közös elemeket nem tartalmazó) halmazra bontjuk úgy, hogy miden él végpontjai más halmazba kerüljenek. Két gráf F=(f,E,V) és G=(f',E',V') izomorf, ha léteznek az élek halmazai (E, E') és a csúcsok halmazai (V, V') közti kölcsönösen egyértelmű leképezések, nevezzük őket w-nek és z-nek, melyre igaz, hogy minden e él pontosan akkor illeszkedik a v csúcsra, ha w(e) él is illeszkedik a z(v) csúcsra. Az izomorfia semmiképp nem teljesülhet, ha a két gráf közül valamelyiknek több csúcsa vagy éle van, vagy a fokszámok eltérnek. Egy gráfnak részgráfja egy olyan gráf, amelynél az élek / csúcsok halmaza része a másik gráf éleinek / csúcsainak halmazának. A feszített részgráf ennek egy speciális esete, amikor csak olyan éleket veszünk el, melyeknek valamelyik végpontja már nem szerepel a csúcshalmazban, vagyis a lehető legtöbb élet meghagyjuk. A részgráfnak létezik komplementere, ami egy olyan gráf, ahol az illeszkedési leképezést megszorítjuk az E\E' halmazra, és az élek halmaza is ez az E\E' halmaz lesz. (A csúcsok változatlanok maradnak. ) Egy séta a gráfban csúcsok és élek sorozata. A séta hossza a benne szereplő élek száma függetlenül attól, hogy azonosak-e. Zártséta, ha ugyanahhoz a csúcshoz érünk vissza, ellenkező esetben nyílt. Az út a séta egy speciális esete, amikor egy csúcsot csak egyszer érinthetünk. A vonal hasonlóképp speciális eset, itt az éleknek kell különbözőnek lenniük. Körnek egy olyan zárt sétát nevezünk, ami vonal és út is egyben, azaz semmit nem érintünk kétszer és ugyanoda érünk vissza. Körnek számít az egyszerű hurok is. Egy gráf összefüggő, ha az élek mentén bármely csúcsából el lehet jutni a másikba. Ha a gráf nem összefüggő, felbontható több komponensre. A komponenst azt vizsgálva kapjuk meg, hogy honnan hová lehet eljutni. Egy-egy maximális izolált gráfrész a gráf egy komponense. Más megfogalmazásban: az elérhetőségi reláció ekvivalenciareláció, így osztályozza a gráf csúcsait, ezek az osztályok a komponensek. Az összefüggőségből egyértelműen adódik, hogy az összefüggő gráf egyetlen komponensű. A gráfok egy újabb speciális típusa a fa, ami összefüggő, és nem tartalmaz kört. Egy fa maximális összefüggő, körmentes gráf. Azaz egyetlen élet hozzáadva már biztosan nem lenne fa. A feszítőfa egy feszített részgráf, ami fa. Feszítőfája minden véges gráfnak létezik. Bármilyen körmentes gráf erdő, melynek komponensei a fák. Euler-vonalnak nevezzük az olyan vonalat, amiben a gráf minden éle szerepel. A Hamilton-út olyan út, mely minden csúcsot tartalmaz. Az irányított gráf olyan (f,E,V) hármas, ahol f (illeszkedési leképezés) E-ből V×V-be képez. Egy V×V-beli számpár első / utolsó tagja az él kezdő- / végpontja. Egy gráf erősen összefüggő, ha vármely v és v' csúcs között vezet irányított út. Ha egy irányított gráf egyetlen komponensű, erősen összefüggő.

Vélemény, hozzászólás?

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöljük.