Gráfelméleti fogalomtár

A Wikipédiából, a szabad enciklopédiából
Ez a szócikk fordítással készül en:Glossary of graph theory, de még csonk.

A gráfelmélet a matematika egyik kutatási területe, a szakszókincse igen gazdag. Néhány fogalom tekintetében nincs egység a szerzők között, előfordulhat, hogy ugyanazon fogalom alatt az egyik mást ért, vagy hogy két különböző fogalmat ugyanabban az értelemben használnak. Ez a cikk igyekszik lépést tartani a mai szóhasználattal, az esetleges többértelműségekre is utalva.

Alapfogalmak[szerkesztés | forrásszöveg szerkesztése]

Egy G gráf két különböző típusú elemből, csúcsokból és élekből áll. Minden élnek két végpontja van, melyek a csúcsok halmazából kerülnek ki, azt mondjuk, hogy az él összeköti a két végpontot. Az élek halmaza tehát definiálható az összes csúcsokból képzett kételemű halmazok részhalmazaként. Gyakran mégis úgy tekintenek az élek halmazára, mint egy halmaz amelyen értelmezve van egy illeszkedési reláció, amely egy élhez egy csúcspárt rendel, az él végpontjait.

Az éleket elláthatjuk egy iránnyal (irányítással), amely az irányított gráf fogalmához vezet (lásd az Irányított gráfok szakaszt).

A gráfoknak más modelljei is vannak: például egy a csúcsok halmazán értelmezett bináris reláció (Gráf (halmazelmélet)), vagy egy négyzetes, 0-kból és 1-kből álló mátrix.

Egy csúcs (alapelem) képe a diagramon egy pont, ezért hívják szögpontnak is. A G gráf csúcshalmazának jelölése V(G), vagy egyszerűen csak V, ha nem okoz félreértést. Egy gráf rendje a csúcsok száma, azaz |V(G)|.

Egy él (két alapelemből álló halmaz) képe a diagramon egy vonal, amely két csúcsot köt össze, ezeket végpontoknak hívjuk. Egy élet, melynek x és y a végpontjai xy-nal jelölünk, azaz nincs köztük semmilyen szimbólum. A G gráf élhalmazának jelölése E(G), vagy E, ha nem okoz félreértést.

Két csúcs szomszédos, ha éllel vannak összekötve. Hasonlóan, két él szomszédos, ha van közös csúcsuk. k

Egy hurokél, vagy hurok egy olyan él, melynek két végpontja ugyanaz a csúcs. Egy él többszörös, ha a gráfban van más él is ugyanezekkel a végpontokkal, egyébként az él egyszerű. Az él multiplicitása azon (többszörös) élek száma melyekkel megegyeznek a végpontjai. Egy gráf egyszerű, ha nincsenek benne többszörös és hurokélek, multigráf, ha vannak többszörös élei, és multigráf vagy pszeudográf, ha többszörös élek és hurokélek is vannak benne (nincs egységes elnevezés az irodalomban). A gráf (megkülönböztető jelző nélkül) többnyire egyszerű gráfot jelöl.

A gráf címkézése általában egyedi címkék (legtöbbször természetes számok) csúcsokhoz és élekhez rendelését jelenti. Ha egy gráf csúcsai, vagy élei címkézettek akkor címkézett gráfnak hívjuk, különben címkézetlennek. Különbséget tehetünk csúcscímkézett és élcímkézett gráfok között, ha hangsúlyozni szeretnénk, hogy csak a csúcs- vagy élhalmaz elemeit tekintjük megkülönböztethetőnek.

Egy címkézett egyszerű gráf, csúcsai: V = {1, 2, 3, 4, 5, 6} és élei: E = Sablon:1,2, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, Sablon:4,6 (ahol az illeszkedési reláció az identitás).

Egy hiperél egy olyan él, amely akárhány csúcsot összeköthet, akár több mint 2-t. Egy olyan gráfot, amelyben lehetnek hiperélek hipergráfnak hívunk. Egy egyszerű gráf tekinthető a hipergráf speciális esetének, ahol minden él pontosan két csúcsot köt össze. Egy élről (ha nincs kimondva, hogy hiperél) mindig feltehetjük, hogy legfeljebb két csúcsot köt össze. Hasonlóan a gráf sem téveszthető össze a hipergráffal.

Egy anti-él egy olyan él, amely nincs benne a gráfban. Formálisan, az u és v csúcsra {u,v} anti-él a G gráfban, ha u és v közt nincs él G-ben, illetve irányított esetben (u,v) anti-él, ha nincs (u,v) él G-ben (de (v,u) él lehet).

Három csúcsot háromszögnek hívunk, ha páronként össze vannak kötve, anti-háromszögnek, ha semelyik kettő nincs összekötve.

A G gráf \overline{G} komplementere a G antiéleiből álló gráf, azaz az a gráf, melynek csúcshalmaza megegyezik G-ével és egy (x,y) él akkor és csak akkor van benne \overline{G}-ben, ha (x,y) nincs benne G-ben. Az egy csúcspontú és nulla élű gráfot triviális gráfnak nevezzük, az olyan gráfot pedig, aminek csak csúcsai vannak, de nincsenek élei, élmentes gráfnak, üres gráfnak vagy nullgráfnak (nincs konzisztens elnevezése az irodalomban). A csúcspont- és élmentes gráfot is szokás nullgráfnak vagy üres gráfnak nevezni, de nem minden matematikus fogadja el az ilyen gráf létezését.

Egy gráf végtelen, ha csúcsainak vagy éleinek vagy akár mindkettőnek száma végtelen. Egy olyan gráfot, amelyben minden csúcs fokszáma véges lokálisan véges gráfnak hívjuk. Egy gráfról, ha nem állítjuk az ellenkezőjét, mindig feltehető, hogy véges.

Azt mondjuk, hogy a két gráf G és H izomorfak (jelölése G ~ H), ha csúcsaik közt van olyan egy-egy értelmű megfeleltetés, melyet izomorfizmusnak hívunk, hogy két csúcs szomszédos G-ben akkor és csak akkor, ha a megfelelőik szomszédosak H-ban. Hasonlóan G homomorf H-val, ha van olyan leképezés V(G)-ről V(H)-ra, melyet homomorfizmusnak hívunk, úgy hogy két csúcs szomszédos G-ben akkor és csak akkor, ha képeik szomszédosak H-ban.

Részgráfok[szerkesztés | forrásszöveg szerkesztése]

A G gráf részgráfja egy olyan gráf, melynek csúcs- és élhalmazai részhalmazai G-éinek. Azt mondjuk, hogy G tartalmazza H-t, ha G-nek van olyan részgráfja, mely megegyezik vagy izomorf H-val (az adott helyzettől függ).

Egy H részgráf feszítő részgráfja G-nek, ha csúcshalmaza megegyezik G-ével. Ekkor H kifeszíti G-t.

Egy H részgráf feszített részgráfja G-nek, ha H bármely két csúcsára igaz, hogy szomszédosak H-ban akkor és csak akkor, ha szomszédosak G-ben. Másként fogalmazva H feszített részgráfja G-nek, ha úgy adódik, hogy vesszük G bizonyos szögpontjait és minden, köztük futó élt.

Egy gráfot, amelyik nem tartalmazza H-t feszített részgráfként H-mentesnek hívunk.

Séták[szerkesztés | forrásszöveg szerkesztése]

Egy séta csúcsok és élek váltakozó sorozata, mely csúccsal kezdődik és csúcsban végződik, és minden csúcs szomszédos az őt megelőző és őt követő éllel, illetve minden él két végpontja az őt megelőző és az őt követő csúcs. Egy séta zárt, ha első és utolsó csúcsai megegyeznek, különben nyitott.

A séta l hossza az őt alkotó élek száma. Minden nyitott sétára l = n‒1, ahol n a meglátogatott csúcsok száma (minden csúcsot annyiszor számolunk, ahányszor meglátogattuk), minden zárt sétára l = n (a kezdő- és végcsúcs ugyan kétszer szerepel, de csak egyszer számoljuk). A példa gráfban (1, 2, 5, 1, 2, 3) egy 5 hosszú nyitott séta, és (4, 5, 2, 1, 5, 4) egy 5 hosszú zárt séta.

Régebben használták az út kifejezést a nyílt sétára. Manapság az út jelentése az egyszerű nyílt séta, azaz a séta nem látogatja meg kétszer ugyanazt csúcsot (így kétszer ugyanazt az élet sem használhatja). A zárt megfelelője az egyszerű sétának a kör. (A séta hossza lehet 0, de a körnél ez nem megengedett.) Hasonlóan a sétához, korábban a kör is „csak” zárt sétát jelentett (ezért félrevezetőek például az Euler-kör és Euler-út hagyományos elnevezések az Euler-sétákra). A példa gráfban az (1, 5, 2, 1) egy 3 hosszú kör. Az n csúcsú utakra és körökre gyakran hivatkozunk P_n-nel illetve C_n-nel. (Bár néhány szerző az utaknál a csúcsok száma helyett a hosszt tekinti paraméternek.)

Az n hosszú kört Cn-nel jelöljük. C1 egy hurokél, C2 két kétszög, azaz egy többszörösél-pár, C3 egy háromszög.

Egy kört páros körnek hívunk, ha a hossza páros, különben páratlan kör. Tétel az, hogy egy gráf páros akkor és csak akkor, ha nem tartalmaz páratlan kört (páros gráf).

Egy gráf körmentes (aciklikus), ha nem tartalmaz kört. Sok alkalmazási területen kitüntetett szerepük van az irányított körmentes gráfoknak (DAG).

Egy út (kör) Hamilton-út (Hamilton-kör), ha minden csúcsot pontosan egyszer érint (azaz feszítő). Egy gráfot, amely tartalmaz Hamilton-kört Hamilton-gráfnak hívunk. (Szokás a Hamilton-gráfok halmazát H-val jelölni, de használják teljesen általános gráfra is, mint például ebben a szócikkben is.)

Egy séta, ha minden élet pontosan egyszer használ Euler-út vagy Euler-kör, aszerint, hogy nyílt vagy zárt. A definíciójából eredően egy ilyen séta egy csúcsot akár többször is érinthet.

Két út pontdiszjunkt (vagy pontidegen, de néha hívják függetlennek is), ha nincs közös csúcsuk, a kezdő és végpontjukat leszámítva. Két út éldiszjunkt (élidegen), ha nincs közös élük.

Fák[szerkesztés | forrásszöveg szerkesztése]

A fa egy összefüggő, körmentes egyszerű gráf. A fa első fokú csúcsait levélnek hívjuk. Egy nem levél csúcs a fában belső csúcs. Néha van a fának egy megkülönböztetett csúcsa, a gyökér. A gyökeres fa olyan fa, melyben van gyökér. Az irányított gyökeres fák éleit általában a gyökértől elfelé mutató irányítással látjuk el.

Sok adatszerkezet használ fákat a számítógéptudományban.

A T fa részfája, egy összefüggő részgráfja T-nek.

Erdőnek hívunk egy körmentes egyszerű gráfot, azaz nem feltétlenül összefüggő. (Az erdők pontdiszjunkt fák uniói, innen az elnevezés.)

Az F erdő egy részerdője F egy részgráfja.

A feszítő fa egy olyan feszítő részgráf, amely fa. Minden gráfnak van feszítő erdője, de feszítő fája csak az összefüggő gráfoknak.

Speciális fák a csillagok, amelyeket úgy kapunk, ha k csúcsot egyenként összekötünk egy központi csúccsal. Tehát a k ágú csillag a K_{1,k}.

Az n-ed fokú fa (n-áris fa) egy gyökeres fa, amelyben minden csúcsnak legfeljebb n gyereke van. A teljes n-ed fokú fában minden csúcs gyerekeinek száma pontosan n vagy 0 (az előbbiek a belső csúcsok, az utóbbiak a levelek). Az első fokú fa egy út. A 2-od fokú fát hívják bináris fának is (a bináris fa fogalma általában ezen felül azt is magában foglalja, hogy különbség van bal- és jobb oldali gyerekek között).

Klikkek[szerkesztés | forrásszöveg szerkesztése]

Az n csúcsú teljes gráf (jelölése K_n) az az n csúcsú gráf, melyben bármely két csúcs szomszédos. A példa gráf nem teljes gráf. K_n éleinek száma az összes lehetséges csúcspárok száma, azaz |E(K_n)| = n(n-1)/2.

Egy klikk egy gráfban, olyan csúcsok halmaza, melyek páronként szomszédosak. Mivel egy klikk csúcsait tartalmazó feszített részgráf teljes gráf, használható a teljes részgráf elnevezés is. Egy k-klikk egy k-ad rendű (k elemszámú) klikk. A példa gráfban az 1, 2 és 5 csúcsok egy 3-klikket alkotnak, amit hívnak háromszögnek is.

A G gráf klikkszáma (jelölése ω(G)) a legnagyobb klikkjének rendje (elemszáma). Így a példa gráf klikkszáma (klikkmérete) 3.

Erősen összefüggő komponens[szerkesztés | forrásszöveg szerkesztése]

Irányított gráfban ekvivalenciarelációt kapunk, ha az a és b csúcsot egymással relációban levőnek deklaráljuk, ha a=b vagy köztük mindkét irányba megy irányított út. Az így kapott ekvivalenciareláció osztályai az erősen összefüggő komponensek. Ha az egész gráf alkot egy komponenst, akkor a gráf erősen összefüggő

Szomszédság és fokszám[szerkesztés | forrásszöveg szerkesztése]

A gráfelméletben a fokszám (főleg a csúcsé) a közvetlen szomszédság mértéke.

Egy él két csúcsot köt össze, azt mondjuk, hogy az él a két végpontjára illeszkedik, vagy azt, hogy az él a végpontjaival szomszédos.

A v csúcs fokszáma a G gráfban (jelölése d_G(v)) a rá illeszkedő élek száma, a hurokéleket kétszer számolva. A 0-ad fokú csúcs izolált csúcs. Az első fokú csúcsot hívják levélnek is. A példa gráfban az 1 és 3 csúcsok foka 2; a 2, 4, és 5 csúcsok foka 3; a 6 csúcs pedig egy levél. Ha az élek halmaza, E véges, akkor a csúcsok fokszámainak összege az élek számának kétszerese.

A fokszámok sorozata egy gráf csúcsinak fokszámait tartalmazza nemnövekvő sorrendben (például d1d2 ≥ … ≥ dn). Egy d_1 \geq d_2,\geq \dots \geq d_n fokszámsorozat megvalósítható, ha van olyan gráf, melynek ez a fokszámsorozata.

Két csúcs szomszédos, ha van köztük él. A példa gráfban az 1 és 2 csúcsok szomszédosak, de 2 és 4 nem.

A v csúcs szomszédai (vagy nyílt szomszédsága; jelölése N_{G}(v)) azok a csúcsok melyekkel v szomszédos, kivéve önmagát. Ha a szomszédok közé v-t is beleértjük, akkor zárt szomszédságról beszélünk (jelölése N_{G}[v]). Az alsó indexben lévő G elhagyható, ha nem okoz félreértést. Egyszerű gráfban egy csúcs fokszáma a szomszédainak száma (d_G(v)=|N_G(v)|).

Egy gráf domináló halmaza a csúcsok egy olyan részhalmaza, melyek zárt szomszédsága a gráf összes csúcsát tartalmazza. Egy v csúcs dominál egy másik u csúcsot, ha v-ből u-ba van él. Egy W csúcsrészhalmaz dominál egy másik U csúcsrészhalmazt, ha minden U-beli csúcs szomszédos valamelyik W-beli csúccsal. A legkevesebb csúcsú domináló halmaz mérete a dominálási szám (jelölése γ(G)).

A számítógépekben egy véges irányított vagy irányítatlan n csúcsú gráfot gyakran reprezentálnak az adjacenciamátrixával (más néven szomszédsági mátrix; jelölése A(G)): ez egy n×n-es (négyzetes) mátrix, melynek az i-edik sor j-edik oszlopában lévő szám adja meg az i-edik csúcsból a j-edik csúcsba menő élek számát. Az irányítatlan gráfok adjacencia mátrixa a főátlóra szimmetrikus; az egyszerű gráfoké csak 0-kból és 1-kből áll, és a főátló csupa 0.

A spektrális gráfelmélet tanulmányozza a gráf és adjacencia mátrixának tulajdonságai közti kapcsolatokat.

Egy gráfban a maximális fokszám (jelölése Δ(G)) az összes csúcs fokszámai közül a legnagyobb; a minimális fokszám (jelölése δ(G)) a legkisebb.

Egy gráf reguláris, ha minden csúcsának fokszáma megegyezik. Ha minden csúcsának foka k, akkor k-reguláris. 0-regulárisak az üres gráfok, vagy független halmazok; az 1-reguláris gráfok a teljes párosítások; a 2-reguláris gráfok csúcsdiszjunkt körök uniói.

Egy k-faktor egy k-reguláris feszítő részgráf. Egy teljes párosítás egy 1-faktor. Egy gráf éleinek k-faktorokba osztását k-faktorizációnak hívjuk. A k-faktorizálható gráf egy olyan gráf, amelynek van k-faktorizációja.

Egy gráf bireguláris, ha a legkisebb és legnagyobb fokszám különbözőek, de minden csúcs fokszáma e két érték valamelyike.

Az erősen reguláris gráf olyan reguláris gráf, melyben minden szomszédos csúcspár közös szomszédainak száma is megegyezik, továbbá minden nem szomszédos csúcspár közös szomszédainak száma is megegyezik.

Függetlenség[szerkesztés | forrásszöveg szerkesztése]

A gráfelméletben a függetlenség jelentése általában páronként diszjunkt vagy kölcsönösen nemszomszédos. Ebben az értelemben a függetlenség a közvetlen nemszomszédság egy formája.

Egy izolált csúcs olyan csúcs, melyre nem illeszkedik egy él sem. Egy független halmaz olyan csúcsok halmaza, melyek közül semelyik kettő sem szomszédos. Mivel egy független halmaz feletti részgráf mindig üres gráf az üres részgráf elnevezés is használható. A példa gráfban az 1, 3 és 6 csúcsok egy független halmazt alkotnak; míg a 3, 5 és 6 csúcsok egy másikat.

A független csúcsok maximális száma (más néven függetlenségi szám; jelölése α(G)) a G gráf legnagyobb független halmazának elemszáma.

Egy gráf felbontható független halmazokra abban az értelemben, hogy a csúcshalmaz felbontható páronként diszjunkt független halmazokra. Az ilyen független részhalmazokat partícióknak, vagy független részeknek hívjuk.

Egy olyan gráfot, amely felosztható két független részre, de kevesebbre nem, páros gráfnak hívunk; amely felosztható k független részre, de kevesebbre nem, az k-részes (? 'k-partite'). Ha k ismeretlen, akkor hívhatjuk többrészesnek (? 'multipartite') is. A k-részes gráfokat hívják k színnel színezhetőnek is.

Egy teljes többrészes gráf egy olyan gráf, melyben két csúcs akkor és csak akkor szomszédos, ha különböző partíciókba tartoznak. Az ilyen gráfok megadásához (izomorfia erejéig) elegendő a partíciók elemszámát megadni. Egy teljes többrészes gráf, melynek partícióinak elemszámai a1, a2, … an, jelölése K_{a_1, a_2, \dots, a_n}. A Ka, b gráfok a teljes páros gráfok.

Egy k-részes gráf félreguláris (? 'semiregular'), ha minden partícióján belül a fokszámok egyformák; egyenrészes (? 'equipartite'), ha minden partíció elemszáma megegyezik; és kiegyensúlyozott k-részes (? 'balanced k-partite'), ha bármely két partíció elemszáma legfeljebb 1-gyel különbözik egymástól.

Egy párosítás olyan élek halmaza, melyek páronként csúcsdiszjunktak. A G gráf párosítási száma (jelölése α'(G)) a legnagyobb párosításának elemszáma. Egy feszítő párosítás, vagy más néven teljes párosítás egy olyan párosítás, mely egy gráf összes csúcsát lefedi.

Összefüggőség[szerkesztés | forrásszöveg szerkesztése]

Az összefüggőség a gráfelméletben a szomszédosság fogalmának kiterjesztése.

Ha egy gráfban bármely két csúcs között van út, akkor a gráfot összefüggőnek hívjuk.

Egy összefüggő komponens (vagy komponens) egy maximális összefüggő részgráf. Az összefüggő gráfok egyetlen komponensből állnak, míg a nem összefüggők legalább kettőből. A G gráf komponenseinek számát C(G)-vel jelöljük.

Csúcsok

Egy elvágó pont (artikulációs pont) egy olyan csúcsa egy összefüggő gráfnak, amelynek elhagyásával a megmaradó részgráf már nem összefüggő (szétesik; egy csúcsot mindig csak a vele szomszédos élekkel együtt lehet elhagyni). Például egy fa összes belső csúcsa elvágó pont. Egy elvágó ponthalmaz csúcsok egy olyan halmaza, melyek elhagyásával a maradék gráf szétesik. Az elvágó élet hasonlóan definiáljuk (lásd alább).

Ha találunk utat a gráfban bármely két csúcs között még tetszőleges k ‒ 1 csúcs elhagyása után is, akkor a gráfot k-szorosan összefüggőnek hívjuk. Vegyük észre, hogy egy gráf akkor és csak akkor k-szorosan összefüggő, ha bármely két csúcs között van k diszjunkt (pontidegen) út. A példa gráf összefüggő tehát, 1-szeresen összefüggő, de nem 2-szeresen összefüggő. A G gráf összefüggősége (?: 'connectivity'; jelölése κ(G)) az a legkisebb szám, ahány csúcs elhagyásával a gráf szétesik. Konvenció szerint Kn teljes gráf összefüggősége n ‒ 1; és az üres gráf összefüggősége 0.

Egy elválasztó pont (szeparáló pont) olyan csúcsa egy gráfnak amelynek elhagyásával a gráf komponenseinek száma növekszik. Azaz egy elválasztó pont valamelyik komponens elvágó pontja. Például az erdők összes belső csúcsa elválasztó pont.

Élek

Egy elvágó él egy olyan él egy összefüggő gráfban, melynek elhagyásával a gráf már nem marad összefüggő. Például a fák minden éle elvágó él. Egy elvágó élhalmaz egy olyan élek halmaza, melyek elhagyásával a gráf nem összefüggő gráfra esik szét. Egy vágás az összes olyan él halmaza, melyeknek egyik végpontja egy adott S csúcsrészhalmazban található, míg a másik végpontjuk V(G)\S-beli. Például K3 élei elvágó élhalmazt alkotnak, de vágást nem. Bármely két él K3-ban minimális elvágó élhalmazt és ugyanakkor vágást is alkotnak. Egy vágás mindenképpen elvágó élhalmaz is; és egy minimális elvágó élhalmaz mindig vágás is egyben (nemüres gráfban).

Egy elválasztó él vagy híd (szeparáló él) egy olyan él egy nem feltétlenül összefüggő gráfban, melynek elhagyásával a gráf komponenseinek száma növekszik, azaz egy híd valamelyik komponens elvágó éle. Pélául az erdők minden éle híd.

Egy gráf k-szorosan élösszefüggő, ha bármely k ‒ 1 él elhagyásával is összefüggő marad. Egy gráf élösszefüggősége (jelölése κ’(G)), azon élek minimális száma, melyek elhagyásával G már nem marad összefüggő. Jól ismert eredmény, hogy κ(G) ≤ κ’(G) ≤ δ(G).

A maximálisan összefüggő részgráfok a gráf komponensei.

Távolság[szerkesztés | forrásszöveg szerkesztése]

Két csúcs távolsága (jelölése dG(u, v)) a G gráfban az egyik legrövidebb köztük menő út hossza. A G gráfra utaló alsó index elhagyható, ha nem vezet félreértésre. Ha u és v egybeesnak, akkor távolságuk 0. Ha u és v között nincs út (nem érhető el egyikből a másik), akkor távolságuk definíció szerint végtelen ∞.

Egy csúcs excentricitása (jelölése εG(v)) a legnagyobb távolság V és bármely más csúcs között. A G gráf átmérője (jelölése diam(G)) a legnagyobb excentricitás agráfban; míg a sugár (jelölése rad(G)) a legkisebb. A nem összefüggő gráfokra diam(G) és rad(G) definíció szerint végtelen ∞. Triviálisan igaz, hogy diam(G) ≤ 2 rad(G). A csúcsokat, melyek excentricitása maximális periférikus csúcsoknak hívjuk. A minimális excentricitású csúcsok alkotják a gráf középpontját. Fának legfeljebb két középponti csúcsa lehet.

Egy v \in G csúcs WG(v) Wiener-indexe a d(v,w) távolságok összege, ahol w végigfutja a gráf összes csúcsát. A G gráf W(G) Wiener-indexe az összes d(u,v) távolság összege, ahol u,v \in G. Egy irányítatlan gráf Wiener-polinomja a \sum_{u,v} \mathrm{qd}(u,v) összeg. A Wiener-indexet és a Wiener-polinomot a matematika kémiai alkalmazásaiban használják.

A G gráf k-adik hatványa egy G-t tartalmató gráf, ami az összes legfeljebb k távolságra levő csúcsok összekötő élét is tartalmazza. Egy gráf második hatványát a gráf négyzetének is nevezik.

Gráfok lerajzolása[szerkesztés | forrásszöveg szerkesztése]

Egy gráf diagramja alatt, az absztrakt gráf valamilyen képi megjelenítését értjük (lásd a példa gráfot).

Egy gráf beágyazása egy felületbe, ha csúcsait elhelyezzük a felületen, majd berajzoljuk a csúcsok közti éleket. Egy metszéspont, vagy élkereszteződés egy egymást metsző élpár. Egy gráf lerajzolható egy felületre, ha a gráf csúcsai és élei elrendezhetőek rajta metszéspontok nélkül, azaz ha van metszésmentes felületbe ágyazása. Tekintsük azokat a felületeket, amikbe az adott G gráf beágyazható. Válasszunk ki ezek közül egy minimális genuszút. Az adott G gráf genusza egyenlő ennek a felületnek a genuszával.

Egy gráf síkba rajzolása a gráfnak egy olyan diagramja (lerajzolása az euklideszi síkra), ahol az élek nem metszik egymást (csak a végpontjaikban). Egy gráf síkba rajzolható (síkgráf), ha van síkba rajzolása. Egy síkgráfot egy adott síkba rajzolásával együtt síkba rajzolt gráfnak hívunk. A példa gráf síkba rajzolható, bizonyítja ezt az ábrán látható egyik lehetséges síkba rajzolása; az n pontú teljes gráf nem rajzolható síkba, ha n > 4; de például minden fa síkba rajzolható.

Különböző síkbarajzolásokhoz különböző duális tartozik (csak a felső duálisban van 6-fokú pont)

Egy síkba rajzolás tartományokra (lap) osztja a síkot, néhány véges és egy végtelen, ún. külső tartományra. Két tartományt szomszédosnak hívunk, ha van közös határoló élük. Egy síkba rajzolt G gráf duális gráfja (jelölése G*) egy olyan gráf, melynek csúcsai G tartományai (beleértve a külső tartományt); és minden G-beli élnek megfelel egy él G*-ban, úgy hogy a duálisbeli él azt a két (nem feltétlenül különböző) csúcsot köti össze amelyek az eredeti él szomszédos tartományai. Vegyük észre, hogy két csúcs akkor és csak akkor szomszédos G*-ban, ha a megfelelő tartományok szomszédosak G-ben. Egy G síkgráf duálisa mindig egy síkbarajzolható multigráf (gondoljunk például a háromszög duálisára), de speciális esetben lehet egyszerű gráf is (például K4, amely izomorf a duálisával, azaz önduális). Minden 3-szorosan összefüggő egyszerű síkgráf (amely szükségképpen izomorf egy P konvex poliéder élhálójával) duálisa egy szintén 3-szorosan összefüggő egyszerű síkgráf (mely izomorf a duális poliéder, P* élhálójával).

Bármely síkgráf izomorf egy konvex poliéder élhálójának részgráfjával. A megfeleltetést sztereografikus projekció biztosítja.

A síkon értelme van a bentnek és a kintnek, így definiálhatjuk a gráf külső lapját, ha a síkba rajzolás nem fedi le az egész síkot. Ez az a végtelen lap, amit a gráf legkülső élei határolnak.


Egy gráfmetszési száma (jelölése cr(G)) a G beágyazásai közül a legkevesebb metszéspontot tartalmazó metszéspontjainak száma.

A G gráf vastagsága azon síkgráfok minimális száma, amennyi már elegendő G lefedéséhez.

Súlyozott gráfok és hálózatok[szerkesztés | forrásszöveg szerkesztése]

Súlyozott gráfban a gráf minden éléhez számértéket rendelünk, az él súlyát. Az élsúlyok legtöbbször valós számok, de adott esetben szorítkozhatunk racionális vagy egész számokra is. Néhány algoritmus még további megszorításokat követel, mint például a Dijkstra-algoritmus, amely csak pozitív (akár nemnegatív) élsúlyok esetén működik jól. Egy út súlya, vagy egy fa súlya az őt alkotó élek összsúlya. Néha egy nemlétező élet (anti-él) egy végtelen ∞ súlyú éllel helyettesítünk. Szokás költségnek is hívni a súlyt; de előfordul a hossz fogalmának félrevezető használata is, ui. egy út hossza súlyozatlan gráfban az éleinek száma, nem pedig összsúlya. Egy gráfról általában feltehető, hogy súlyozatlan, de bármely súlyozatlan gráfra gondolhatunk egy olyan súlyozott gráfként, melyben minden él súlya egységnyi 1.

Néhány gráfelméleti cikkben a hálózat a súlyozott gráf szinonimája. Egy hálózat lehet irányított, vagy irányítatlan, tartalmazhat két kitüntetett csúcsot, ezeket forrásnak és nyelőnek hívjuk. Klasszikus hálózati problémák például:

Irányított gráfok[szerkesztés | forrásszöveg szerkesztése]

Egy irányított él reprezentálható egy rendezett csúcspárral. Egy irányítatlan él esetében nincs különbség a végpontok között, azaz felcserélhetőek. Bár az irányított gráfbeli hurokél két végpontja megegyezik, így felcserélhetőek, nem tekintjük irányítatlannak. Néhány irányított él többszörös él, ha kezdődő- és végződő csúcsaik megegyeznek. Két él ellentétes irányú, ha az egyik kezdődő/végződő csúcsai a másik végződő/kezdődő csúcsai. Az irányított gráf (angolosan digráf) hasonló az irányítatlan gráfhoz, azzal a különbséggel, hogy élei irányítottak. Egy vegyes gráf tartalmazhat irányított és irányítatlan éleket is, így mindkét gráftípus általánosításának tekinthető. Ha egy gráf típusára nincs külön utalás, szinte mindig feltehető, hogy irányítatlan.

Egy irányított gráf egyszerű, ha hurokél- és többszörösél-mentes. Ha nincs utalás az ellenkezőjére, akkor általában feltehető, hogy a gráf egyszerű.

Egy Γ irányított gráfban különbséget teszünk kül-fok (ki-fok; jelölése dΓ+(v)), a v csúcsot elhagyó élek száma, és bel-fok (be-fok, jelölése dΓ+(v)), a v csúcsba érkező élek száma között. A v csúcs fokszáma (jelölése dΓ(v) a bel- és kül-fokainak összege. Ha a szövegkörnyezet egyértelművé teszi, akkor az alsó indexbeli Γ elhagyható. A gráfbeli legnagyobb és legkisebb külfok jelölése Δ+(Γ) és δ+(Γ); és legnagyobb és legkisebb belfok Δ-(Γ) és δ-(Γ).

Egy v csúcs utódainak halmaza (? 'out-neighborhood, or successor set'; jelölése NΓ+(v), kimenő élei végződő csúcsainak halmaza. Hasonlóan a v csúcs elődeinek halmaza (jelölése NΓ-(v)) a bejövő élei kezdőpontjainak halmaza.

Forrásnak hívunk egy csúcsot, ha be-foka 0; nyelőnek, ha ki-foka 0.

Egy irányított gráf Euler-gráf, ha a be- és ki-fokok csúcsonként egyenlők.

Egy irányítatlan vagy vegyes gráf egy irányítása az irányítatlan élekhez rendelt irányítás. Ha mást nem mondanak, akkor egyszerű irányítatlan gráfban minden irányítatlan élt irányítottal helyettesítenek.

A turnament olyan irányított gráf, melyben bármely két csúcs között pontosan az egyik irányban fut él. Az irányítatlan teljes gráfból úgy kapunk tournamentet, ha minden élet egy tetszőleges irányítással látunk el, ezért hívják teljes irányított gráfnak is (ez az egyértelműséget sugalló elnevezés kissé félrevezető, mert az n csúcsú turnamentek általában nem izomorfak, nem úgy, mint az n csúcsú teljes gráfok).

Egy irányított út (vagy csak út, ha a szövegkörnyezet egyértelmű) egy olyan egyszerű út, melynek minden éle ugyanabba za irányba mutat, azaz minden belső csúcsának be- és ki-foka is 1. Egy v csúcs elérhető egy u csúcsból, ha van olyan iránytott út, amely u-ból indul és v-ben végződik. Vegyük észre, hogy ha u-ból v elérhető, abból általában nem következik, hogy v-ből u is elérhető.

Ha v elérhtő u-ból, akkor u elődje v-nek, illetve v utódja u-nak. Ha van irányított él u-ból v-be, akkor v az u közvetlen utódja és u a v közvetlen őse. Az előbbiekkel egyenértékűek a leszármazott és ős elnevezések, de szülőgyerek viszonyról általában csak gyökeres fák esetében beszélünk.

Egy irányított gráf erősen összefüggő, ha minden csúcs minden más csúcsból elérhető (irányított úton); és gyengén összefüggő, ha az alapul szolgáló irányítatlan gráf összefüggő. Egy gyengén összefüggő gráfra gondolhatunk úgy, mint egy irányított gráf melyben minden csúcs minden csúcsból „elérhető”, ha az élek irányításáról megfeledkezhetünk. Az erős irányítás (?: 'strong orientation') éleknek egy olyan irányítása, mely erősen összefüggő gráfot eredményez.

Egy irányított kör (vagy csak kör, ha egyértelmű) egy olyan egyszerű kör, melyben minden él ugyanabba az irányba mutat, azaz minden csúcsának be- és ki-foka is 1. Egy irányított gráf körmentes (aciklikus), ha nincs benne irányított kör (angolul directed acyclic graph; lásd DAG).

A fenyő egy olyan irányított fa, amiben egy csúcsból minden csúcs elérhető.

Színezések[szerkesztés | forrásszöveg szerkesztése]

Egy színezés a gráfelméletben „színeket” (kék, zöld stb., de lehetnek természetes számok is az általánosságot megőrizve) rendel a gráf elemeihez. Ezek az elemek lehetnek csúcsok, élek, tartományok, vagy ezeknek a keverékei.

Egy gráf színezése alatt (hacsak a szövegkörnyezet nem utal másra) általában a gráf csúcsainak színezését értjük. Egy színezés (helyes, megfelelő), ha a szomszédos csúcsok különböző színűek. Egy gráf k színnel színezhető, ha van legfeljebb k színt használó jó színezése. Egy G gráf kromatikus száma (jelölése χ(G)) az a legkisebb k szám, amelyre G k színnel színezhető.

Egy gráf élszínezése jó, ha a szomszédos élek különböző színűek. Egy gráf k színnel élszínezhető, ha van legfeljebb k színt használó jó élszínezése. Egy G gráf élkromatikus száma (jelölése χe(G)) az a legkisebb k szám, amelyre G k színnel élszínezhető.

Lásd még[szerkesztés | forrásszöveg szerkesztése]