Gráfok tulajdonságai

Az ábrán egy szociális hálózat egyik lehetséges megjelenítését rajzoltuk fel:

Két név közötti vonal azt jelenti, hogy ezek az emberek ismerik egymást. Ha két név között nincs vonal, akkor ők nem ismerik egymást. Az „ismerik egymást” reláció mindkét irányban érvényes: például, ha Audrey ismeri Gaylet, akkor egyben az is igaz, hogy Gayle ismeri Audreyt.

Ez a szociális hálózat egy gráf. A nevek a gráf csúcspontjai vagy csúcsai. A vonalak az élek, amik két csúcspontot kötnek össze. Az $u$u és $v$v csúcsokat összekötő élt az $(u,v)$left parenthesis, u, comma, v, right parenthesis párossal jelöljük. Mivel az „ismerik egymást” reláció kétirányú, ez a gráf irányítatlan. Az irányítatlan $(u,v)$left parenthesis, u, comma, v, right parenthesis él megegyezik a $(v,u)$left parenthesis, v, comma, u, right parenthesis éllel. Később találkozni fogunk irányított gráffal is, amiben a csúcsok közötti reláció nem feltétlenül érvényes mindkét irányban. Egy irányítatlan gráfban két csúcspont közötti él, mint például az Audrey és Gayle közötti él illeszkedik a két csúcspontra, valamint azt mondjuk, hogy két csúcspont, amit összeköt egy él, szomszédosak. A csúcsponthoz illeszkedő élek száma adja meg a csúcspont fokát.

Audrey és Frank nem ismerik egymást. Tegyük fel, hogy Frank szeretne megismerkedni Audreyval. Hogyan találhat valakit, aki be tudná őt mutatni Audreynak? Frank ismeri Emilyt, aki ismeri Billt, aki ismeri Audreyt. Azt mondjuk, hogy Frank és Audrey között van egy három él hosszú út. Igazság szerint ez a legközvetlenebb módja annak, hogy Frank megismerhesse Audreyt; nincs közöttük háromnál kevesebb élt tartalmazó útvonal. A két csúcspont közötti legkevesebb élt tartalmazó útvonalat legrövidebb útnak nevezzük. Az alábbi ábrán vastag vonallal jelöltük ezt a szóban forgó legrövidebb utat.

Az olyan útvonalat, amely egy adott csúcspontból visszavezet ugyanabba a csúcspontba, körnek nevezzük. A szociális háló számos kört tartalmaz; az egyik ilyen például Audreytól Billhez, majd Emilyn keresztül Jeffhez, Harryhez, Ilanához végül vissza Audreyhoz vezet. Van egy rövidebb kör Audreyval, amelyet a lenti ábrán mutattunk meg. Ebben Audrey, Bill, Gayle, végül megint Audrey van összekötve. Találsz-e ezen kívül más köröket?

Előfordul, hogy számokat rendelünk az élekhez. Például a szociális hálóban számokkal jellemezhetjük azt, hogy két ember mennyire jól ismeri egymást. Egy másik példa lehet, amikor gráffal ábrázolunk egy úthálózatot. Tegyük fel, hogy nincsenek egyirányú utak, ilyenkor a térkép egy irányítatlan gráf, ahol a városok a csúcspontok, az utak az élek, és az élekhez rendelt értékek az egyes utak hosszát mutatják. Például alább látható egy nem méretarányos térkép, melyen az Egyesült Államok északkeleti részén található országutakat tüntettünk fel. A távolságokat hozzárendeltük az élekhez:

Általánosságban az élekhez rendelt számokat az él súlyának nevezzük, és azokat a gráfokat, ahol az élekhez súlyok tartoznak, súlyozott gráfnak hívjuk. A térkép esetében, amikor két helység között a legrövidebb utat keressük, akkor arra az útvonalra van szükségünk, ahol a két csúcs közötti utakhoz rendelt súlyok összege a legkisebb. A súlyozatlan gráfhoz hasonlóan ezt ez útvonalat is legrövidebb útnak nevezzük. Például ezen a gráfon a legrövidebb út New Yorkból Concordba New Yorkból New Havenen, Hartfordon, Sturbridgen, Westonon, Readingen át vezet Concordba 289 mérföld hosszan.

A csúcsok közötti kapcsolat nem mindig kétirányú, a térképen megjelölhetünk egyirányú utakat. Az alábbi gráf például azt mutatja, milyen sorrendben öltözhet fel egy jéghoki kapus:

Most az élek, melyeket nyilakkal láttunk el, irányítottak, ami irányított gráfot eredményezett. Itt az irányok azt mutatják, hogy a felszerelés mely darabjait kell a többi ruhadarab előtt felvenni. Például a mellvédőtől a pulcsi felé vezető él azt jelöli, hogy a mellvédőt a pulóver előtt kell felvenni. A csúcsok melletti számok a sok közül egy lehetséges felöltözési sorrendet mutatnak, mely szerint először az alsónadrágot vesszük fel, majd a zokni jön, ezután a kompressziós nadrág és így tovább, a blokkoló lesz az utolsó. Megfigyelhetted, hogy ebben az irányított gráfban nincsen kör; az ilyen gráfokat irányított körmentes gráfnak hívjuk (találkozhatsz még a dag rövidítéssel az angol directed acyclic graph rövidítéséből). Persze létezik súlyozott irányított gráf is, ilyen az úthosszakat is feltüntető egyirányú utakat tartalmazó térkép.

Különböző terminológiát alkalmazunk irányított élekkel kapcsolatban. Azt mondjuk, hogy egy irányított él kiindul az egyik csúcspontból és beérkezik egy másikba. Például az egyik irányított él kiindul a mellvédő csúcsból és beérkezik a pulcsi csúcsba. Ha egy irányított él kiindul az $u$u csúcspontból és beérkezik a $v$v csúcspontba, ezt így jelöljük: $(u,v)$left parenthesis, u, comma, v, right parenthesis, ahol fontos a csúcspontok sorrendje a párosban. Az egy csúcsból kiinduló élek száma a csúcspont kifoka, a csúcsba beérkező élek száma pedig a csúcspont befoka.

A gyakorlatban mind az irányított, mind az irányítatlan gráfokat sokszor használják a valós világ kapcsolatainak modellezésére.

Amikor gráfokkal foglalkozunk, megkönnyíti a dolgunkat, ha csúcspontok és élek halmazában gondolkodunk. Általában a csúcspontok halmazát $V$V-vel (vertices), az élek halmazát $E$E-vel (edges) szokás jelölni. Amikor ábrázolunk egy gráfot, vagy egy algoritmust futtatunk a gráfon, akkor gyakran a csúcspontok és élek halmazának méretét használjuk az aszimptotikus jelölésben. Például tegyük fel, hogy a futásidő a csúcspontok számának lineáris függvénye. Precíz jelölési konvenció alapján ezt – alkalmazva a $|\cdot|$vertical bar, dot, vertical bar jelölést a halmaz méretére – így írjuk: $\Theta(|V|)$\Theta, left parenthesis, vertical bar, V, vertical bar, right parenthesis. A halmazméret jelölés használata azonban kényelmetlen az aszimptotikus jelölésben, ezért bevezetjük azt a konvenciót, hogy az aszimptotikus jelölésben, de kizárólag az aszimptotikus jelölésben, elhagyjuk a halmazméret jelölést, és megállapodunk abban, hogy itt halmazok méretéről beszélünk. Így $\Theta(|V|)$\Theta, left parenthesis, vertical bar, V, vertical bar, right parenthesis helyett egyszerűen $\Theta(V)$\Theta, left parenthesis, V, right parenthesis-t írunk. hasonló módon $\Theta(\lg |E|)$\Theta, left parenthesis, \lg, vertical bar, E, vertical bar, right parenthesis helyett $\Theta(\lg E)$\Theta, left parenthesis, \lg, E, right parenthesis-t írunk.

Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tanmenetfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.