10.6 Gráfok bejárása

Legyen u és v a G gráf - nem szükségképpen különböző - két csúcsa.  Egy W-vel jelölt u-v séta a G gráfban a csúcspontoknak és az éleknek egy olyan W: u = u0,e1,u1,e2,u2,....,uk-1,ek,uk = v véges, alternáló sorozata, amely az u csúcsponttal kezdődik, a v csúccsal végződik, és ei = ui-1ui mindig egy él, i=1,2,...,k. A k számot a W séta hosszának nevezzük.

Egy u-v sétát zártnak vagy nyitottnak nevezünk attól függően, hogy  u = v vagy
uv.

9.ábra. Példa egy 6 hosszúságú sétára

Az u-v ösvény az egy olyan u-v séta, amelyben él nem ismétlődik, és egy u-v út az egy olyan u-v séta, amelyben csúcspont nem ismétlődik.

Megjegyzés.

A fenti definíciókból azonnal következik, hogy minden út egyben ősvény is, és minden út egyben séta is, de a megfordítottja általában nem igaz. Tekintsük a következő gráfot:

A fenti gráfban

  • egy v1-v4 séta de nem ösvény.
  • egy ösvény de nem út.
  • egy út.

A következő tétel a szomszédsági mátrix egy hasznos felhasználását mutatja be:

Tétel 10.2: Ha A a G szomszédsági mátrixa, és V(G) = {v1,v2,...,vn}, akkor az Ak hatványmátrix (i,j) eleme, k ³ 1, megadja a k hosszúságú vi-vj séták számát a G gráfban.

A tételt nem bizonyítjuk, de mutatunk egy példát az alkalmazásra. Legyen G a következő gráf:

Határozzuk meg a gráfban a 3 hosszúságú utak számát a v1 és a v3 csúcsok között. Ehhez meg kell határoznunk az A3 mátrixot:

Az A3 mátrix a1,3 = 4 eleme mutatja, hogy a v1 és v3 csúcs között összesen 4 különböző út található. Valóban: , , , .

Egy nem triviális zárt ösvényt körútnak nevezünk, és azt a körutat, amelyben n különböző csomópont szerepel, körnek nevezzük.

Egy aciklikus gráfban nincs kör. Az aciklikus gráfot fának nevezzük, és T(n, n-1)-gyel jelöl-jük. (Világos: egy n csúcsú fának mindig n-1 éle van!)

Egy kör páros, ha hossza páros, egyébként a kör páratlan. Egy k hosszúságú kört k-körnek nevezünk. A 3-kör a háromszög. Azt az n-ed rendű gráfot, amely út, Pn jelöli, és Cn egy n csúcspontú kört jelöl.

Egy u csúcsról azt mondjuk, hogy összeköthető a v csúccsal, a gráfban létezik egy u-v út. Egy gráf összefüggő, ha bármely két csúcsa összeköthető. Egyébként a gráf nem összefüggő.

Tétel 10.3: Egy G gráf csúcshalmazán értelmezett „összefüggő" reláció egy ekvivalencia reláció.

Azokat a részgráfokat, amelyek az ekvivalencia reláció eredményeként létrejött ekvivalencia osztályoknak felelnek meg, a G gráf összefüggő komponensének nevezzük. A G gráf komponenseinek számát k(G) jelöli.

Egy összefüggő gráfban az u és v csúcsok d(u,v) távolságán  a két csúcspont között megadható u-v utak minimális hosszát értjük.

10.a. ábra. Példa a v1 csúcstól mért távolságokra

A 10. ábrán a csúcsok mellé írt számok mutatják az adott csúcsnak a v1 csúcstól való távolságát. Egy adott csúcstól azonos távolságra lévő csúcspontok szinteket alkotnak:

10.b. ábra. A v1 csúcstól mért távolságok alapján definiált szintek.

Figyeljük meg, hogy a 10.a és a 10.b ábrán látható két gráf izomorf egymással!