5.3. Gráfelméleti alapfogalmak

Egy G gráf két halmazból áll: a csúcsok vagy pontok V halmazából, ami egy nemüres halmaz, és az E élek halmazából, melynek elemei V -beli párok. Ha ezek a párok rendezettek, akkor irányított, ellenkező esetben irányítatlan gráfokról beszélünk. Gyakran csak arra vagyunk kiváncsiak, hogy két csúcs között van-e él, míg máskor ehhez az élhez valamilyen költségeket is rendelünk. Úton egy olyan v1, . . . , vk csúcssorozatot értünk, melyre (vi, vi+1) éle a gráfnak. Az utat körnek nevezzük, ha kezdő- és végpontja megegyezik (ám nincs más közös pontja). A csúcsok halmazán értelmezhetünk egy relációt aszerint, hogy a két kiválasztott csúcs között (az irányítástól eltekintve) vezet-e út. Ezen ekvivalenciareláció ekvivalenciaosztályait komponenseknek hívjuk. Egy körmentes gráfot erdőnek nevezünk, s az egy komponensből álló erdőt fának. A bináris fa egy olyan fa, melynek a csúcsai szinteken helyezkednek el. A legfelső szinten pontosan egy csúcs van, ezt gyökérnek nevezzük. Egy tetszőleges x csúcsból legfeljebb két csúcs indul ki, ezek eggyel alacsonyabb szinten levő csúcsokhoz vezetnek. A balra menő él végpontja az x bal fia, a jobbra menő él végpontja az x jobb fia. Azokat a csúcsokat, melyeknek nincs fia, leveleknek nevezzük. Az alábbi ábrán látható egy bináris fa.

Az informatikában megszokott módon a fák ábrázolásakor a fa gyökere kerül felülre, és a levelek alulra. Az ábrán láthetó fa speciális, teljes fa. A teljes fa levelei két szinten helyezkednek el, és legfeljebb egy kivétellel minden nem levél csúcsnak két fia van. Ha pedig sorfolytonosan tekintjük a fát, egyik csúcsnak sincs kevesebb fia, mint a sorban utána következőnek. Az ilyen fát tárolhatjuk tömbben, illetve egy tömböt tekinthetünk fának. Az előbbi fa csúcsaiban szereplő számok a tömb megfelelő elemeinek az indexét jelölik. Ha a fa csúcsai az A tömb 1, . . . , n elemei, akkor az A[i] bal fia A[2i], míg a jobb fia A[2i+1]. Hasonlóan, ha j ≥ 1, akkor az A[j] apja A[b i 2c], ahol az bˇc az egészrész függvényt jelenti. Például az A[5] fiai az A[10] és az A[11] csúcsok, míg az A[9] és A[8] csúcsok apja az A[4] csúcs.