Gr´ afelm´ eleti feladatok d e
c f
a
b
s´ eta: a, b, c, d, e, c, a, b, f vonal: c, d, e, c, b, a ut: f, b, a, e, d ´
gr´ af, cs´ ucsok, ´ elek (walk, lant ¸) (trail, lant ¸ simplu) (path, lant ¸ elementar) 1
ir´ any´ıtott gr´ af, ir´ any´ıtott cs´ ucsok, ir´ any´ıtott ´ elek ir´ any´ıtott s´ eta ir´ any´ıtott vonal ir´ any´ıtott ´ ut
(directed walk, drum) (directed trail, drum simplu) (directed path, drum elementar)
2
Gr´ afnak nevezz¨ uk a G = (V, E, G) rendezett h´ armast, ahol V cs´ ucsok (vagy sz¨ ogpontok esetleg pontok) nem ¨ ures halmaza, E ´ elek halmaza, G :E →V ⊗V. Ha G(e1) = G(e2), akkor e1 ´ es e2 p´ arhuzamos vagy t¨ obbsz¨ or¨ os ´ elek. Ha G(e) = {a, a}, akkor az e ´ el hurok´ el. Ha G(e) = {a, b}, akkor azt mondjuk, hogy az a ´ es b cs´ ucsokat az e ´ el k¨ oti ¨ ossze, a ´ es b szomsz´ edosak, az e ´ el illeszkedik az a ´ es b cs´ ucsokra, az a ´ es b cs´ ucsok az e ´ el v´ egpontjai. 3
Az a ´ es b cs´ ucsokra illeszked˝ o (p´ arhuzamos) ´ elek halmaza: G −1(a, b) = {e ∈ E | G(e) = {a, b}}. Legyen x a G gr´ af egy cs´ ucsa. Jel¨ olj¨ uk NG(x)-szel vagy csak N (x)-szel az x-szel szomsz´ edos cs´ ucsok halmaz´ at: NG(x) = {y ∈ V (G) | ∃e ∈ E(G), G(e) = {x, y}} vagy NG(x) = {y ∈ V (G) | G −1(x, y) 6= ∅.} A G gr´ afban az x-hez illeszked˝ o ´ elek (amelyek nem hurok´ elek) halmaza: IG(x) = {e ∈ E(G)|∃y ∈ V (G), y 6= x, G(e) = {x, y}} Az x-hez illeszked˝ o hurok´ elek halmaza: LG(x) = {e ∈ E(G)|G(e) = {x, x}} 4
Az x cs´ ucs foksz´ ama vagy foka, amelyet ϕ(x)-szel jel¨ ol¨ unk, az x-hez illeszked˝ o´ elek sz´ ama (a hurok´ eleket k´ etszer sz´ amolva): ϕ(x) = |IG(x)| + 2|LG(x)|. Ha ϕ(x) = 0, akkor x izol´ alt cs´ ucs. Ha ϕ(x) = 1, akkor x lev´ el. Egy t¨ obbsz¨ or¨ os ´ eleket ´ es hurok´ eleket nem tartalmaz´ o gr´ afot egyszer˝ u gr´ afnak nevezz¨ uk. Ha G egyszer˝ u gr´ af, akkor |G −1(a, b)| ≤ 1 tetsz˝ oleges a, b ∈ V cs´ ucsokra, ´ es G −1(a, a) = ∅ tetsz˝ oleges a ∈ V cs´ ucsra, teh´ at G(e) = {a, b} helyett egyszer˝ uen ´ırhatunk {a, b}-t, amely a megfelel˝ o ´ elt jelenti. Ekkor a gr´ af is jel¨ olhet˝ o egyszer˝ ubben: G = (V, E).
5
Egyszer˝ u gr´ afban az x foksz´ ama vagy foka, amelynek jele szint´ en ϕ(x) vagy ϕG(x), az NG(x) halamz elemsz´ ama: ϕ(x) = |NG(x)|. P´ eld´ ak.
V (G1) = {1, 2, 3, 4, 5}, E(G1) = {e1, e2, e3, e4, e5, e6, e7}, G(e1) = G(e2) = G(e3) = {1, 4}, G(e4) = {2, 4}, G(e5) = {2, 1}, G(e6) = {2, 3}, G(e7) = {3, 4}. ϕ(1) = 4, ϕ(2) = 3, ϕ(3) = 2, ϕ(4) = 5, ϕ(5) = 0. 6
V (G2) = n {a, b, c, d, e}, o E(G2) = {a, c}, {a, d}, {b, c}, {b, e}, {b, d}{e, d}
7
Ha egy gr´ af minden foksz´ ama azonos, p´ eld´ aul r, akkor a gr´ af regul´ aris vagy r-regul´ aris. A k¨ ovetkez˝ o gr´ af egy (7,14) 4-regul´ aris gr´ af.
8
Ha egy egyszer˝ u gr´ afban b´ armely k´ et cs´ ucsot ´ el k¨ ot ¨ ossze, akkor a gr´ af teljes gr´ af. Az n-cs´ ucs´ u teljes gr´ af jele: Kn.
9
A G = (V , E) egyszer˝ u gr´ af a G = (V, E) egyszer˝ u gr´ af komplementuma vagy n komplementere, o ha V = V , E = {a, b} | {a, b} 6∈ E .
Ha a G egyszer˝ u gr´ af n-cs´ ucs´ u, akkor E(G) ∪ E(G) = E(Kn). 10
A G1 ´ es G2 gr´ afok izomorfak, ha l´ etezik egy bijekt´ıv f¨ ugv´ eny ψ : V (G1) → V (G2), ´gy, hogy ha {a, b} ∈ E(G1), akkor {ψ(a), ψ(b)} ∈ E(G2). u Az izomorfizmust tetsz˝ oleges gr´ afokra is ´ ertelmezhetj¨ uk. K´ et G1 ´ es G2 gr´ af izomorf, ha l´ etezik egy ψ : V (G1) → V (G2) bijekt´ıv f¨ uggv´ eny ´ ugy, hogy |G1−1(a, b)| = |G2−1(ψ(a), ψ(b))| minden a, b ∈ V (G1)-re.
11
P´ elda izomorf gr´ afokra.
A ψ f¨ uggv´ eny: x 1 2 3 ψ(x) x1 x5 x3
a x2
b x6
c x4
Izomorf gr´ afokban ϕ(x)=ϕ(ψ(x)) minden x ∈ V (G1)-re. 12
Ir´ any´ıtott gr´ afok Ir´ any´ıtott gr´ afnak nevezz¨ uk a ~ = (V, E, G) ~ rendezett h´ G armast, ahol V a cs´ ucsok (vagy sz¨ ogpontok vagy pontok) halmaza, E az ir´ any´ıtott ´ elek halmaza ´ es ~ :E →V ×V G ~ Ha e ∈ E ´ es (a, b) ∈ G(e), akkor a az e ´ el kezd˝ opontja, b pedig az e ´ el v´ egpontja. Ha egy ´ elnek a kezd˝ o- ´ es v´ egpontja egybeesik, akkor az az ´ el hurok´ el. 13
Ebben az ir´ any´ıtott gr´ afban az e1 ´ es e2 ´ elek p´ arhuzamosak, de e6 ´ es e8 nem. Ha egy ir´ any´ıtott gr´ afban nincsenek p´ arhuzamos ´ elek ´ es hurok´ elek, akkor az egyszer˝ u ir´ any´ıtott gr´ af. 14
~ ir´ Legyen G any´ıtott gr´ af. Ekkor ~ |G ~ −1(x, y) 6= ∅} N be (y) = {x ∈ V ( G) ~ G
az y-ba befut´ o´ elek kezd˝ opontjainak halmaza ~ |G ~ −1(y, z) 6= ∅} N ki (y) = {z ∈ V ( G) ~ G
az y-b´ ol kifut´ o´ elek v´ eppontjainak halmaza. Egy ir´ any´ıtott gr´ afban az x cs´ ucs be-foka az x-be befut´ o ´ elek sz´ ama (jel¨ ol´ ese ϕbe(x)), az x cs´ ucs ki-foka az x-b˝ ol kifut´ o ´ elek sz´ ama (jel¨ ol´ ese ϕki(x)). Ha egyszer˝ u ir´ any´ıtott gr´ afr´ ol van sz´ o, akkor: ϕbe(x) = |N be(x)| ϕki(x) = |N ki(x)|. 15
Gr´ afok ´ abr´ azol´ asa 1) – geometriai ´ abr´ azol´ as 2) – szomsz´ eds´ agi (adjacencia) m´ atrixszal G = (E, V, G), V = {x1, x2, . . . , xn} A = (aij )i,j=1,n (
aij =
a szomsz´ eds´ agi m´ atrix, ahol
|G −1(xi, xj )| ha i 6= j 2|G −1(xi, xj )| ha i = j 16
ϕ(xi) =
n X
aij , minden i = 1, 2, . . . , n
j=1
Az egyszer˝ u gr´ af szomsz´ eds´ agi m´ atrixa csak 0 ´ es 1 sz´ amokat tartalmaz. Ir´ any´ıtott gr´ af eset´ eben a defin´ıci´ o hasonl´ o. 17
3) – illeszked´ esi (incidencia) m´ atrixszal G = (E, V, G), V = {x1, x2, . . . , xn}, E = {e1, e2, . . . , em} B = (bij )i=1,n,j=1,m,
bij =
1
2
0
ha xi illeszjedik ej -hez ´ es ej nem hurok´ el ha xi illeszjedik ej -hez ´ es ej hurok´ el ha xi nem ej -hez.
18
19
4) – list´ aval a) Minden cs´ ucsnak felsoroljuk a szomsz´ edjait. x1 x2 x3 x4
x2 x1 x1 x1
x3 x3 x2 x3
x4 x3 x2 x3
x4
x4
Haszn´ alhatunk l´ ancolt list´ akat is. b) A list´ akat egym´ as ut´ an ´ırjuk egy-egy ∗-gal elv´ alasztva, a v´ eg´ ere k´ et csillagot t´ eve. x2
x3
∗
∗
x4
∗
x1
x3
x3
∗
x1
x2
x2
x4
x4
∗
x1
x3
20
x3
c) A ∗-okat elhagyjuk, ´ es m´ eg egy list´ at haszn´ alunk, amelyikben az egyes list´ ak kezd˝ oindexeit adjuk meg. x2
x3
x4
1
4
7
x1
x3
x3
x1
x2
x2
x4
x4
x1
x3
x3
12
A m´ asodik lista elemei az egyes list´ ak kezd˝ oelemeire mutatnak a k¨ ovetkez˝ ok´ eppen: x2 ↑
x3
x4
x1 ↑
x3
x3
x1 ↑
x2
x2
x4
x4
x1
x3
x3
↑
21
Legr¨ ov´ıdebb utak
A szomsz´ eds´ agi m´ atrix: A = aij
aij =
(0)
, ahol aij = dij , azaz: i,j=1,n
~ W(vi, vj ) ha {vi, vj } ∈ E(G) (vagy (vi, vj ) ∈ E(G))
0 ∞
ha i = j ~ ha {vi, vj } 6∈ E(G) (vagy (vi, vj ) 6∈ E(G))
A Floyd–Warshall-algoritmus t´ avols´ agi m´ atrix meghat´ aroz´ asa Floyd, Robert W. (1936–2001) Warshall, Stephen (1935–2006) 22
Kezdetben pij := i ha dij 6= ∞ ´ es i 6= j; m´ as esetekben pij := 0. FloydWarshall(D0) 1. D := D0 2. for k := 1 to n do 3. for i := 1 to n do 4. for j := 1 to n do 5. if dij > dik + dkj then 6. dij := dik + dkj 7. pij := pkj 8. return D, p
23
Egy ux–uy utat a k¨ ovetkez˝ o algoritmussal hat´ arozzuk meg: 1. 2. 3. 4. 5.
k := n : uk := y while uk 6= x do uk−1 := pxuk k := k − 1
A keresett ´ ut: uk , uk+1, . . . , un.
24
P´ elda.
25
A szomsz´ eds´ agi m´ atrixa ´ es a megfelel˝ o P m´ atrix kezdeti ´ ert´ eke:
0
1
3
∞
8
∞ 0 1 ∞ 5 D0 = ∞ ∞ 0 1 ∞ ∞ ∞ ∞ 0 2
∞ ∞
4
∞
0
0 1 1 0 1
0 0 2 0 2 P0 = 0 0 0 3 0 0 0 0 0 4
0 0 5 0 0
Az algoritmus eredm´ enye a D ´ es P m´ atrixok:
0
1
2 3 5
∞ 0 1 2 4 D= ∞ ∞ 0 1 3 ∞ ∞ 6 0 2
∞ ∞ 4 5 0
0 1 2 3 4
0 0 2 3 4 P = 0 0 0 3 4 0 0 5 0 4
0 0 5 3 0
26
R´ eszsorozatok n, d1 ≤ d2, s pozit´ıv eg´ eszek, x1, x2, . . . , xn sorozat (elemei Σ-b´ ol). (d1, d2)-r´ eszsorozat: xi1 , xi2 , . . . , xis , ahol i1 ≥ 1, d1 ≤ ij+1 − ij ≤ d2, for j = 1, 2, . . . , s − 1, is ≤ n, Hat´ arozzuk meg a (d1, d2)-r´ eszsorozatokat! 27
P´ eld´ aul: a, a, b, c, a, d, e (2, 4)-r´ eszsorozatok: (a), (a, b), (a, c), (a, b, a), (a, a), (a, c, d), (a, b, d), (a, a, e), (a, b, a, e), (a, c, e), (a, b, e), (a, d), (b), (b, a), (b, d), (b, a, e), (b, e), (c), (c, d), (c, e), (a, e), (d), (e). 28
x1, x2, . . . , xn elemei p´ aronk´ ent k¨ ul¨ onb¨ oznek: (d1, d2)-r´ eszsorozatok sz´ am´ anak kisz´ am´ıt´ asa: G = (V, n E), ahol o V = x1, x2, . . . , xn , n
o
E = (xi, xj ) | d1 ≤ j − i ≤ d2, i = 1, 2, . . . , n, j = 1, 2, . . . , n .
(2,4)-r´ eszsorozatok gr´ afja 29
A gr´ af szomsz´ eds´ agi m´ atrixa: A = aij (
aij =
1, if d1 ≤ j − i ≤ d2, 0, k¨ ul¨ onben,
i=1,n j=1,n
ha i = 1, 2, . . . , n, j = 1, 2, . . . , n.
A gr´ afban nincs ir´ any´ıtott k¨ or, ez´ ert Ak (ahol Ak = Ak−1A, A1 = A) i-edik sor´ aban ´ es j-edik oszlop´ aban l´ ev˝ o elem a khossz´ us´ ag´ u ir´ any´ıtott utak sz´ am´ at jelenti ai ´ es aj k¨ oz¨ ott. Ha A0 az egys´ egm´ atrix (1 a f˝ o´ atl´ on, 0 m´ ashol), legyen R = (rij ): R = A0 + A + A2 + · · · + Ak , ahol Ak+1 = O (nulla m´ atrix). A (d1, d2)-r´ eszsorozatok sz´ ama C(n; d1, d2) =
n X n X
rij .
i=1 j=1 30
Warshall(A, n) 1. W := A 2. for k := 1 to n 3. do for i := 1 to n 4. do for j := 1 to n 5. do wij := wij + wik wkj 6. return W R = A0 + W .
31
A=
0 0 0 0 0 0
0 0 0 0 0 0
1 0 0 0 0 0
1 1 0 0 0 0
1 1 1 0 0 0
0 1 1 1 0 0
.
Warshall-algoritmus alkalmaz´ asa ut´ an: W =
0 0 0 0 0 0
0 0 0 0 0 0
1 0 0 0 0 0
1 1 0 0 0 0
2 1 1 0 0 0
2 2 1 1 0 0
,
R=
1 0 0 0 0 0
0 1 0 0 0 0
1 0 1 0 0 0
1 1 0 1 0 0
2 1 1 0 1 0
2 2 1 1 0 1
,
C(6; 2, 4) = 19, az R elemeinek ¨ osszege. 32
Latin n´ egyzet seg´ıts´ eg´ evel: a, b, c, d, e, f, g n = 7, d1 = 2, d2 = 4 eset´ eben: A=
∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅
∅ {ac} {ad} {ae} ∅ ∅ ∅ ∅ {bd} {be} {bf } ∅ ∅ ∅ ∅ {ce} {cf } {cg} ∅ ∅ ∅ ∅ {df } {dg} , ∅ ∅ ∅ ∅ ∅ {eg} ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ 33
∅ ∅ ∅ ∅ ∅ ∅ ∅
∅ {ac} {ad} {ace, ae} {adf, acf } {aeg, aceg, adg, acg} ∅ ∅ {bd} {be} {bdf, bf } {beg, bdg} ∅ ∅ ∅ {ce} {cf } {ceg, cg} ∅ ∅ ∅ ∅ {df } {dg} ∅ ∅ ∅ ∅ ∅ {eg} ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅ ∅
.
Hozz´ asz´ am´ıtva az egyelem˝ u r´ eszsorozatokat is: C(7; 2, 4) = 30.
34
Gazdas´ agos fesz´ıt˝ of´ ak S´ ulyozott gr´ afban egy fesz´ıt˝ ofa ´ ert´ eke az ´ eleihez rendelt s´ ulyok osszege. Adott s´ ¨ ulyozott gr´ afban keress¨ uk a legkisebb ´ ert´ ek˝ u fesz´ıt˝ of´ at, amelyet minim´ alis fesz´ıt˝ of´ anak nevez¨ unk. Kruskal algoritmusa A gr´ af ´ eleit s´ ulyuk szerint n¨ ovekv˝ o sorrendbe rendezz¨ uk. Az els˝ o ´ el a sorb´ ol beker¨ ul a leend˝ o gazdas´ agos fav´ azba (az al´ abbi algoritmusban a leend˝ o fav´ azba beker¨ ul˝ o´ eleket megcsillagozzuk). Kezdetben a gr´ af minden cs´ ucsa egy-egy halmazt k´ epez. Egy ´ el akkor ker¨ ul be a fav´ azba, ha v´ egpontjai k¨ ul¨ onb¨ oz˝ o halmazb´ ol val´ ok, ´ es ekkor a k´ et megfelel˝ o halmazt egyes´ıtj¨ uk. Az algoritmus akkor ´ er v´ eget, amikor a gr´ af minden cs´ ucsa egy halmazban van. 35
Az els˝ o oszlopban az ´ elek vannak, a m´ asodikban a megfelel˝ o s´ uly ´ ert´ eke, a harmadikban csillag, ha az ´ el beker¨ ult a fav´ azba, a negyedik oszlopban pedig a cs´ ucshalmazok. 36
{5,7} {7,8} {3,8} {1,3} {3,4} {4,8} {2,3} {1,5} {2,5} {4,5} {1,6} {3,5} {1,2} {5,6} {5,8}
1 2 3 4 4 4 5 6 6 6 8 9 10 12 13
* * * * *
{1}, {2}, {3}, {4}, {5}, {6}, {7}, {8} {5,7}, {1}, {2}, {3}, {4}, {6}, [8} {5,7,8}, {1}, {2}, {3}, {4}, {6} {3,5,7,8}, {1}, {2}, {4}, {6} {1,3,5,7,8}, {2}, {4}, {6} {1,3,4,5,7,8}, {2}, {6}
*
{1,2,3,4,5,7,8}, {6}
*
{1,2,3,4,5,6,7,8}
37
A csillaggal megjel¨ olt ´ elek a gazdas´ agos fav´ az ´ elei. Maga a fav´ az a k¨ ovetkez˝ o:
38
Az algoritmus le´ır´ as´ ahoz tekints¨ uk az ´ elek E = {e1, e2, . . . , em} halmaz´ at ´ ugy, hogy W(ei) ≤ W(ei+1), minden i = 1, 2, . . . , m − 1 ´ ert´ ekre (azaz, az ´ elek s´ ulyuk szerint n¨ ovekv˝ o sorrendben vannak indexelve). Halmazok helyett egy h = (h1, h2, . . . , hn) vektort haszn´ alunk (n a cs´ ucsok sz´ ama), amelynek elemei kezdetben egyenl˝ oek az index¨ ukkel, ami arra utal, hogy k¨ ul¨ onb¨ oz˝ o halmazok elemei. Amikor k´ et halmazt egyes´ıt¨ unk, a megfelel˝ o hi ´ ert´ ekeket egyenl˝ ov´ e tessz¨ uk (egyik halmaz elemeinek hi ´ ert´ ekeit a m´ asik halmaz hi ´ ert´ ekeire ´ all´ıtjuk.).
39
Kruskal(E) 1. for j=1,2, . . . , n do 2. hj := j 3. i := 1 4. while h elemei k¨ ul¨ onb¨ oz˝ oek do 5. if (ei v´ egpontjai vk , vl ) ´ es (hk 6= hl ) then 6. ki´ır ei 7. for j:=1, 2,. . . , n do 8. if hj = hl then 9. hj := hk 10. i:=i+1
40
´ rv´ız ut´ A an Egy megye helys´ egei (v´ arosok, falvak) k¨ oz¨ otti utakat n´ ehol elmosta az ´ arv´ız. A helys´ egek xi, i = 1, 2, . . . , n, ´ es a k¨ ozt¨ uk ´ epen l´ ev˝ o utakat az A = (aij ) m´ atrix jelzi: aij = 1, ha xi ´ es xj k¨ oz¨ ott van ´ epen maradt u ´t, ´ es aij = 0, ha az ´ ut j´ arhatatlan. K´ erd´ es: el lehet-e jutni a megye b´ armelyik helys´ eg´ eb˝ ol b´ armelyik m´ asik helys´ eg´ ebe? Megold´ as: Gr´ affal, amelynek szomsz´ eds´ agi m´ atrixa A. V´ alasztunk egy tetsz˝ oleges helys´ eget: pl. x1. U = {x1}. U = U ∪N (U ) ameddig U nem v´ altozik. (N (U ) az U szomsz´ edai.) Ha U tartalmazza az ¨ osszes helys´ eget, akkor a v´ alasz igen, k¨ ul¨ onben nem. 41
Euler-vonal keres´ ese Fleury algoritmusa – Ellen˝ orizz¨ uk, hogy a gr´ af Euler-gr´ af-e (minden foksz´ am p´ aros) vagy pontosan k´ et p´ aratlan fok´ u cs´ ucsa van. – Elindulunk tetsz˝ oleges cs´ ucsb´ ol (vagy egy p´ aratlan foksz´ am´ ub´ ol). – Mindig olyan ´ uj ´ elt v´ alasztunk, amely nem h´ıd (kit¨ or¨ olj¨ uk). (Hidat csak akkor, ha m´ as nincs.)
42
Hamilton-´ ut keres´ ese visszal´ ep´ eses m´ odszerrel El´ egs´ eges felt´ etelek: R´ edei-t´ etel Dirac-t´ etel Ore-t´ etel
43
