Gráfelméleti fogalomtár

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

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.

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 = {1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {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 ${\displaystyle {\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 ${\displaystyle {\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

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 (spanning subgraph) G-nek, ha csúcshalmaza megegyezik G-ével. Ekkor H kifeszíti G-t.

Egy H részgráf feszített részgráfja (induced subgraph) G-nek, ha H bármely két csúcsára igaz, hogy pontosan akkor szomszédosak H-ban, 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 csúcsait é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.

Egy gráf minorja egy olyan gráf, amely megkapható belőle élek törlésével, összehúzásával, izolált csúcsok törlésével, kettős élek és hurokélek megszüntetésével.

Számos gráfcsalád jellemezhető a benne részgráfként elő nem forduló struktúrákkal, lásd Tiltott gráfok szerinti osztályozás.

Séták

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 ${\displaystyle P_{n}}$-nel illetve ${\displaystyle 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 C_n-nel jelöljük. C₁ egy hurokél, C₂ két kétszög, azaz egy többszörösél-pár, C₃ 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 (→irányított körmentes gráf).

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

Bővebben: Fa (gráfelmélet)

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. Olyan kontextusban, ahol a fák általában gyökeresek, a nem gyökeres fákat szabad fáknak is nevezik.

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 ${\displaystyle K_{1,k}}$.

Az n-edfokú fa (n-áris fa) egy gyökeres fa, amelyben minden csúcsnak legfeljebb n gyereke van. A teljes n-edfokú 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).

A hernyó olyan fa, melynek az összes csúcsa egy központi úttól legfeljebb egy él távolságra található.

Klikkek

Bővebben: klikk (gráfelmélet)

Az n csúcsú teljes gráf (jelölése ${\displaystyle 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. ${\displaystyle K_{n}}$ éleinek száma az összes lehetséges csúcspárok száma, azaz ${\displaystyle |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

Bővebben: Erősen összefüggő komponens

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

Bővebben: Gráftulajdonság

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 ${\displaystyle 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úcsainak fokszámait tartalmazza nemnövekvő sorrendben (például d₁ ≥ d₂ ≥ … ≥ d_n). Egy ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 (${\displaystyle 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 páros, és a párosítás egy-egy oldalán a fokszámok megegyeznek.

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

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 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 a₁, a₂, … a_n, jelölése ${\displaystyle K_{a_{1},a_{2},\dots ,a_{n}}}$. A K_{a, 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

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ó csúcshalmaz vagy 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 K_n 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 = {S, T} vágás (cut) G-ben a csúcshalmaz kétosztályú partíciója két nemüres csúcshalmazba. S és T a vágás két osztálya vagy partja. Az E(V) = {e ∈ E(G) : e két végpontja különböző partra esik} a V vágás élhalmaza (cut-set). V egy x-y vágás, ha x ∈ S és y ∈ T. Ha egy hálózatban beszélünk vágásról, akkor az mindig egy s-t vágás, tehát a forrás és a nyelő különböző osztályba esik.^[1] Szokás a vágás élhalmazát (cut-set) is vágásnak nevezni. Ebben az értelemben 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 K₃ élei elvágó élhalmazt alkotnak, de vágást nem. Bármely két él K₃-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, hídé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éldá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

Két csúcs távolsága (jelölése d_G(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 egybeesnek, 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 a grá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 periferikus 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 ${\displaystyle 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 ${\displaystyle u,v\in G.}$ Egy irányítatlan gráf Wiener-polinomja a ${\displaystyle \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 tartalmazó 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.

Ennek a szakasznak egy része vagy egésze lefordítandó. Segíts te is a fordításban!

Sűrűség

Bővebben: Sűrű gráf

Egy gráf sűrűsége alatt egy véges gráfban az élek lehetséges maximális számának és a tényleges számának az arányát értjük. Jele D, szélső értékei a teljes gráfnál értéke 1, az üres gráfnál 0. Egy gráf sűrű, ha az élek száma közel áll az élek maximális lehetséges számához, ritka, ha ennél jóval kevesebb – az, hogy mi számít sűrűnek vagy ritkának, a szövegkörnyezettől függhet.

Egy (k,l)-ritka gráf (sparse graph) minden nem üres részgráfjának n csúcsa között legfeljebb kn − l él húzódik, a (k,l)-éles gráf (tight graph) (az „éles” szó itt a matematikai zsargonban használt, tovább már nem javítható eredményre utal) pedig (k,l)-ritka és pontosan kn − l éllel rendelkezik.

Végtelen gráfoknál értelmezhetők valahol sűrű és sehol sem sűrű gráfosztályok.

Gráfok lerajzolása

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, és az élek csak a csúcsokban metszik egymást. Kevésbé szigorú értelemben beágyazásnak tekintik azt is, amikor az élek metszhetik egymást. Ilyenkor beszélhetünk beágyazásról és metszésmentes beágyazásról. Előbbi esetben a 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 génuszút. Az adott G gráf génusza egyenlő ennek a felületnek a génuszá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ó.

A Fáry-tétel értelmében minden síkgráf síkba rajzolható csupa egyenes szakaszú élekkel is; ezt a reprezentációt egyenes élű síkgráfnak nevezzük.

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 K₄, 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 külsíkgráf vagy outerplanar gráf (esetleg: outerplanáris gráf) olyan gráf, mely síkba rajzolható úgy, hogy minden csúcsa a külső tartománnyal szomszédos legyen.

Egy gráf metszé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

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:

• legrövidebb utak keresése,
• minimális költségű feszítőfa keresése,
• maximális–folyam–minimális–vágás-tétel.

Irányított gráfok

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 turnamentet, 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 az 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ányított ú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érhető 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 irányított körmentes gráf).

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

Gráfműveletek

Bővebben: Gráfművelet

Egy gráfművelet olyan művelet, mely gráf(ok)hoz rendel gráfot.

Elemi műveletnek tekintjük valamely él vagy csúcs törlését, csúcsok összevonását és szétválasztását.

Az élösszehúzás (edge contraction) olyan gráfművelet, ami a gráf egy élét eltávolítja, miközben az él által korábban összekötött két csúcsot összeolvasztja.

A csúcsazonosítás a művelet kevésbé korlátozott formája: megszünteti azt a korlátozást, hogy az „összehúzásnak” egy éllel összekötött két csúcs között kell végbemennie.

A csúcshasítás vagy csúcsszétvágás azt jelenti, hogy egy v csúcsot helyettesítünk a szomszédos v′ és v′′ csúcsokkal, az e = vu éleket pedig vagy a v′u, vagy a v′′u fogja helyettesíteni, tehát ha az eredeti csúcs szomszédos volt a gráf egy csúcsával, akkor a két új csúcs közül legalább az egyik szomszédos lesz vele. A csúcsazonosítás fordított művelete.

Az útösszehúzás során egy út összes éleit húzzuk össze egyetlen, az út végpontjai közötti éllé.

Összetett unáris gráfműveletek:

• Élgráf: élgráfképzéskor a csúcspontok az eredeti gráf élei, és két csúcs akkor van összekötve, ha az eredeti gráfban a két élnek volt közös végpontja.
• Duális gráf: síkbarajzolt gráf duális gráfja alatt azt a gráfot értjük, amelynek csúcsai az eredeti gráf tartományai, és azok a csúcsok vannak összekötve, amik megfelelői szomszédos tartományok voltak (ha több él mentén voltak szomszédosak, akkor többszörösen is). Síkbarajzolt gráf duálisa is síkbarajzolható gráf.
  • A gyenge duális képzésekor csak a korlátos tartományok csúcsaival foglalkozunk.
• Komplementer gráf: valamely ${\displaystyle G=(V,E)}$ gráf komplementer gráfja az a gráf, amelynek csúcshalmaza megegyezik a G gráf csúcshalmazával, az élhalmaza pedig a G gráf élhalmazának a komplementer halmaza (a teljes gráf élhalmazára, mint alaphalmazra nézve).
• Gráfminor: olyan gráf, amely megkapható az eredeti gráfból élek törlésével, összehúzásával, izolált csúcsok törlésével, kettős élek és hurokélek megszüntetésével.
• Gráfhatvány: valamely G=(V,E) gráf k-adik hatványa az a (V,F) gráf, amely tartalmazza élként azokat a csúcspárokat, amelyek távolsága a G gráfban legfeljebb k. Valamely gráf második hatványát nevezik a gráf négyzetének is.

A bináris (vagy binér) gráfműveletek gráfpárokhoz rendelnek hozzá gráfokat. Ilyen a diszjunkt unió és a gráfszorzás (lexikografikus vagy tenzor-).

Színezések

Bővebben: Gráfok színezé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 jó (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ő.

Egyéb

• Split gráf: olyan gráf, mely kettébontható egy klikkre és egy független halmazra.
• Fafelbontás (branchwidth), fafelbontás szélessége
• Favastagság (treewidth): egy gráf minimális fafelbontásának szélessége

Kapcsolódó szócikkek

• Gráf (halmazelmélet)

Jegyzetek

1. Hajnal Péter: Gráfok magasabb fokú összefüggősége, folyamok