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
u ≠ v.
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!