„Gráfelméleti fogalomtár” változatai közötti eltérés

A Wikipédiából, a szabad enciklopédiából
[nem ellenőrzött változat][nem ellenőrzött változat]
Tartalom törölve Tartalom hozzáadva
Illes (vitalap | szerkesztései)
a →‎Klikkek: rang->rend
Illes (vitalap | szerkesztései)
191. sor: 191. sor:
== Távolság ==
== Távolság ==


Két csúcs '''távolság'''a (jelölése ''d''<sub>''G''</sub>(''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 eléhető egyikből a másik) akkor távolságuk definíció szerint [[végtelen]] ∞.
Két csúcs '''távolság'''a (jelölése ''d''<sub>''G''</sub>(''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ás'''a (jelölése ε<sub>''G''</sub>(''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.
Egy csúcs '''excentricitás'''a (jelölése ε<sub>''G''</sub>(''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 lap 2007. január 28., 15:18-kori változata

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

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 = {{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 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 -ben, ha (x,y) nincs benne G-ben. Az egy csúcsponttal és nulla éllel rendelkező 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 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

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 -nel illetve -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

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észedő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 .

Az n-áris fa egy gyökeres fa, amelyben minden belső csúcsnak n gyereke van. Az 1-áris fa egy út. A 2-áris 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 jobboldali gyerekek között.)

Klikkek

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

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).

Erősen összefüggő komponens

Szomszédság és fokszám

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 ) 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ú cúcsok 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 fokszám sorozat megvalósítható, ha van olyan gráf, melynek ez a fokszám sorozata.

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 ) azok a csúcsok mellyekkel 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 ). 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 ().

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 adjacencia mátrixával (másnéven szomszédsági mátrix): 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

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ásné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 (? 'partite set, or simply part') 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 . 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ásné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ó 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).

Távolság

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.


A szócikk egy része még lefordítandó. Segíts te is a fordításban!

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úsok 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.

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

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íkbarajzolá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íkbarajzolt 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).

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

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

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 minden be- és ki-fokok csúcsonként egyenlők.

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ú tournamentek általában nem izomorfak, nem úgy, mint az n pontú 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).

Lásd még


A szócikk egy része még lefordítandó. Segíts te is a fordításban!