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 A 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 halmazra, amelyen illeszkedési reláció van értelmezve , amely egy élhez egy csúcspárt rendel, az él végpontjait.
Az éleket elláthatjuk 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 a csúcsok halmazán értelmezett bináris reláció (→Gráf (halmazelmélet)), vagy négyzetes, 0-kból és 1-kből álló mátrix.
A 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. A gráf rendje a csúcsok száma, azaz |V(G)|.
Az él (két alapelemből álló halmaz) képe a diagramon vonal, amely két csúcsot köt össze, ezeket végpontoknak hívjuk. Az é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.
A hurokél vagy hurok olyan él, amelynek két végpontja ugyanaz a csúcs. Az é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. A 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 a 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.
thumb|250px|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). A hiperél egy olyan él, amely akárhány csúcsot összeköthet, akár több mint 2-t. Az olyan gráfot, amelyben lehetnek hiperélek hipergráfnak hívunk. Az egyszerű gráf tekinthető a hipergráf speciális esetének, ahol minden él pontosan két csúcsot köt össze. Az é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.
Az anti-él 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 az (x,y) él akkor és csak akkor van benne -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. Az olyan gráfot, amelyben minden csúcs fokszáma véges lokálisan véges gráfnak hívjuk. A 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 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).
A 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.
A 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.
A gráfot, amelyik nem tartalmazza H-t feszített részgráfként H-mentesnek hívunk.
A gráf minorja 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. A 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) 5 hosszú nyitott séta, és (4, 5, 2, 1, 5, 4) 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) 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 hurokél, C2 két kétszög, azaz többszörösél-pár, C3 egy háromszög.
A kört páros körnek hívunk, ha a hossza páros, különben páratlan kör. Tétel az, hogy a gráf páros akkor és csak akkor, ha nem tartalmaz páratlan kört (→páros gráf).
A 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).
Az út (kör) Hamilton-út (Hamilton-kör), ha minden csúcsot pontosan egyszer érint (azaz feszítő). A 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.)
A 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 az 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 összefüggő, körmentes egyszerű gráf. A fa elsőfokú csúcsait levélnek hívjuk. A nem levél csúcs a fában belső csúcs. Néha van a fának 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, összefüggő részgráfja T-nek.
Erdőnek hívjuk a 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ő részerdője F részgráfja.
A feszítő fa 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-edfokú fa (n-áris fa) 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 ú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
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). Így a példa gráf klikkszáma (klikkmérete) 3.
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
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ú 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 d1 ≥ d2 ≥ ... ≥ dn). Egy 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 ) 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 ). 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 ().