Középiskolai tanulmányainkból tudjuk, hogy a gráf bizonyos elemek és a köztük fennálló közvetlen kapcsolatok halmaza.

Az elemeket csomópontoknak, a kapcsolatokat pedig éleknek nevezzük, illetve grafikusan pontokkal és szakaszokkal ábrázoljuk.

Például:

• egy társaság tagjai a pontok, és azok között van él, akik ismerik egymást;
• csapatok a pontok, az élek a lejátszott mérkőzések;
• összes dolgozó a közvetlen főnökkel összekapcsolva;
• tömegközlekedési útvonalak a rajtuk lévő megállókkal;
• települések a köztük lévő közvetlen vasúti összeköttetéssel.

Rajzoljunk gráfokat a fenti példák mindegyikére!

Ismételjük át a legfontosabb gráfelméleti fogalmakat!

Hurok az önmagába vezető él. Például mindenki ismerheti önmagát.

Izolált pont, melyből/melybe nem vezet él. Például egy csapat, amelyik még egy mérkőzést sem játszott.

Egyszerű gráf, amelyben bármely két pont között legfeljebb egy él van és nincs benne hurok. A tömegközlekedési útvonalak általában nem egyszerű gráfot alkotnak; a mérkőzések pedig csak akkor, ha két csapat pontosan egyszer játszik egymással.

Ha az élekhez irányítást is rendelünk, irányított gráfot kapunk (a nem szimmetrikus kapcsolatok kifejezésére). Például a nyertes mérkőzések jelölésére, a ki-kinek a főnöke, a mi-mibe épül be, a járat-irányok, esetleg a ki-kit szeret kapcsolat kifejezésére. A szimmetrikus kapcsolatokat gyakran érdemesebb irányítás nélkül ábrázolni, mint két darab egyirányú éllel.

Két pontot összekötő út a kezdőpontból a végpontba tartó, egymáshoz csatlakozó élek sorozata, mely egyetlen ponton sem megy át kétszer.

Körút az olyan út, amelynek a kezdő- és végpontja megegyezik.

Összefüggő a gráf, ha bármely két pontja között van út.

Az összefüggő körmentes gráf speciális névvel rendelkezik, ez a fa; speciális irányítással az ún. gyökeres fa. A fában egy kitüntetett pont a gyökér, melyen kívül az összes többi pontnak (utódnak) van megelőzője (szülője), ami a gyökérből a pontba vezető körmentes útban a pontot megelőző pont. Például egy szervezeti felépítés, a részalkatrészek egymásba épülése, a lemezek könyvtárszerkezete stb. a hierarchiát jól érzékeltető fa. Célszerű ezt a speciális irányítást az utódtól a szülő felé jelölni - ha egyáltalán jelölni akarjuk -, mert fordítva nem egyértelmű. A számítástechnikában kiemelt jelentőségű a bináris fa, amely minden pontjából legfeljebb két utód indul. A fák „leghasznosabb" tulajdonsága, hogy a fa bármely pontjából bármely pontjába - irányított élek előfordulása esetén csak a gyökérig - úton el lehet jutni.

Jelen fejezetbe nem a bináris fa alkalmazása és annak bejárási algoritmusa kívánkozik, hanem a gráfoknak a számítógép számára értelmezhetővé tétele. A gráf szomszédsági mátrix vagy lista használatával tehető „emészthetővé" a számítógép számára.

A gráfok implementációja

Az A szomszédsági mátrix a_ij eleme lehetne logikai érték, attól függően, hogy az i. és j. pont között van-e él. Természetesen az értékek lehetnének számok, a többszörös élek megjelenítésével akár nem csak 0-k vagy 1-ek. A nem irányított gráf mátrixa biztosan szimmetrikus a főátló szerint.

A szomszédsági mátrixban az élek tárolása ritka gráf esetén igencsak gazdaságtalan, ugyanakkor könnyen karbantartható és gyorsan lekérdezhető.

Ha csak a meglévő éleket tároljuk el gazdaságossági megfontolásból (2 vektor is elegendő ennek megoldására), akkor nehézkesebb lesz az élek felvitele és törlése, valamint több keresést igényelnek majd a lekérdezések.