1 Utaz´ ou ¨ gyn¨ ok feladat Az utaz´ ou ¨ gyn¨ ok probl´ em´ aja Adott n sz´am´ u v´aros ´es a v´arosokat ¨osszek¨ ot˝ o utak, amelyeknek ismert a hossza. Adott tov´abb´a egy u ¨gyn¨ok, akinek adott v´arosb´ ol kiindulva, minden v´arost v´egig kell l´atogatnia u ´gy, hogy minden v´arost pontosan egyszer ´erint, ´es az u ´t befejezt´evel visszat´er a kiindul´asi v´arosba. Hat´arozzuk meg az u ¨gyn¨ok legr¨ovidebb u ´tj´at. Vezess¨ uk be a k¨ovetkez˝o jel¨ol´eseket. Jel¨olje 1, 2, . . . , n a v´arosokat ´es cij az i-edik ´es j-edik v´arosokat ¨osszek¨ ot˝ o u ´t hossz´at. Ha a k´et v´arost nem k¨oti ¨ossze u ´t, akkor legyen cij = W , ahol W m´ar az el˝oz˝oekben is alkalmazott megfelel˝oen nagy sz´am. Legyen ½
1, ha az u ¨gyn¨ok az i-edik v´arosb´ ol a j-edik v´arosba megy, 0 k¨ ul¨onben. ¯ az {1, . . . , n} \ Q halV´eg¨ ul jel¨olje tetsz˝oleges Q ⊆ {1, . . . , n} halmazra Q mazt. Akkor a fenti feladat az al´abbi, utaz´ ou ¨gyn¨ ok probl´ema n´even ismert optimumsz´am´ıt´asi modellel ´ırhat´ o le. xij =
n X
xit = 1 (i = 1, . . . , n)
t=1
(1)
n X
xtj = 1 (j = 1, . . . , n)
t=1
XX
xij ≥ 1 (∅ 6= Q ⊂ {1, . . . , n})
¯ i∈Q j∈Q
xij ∈ {0, 1}, (i = 1, . . . , n; j = 1, . . . , n) —————————————————— n X n X
cij xij = z → min
i=1 j=1
Az els˝o felt´etelcsoport garant´ alja, hogy az u ¨gyn¨ ok minden v´arosb´ ol t´avozik. A m´asodik felt´etelcsoport biztos´ıtja, hogy az u ¨gyn¨ ok eljut minden v´arosba. Sajn´alatos m´odon a k´et felt´etelcsoport megengedi diszjunkt r´eszk¨orutak kialakul´as´at. Ezt k¨ usz¨ ob¨ oli ki a harmadik felt´etelcsoport, amelyben el˝o´ırjuk, hogy a v´arosok tetsz˝oleges ∅ 6= Q ⊂ {1, . . . , n} r´eszhalmaz´ ara az u ¨gyn¨ok valamely Q-beli v´arosb´ ol egy nem Q-beli v´arosba l´atogat. Ez
2 val´oban kiz´arja a r´eszk¨ orutat, ugyanis a r´eszk¨ or´ utban szerepl˝o v´arosok halmaz´at tekintve Q-nak, a harmadik felt´etelcsoport megfelel˝o felt´etele nem teljes¨ ul. Megjegyezz¨ uk, hogy az utaz´o u ¨gyn¨ ok probl´em´ aja a kor´ abbi fejezetek terminol´ogi´aj´aval ¨osszhangban u ´gy interpret´ alhat´ o, hogy egy minim´alis hossz´ us´ag´ u, minden cs´ ucspontot tartalmaz´o ir´any´ıtott k¨orutat kell meghat´arozni egy adott h´al´ozatban. Az (1) modellel kapcsolatban vegy¨ uk ´eszre, hogy a harmadik felt´etelcsoportban a felt´etelek sz´ama 2n − 2, ami m´ar viszonylag kicsi n mellett is nagyon sok egyenl˝otlens´eget eredm´enyez. A felt´etelek sz´am´ anak cs¨okkent´es´ere a probl´em´anak t¨obb ekvivalens formaliz´al´ asa is kidolgoz´asra ker¨ ult. A k¨ovetkez˝o (2) v´altozatot A. Tucker dolgozta ki 1960-ban. n X
xit = 1 (i = 1, . . . , n)
t=1
(2)
n X
xtj = 1 (j = 1, . . . , n)
t=1
ui − uj + (n − 1)xij ≤ n − 2 (2 ≤ i 6= j ≤ n) xii = 0, xij ∈ {0, 1}, (i = 1, . . . , n; j = 1, . . . , n) ui ≥ 0 & eg´esz (i = 2, . . . , n) ———————————————————— n X n X
cij xij = z → min
i=1 j=1
Az ekvivalencia igazol´as´ ahoz egyr´eszt azt kell megmutatnunk, hogy diszjunkt r´eszk¨orutak egyes´ıt´ese nem el´eg´ıti ki a (2) feladat felt´etelrendszer´et. ¯ u ¯ ) lehetEzt indirekt bizony´ıtjuk. Tegy¨ uk fel, hogy a feladat valamely (X, s´eges megold´as´ara x ¯i1 i2 = x ¯i2 i3 = . . . x ¯ik i1 = 1 teljes¨ ul valamely 1 < k < n eg´eszre. Az ´altal´ anoss´ ag megszor´ıt´ asa n´elk¨ ul ¯ u ¯ ) lehets´eges megold´as, ez´ert feltehetj¨ uk, hogy 1 ∈ / {i1 , . . . , ik }. Mivel (X,
3
u ¯ i1 − u ¯i2 + (n − 1)¯ xi1 i2 ≤ n − 2 u ¯ i2 − u ¯i3 + (n − 1)¯ xi2 i3 ≤ n − 2 .. . xik i1 ≤ n − 2 u ¯ik − u ¯i1 + (n − 1)¯ ¨ teljes¨ ul. Osszeadva rendre az egyenl˝ otlens´egek bal- ´es jobboldalait, az al´abbi egyenl˝otlens´egnek kell fenn´allnia k(n − 1) ≤ k(n − 2) , ami 1 < k < n eset´en ellentmond´ as. M´asr´eszt igazolnunk kell, hogy b´armely k¨or´ uthoz l´etezik a (2) feladatnak ¯ u ¯ ´ ¯ ) lehets´eges megold´asa, hogy az X egy olyan (X, altal meghat´arozott ´elek pontosan a tekintett k¨orutat szolg´altatj´ ak. Ehhez tekints¨ unk egy tetsz˝ole¯ ges, az (1, i2 ), (i2 , i3 ), . . . , (in , 1) ´eleket tartalmaz´o k¨orutat. Defini´aljuk X-t ¯ -t a k¨ovetkez˝ok szerint: ´es u x ¯1i2 = x ¯i2 i3 = . . . x ¯in 1 = 1 , x ¯ij = 0 a t¨obbi indexp´arra, u ¯it = t (t = 2, . . . , n) . ¯ u ¯ ) kiel´eg´ıti (2) felt´etelrendszer´et. A felt´etelek telMegmutatjuk, hogy (X, jes¨ ul´ese a harmadik felt´etelcsoportt´ol eltekintve nyilv´ anval´ o. Legyen ezek ¯ vektor defin´ıci´ ut´an 2 ≤ i 6= j ≤ n tetsz˝oleges indexp´ar. Az u oj´ ab´ ol k¨ovetkezik, hogy u ¯i − u ¯j ≤ n − 2. M´asr´eszt x ¯ij = 1 akkor ´es csak akkor teljes¨ ul, ha i = ir ´es j = ir+1 valamely 2 ≤ r ≤ n indexre. De ebben az esetben u ¯i − u ¯j + (n − 1)¯ xij = r − (r + 1) + (n − 1) ≤ n − 2 , ¯ u ¯ ) lehetazaz a harmadik felt´etelcsoport felt´etelei rendre teljes¨ ulnek, ´ıgy (X, s´eges megold´asa (2)-nek. Vizsg´aljuk ezek ut´an az (1) feladatot. Az ´altal´ anoss´ ag megszor´ıt´ asa n´elk¨ ul feltehetj¨ uk, hogy az u ¨gyn¨ ok az 1-gyel jelzett v´arosb´ ol indul. Ekkor
4 n − 1 sz´am´ u v´arosba mehet, majd n − 2-be, ´es ´ıgy tov´ abb. Ebb˝ol az k¨ovetkezik, hogy a lehets´eges megold´asok sz´ama (n − 1)!. Viszont ´ıgy r¨ogt¨ on ad´odik, hogy az (1) feladatnak mindig l´etezik optim´alis megold´asa. Ezzel kapcsolatban c´elszer˝ u megjegyezni, hogy amennyiben az i-edik v´arosb´ ol nem vezetett u ´t a j-edik v´arosba, akkor ezt a modellben egy W hossz´ us´ ag´ u fikt´ıv u ´ttal helyettes´ıtett¨ uk. ´Igy, ha optimum´ert´ekk´ent W ad´odik, akkor ez azt jelenti, hogy a v´arosok k¨oz¨ otti u ´th´ al´ ozat olyan, amely nem teszi lehet˝ov´e a k¨orbej´ar´ast, azaz a gyakorlati probl´em´ anak nincs lehets´eges megold´asa. Vegy¨ uk ´eszre, hogy az (1) feladat felt´etelrendszere csak n-t˝ ol f¨ ugg. ´Igy a k¨olts´egm´atrix egy´ertelm˝ uen meghat´arozza a feladatot. Ennek alapj´an az (1) feladatra a T SP (C) jel¨ol´essel fogunk hivatkozni. Itt az angol Traveling Salesman Problem n´ev r¨ovid´ıt´es´et haszn´aljuk, mely a t´emak¨ or irodalm´aban igen sz´eles k¨orben elterjedt. Cn×n
¯ m´ A tov´abbiakban az egyszer˝ ubb t´argyal´ as ´erdek´eben az X atrixot k¨ or´ utnak nevezz¨ uk, ha minden x ¯ij = 1-re v´eve az (i, j) ´elet, az ´ıgy k´epezett ´elek az n-sz¨ogpont´ u teljes gr´afban ir´any´ıtott k¨ort alkotnak. Most ism´etelten haszn´aljuk a hozz´arendel´esi feladatok bemutat´ as´ an´ al defini´alt m´atrixok ekvivalenci´ aj´ at. A tekintett rel´aci´o ´es a TSP kapcsolat´at adja meg a k¨ovetkez˝ o ´all´ıt´ as. seg´ edt´ etel. Ha Cn×n ∼ Dn×n , akkor a T SP (C) ´es T SP (D) feladatok optim´ alis megold´ asai megegyeznek. Bizony´ıt´ as. Mivel mindk´et feladatnak l´etezik optim´alis megold´asa, ez´ert az ´all´ıt´as korrekt. M´asr´eszt a tekintett k´et feladat felt´etelrendszere azonos, ez´ert a lehets´eges megold´asok halmaza k¨oz¨ os, amelyet jel¨olj¨ on L. Tov´ abb´ a jel¨olje a T SP (C) ´es T SP (D) feladatok c´elf¨ uggv´eny´et rendre zC ´es zD . Meg¯ = zD (X) ¯ + γ teljes¨ mutatjuk, hogy van olyan γ konstans, amelyre zC (X) ul ¯ lehets´eges megold´asra. Val´ tetsz˝oleges X oban, mivel C ∼ D, ez´ert vannak olyan α1 , . . . , αn ; β1 , . . . , βn konstansok, hogy cij = dij + αi + βj teljes¨ ul b´armely 1 ≤ i ≤ n, 1 ≤ j ≤ n indexp´ arra. De akkor ¯ = zC (X)
n X n X
cij x ¯ij =
i=1 j=1 n X n X i=1 j=1
dij x ¯ij +
n X n X
(dij + αi + βj )¯ xij =
i=1 j=1 n X i=1
αi
n X j=1
x ¯ij +
n X j=1
βj
n X
x ¯ij .
i=1
P ¯ lehets´eges megold´as, ez´ert Pn x ¯ij = 1. De akkor es ni=1 x Mivel X j=1 ¯ij = 1 ´
5
¯ = zD (X) ¯ + zC (X)
n X i=1
αi +
n X
βj .
j=1
P P ¯ = zD (X) ¯ +γ Most legyen γ = ni=1 αi + nj=1 βj . Akkor a zC (X) ¯ egyenlethez jutunk, amely teljes¨ ul b´armely X lehets´eges megold´asra. Ez pontosan azt jelenti, hogy a lehets´eges megold´asok halmaz´an a k´et c´elf¨ uggv´eny csak egy addit´ıv konstansban t´er el egym´ast´ ol, amib˝ol nyilv´ anval´ oan k¨ovetkezik az ´all´ıt´as.
k¨ ovetkezm´ eny. Az optim´ alis megold´ as meghat´ aroz´ as´ at illet˝ oen elegend˝ o olyan T SP (C) feladatok vizsg´ alat´ ara szor´ıtkoznunk, amelyekre C ≥ 0 teljes¨ ul. A fenti k¨ovetkezm´eny alapj´an a tov´ abbiakban minden hivatkoz´ as n´elk¨ ul felt´etelezz¨ uk, hogy a vizsg´alt feladatok c´elf¨ uggv´enyegy¨ utthat´ oi rendre nemnegat´ıvak. Az (1) feladattal kapcsolatosan azt is ´eszrevehetj¨ uk, hogy amennyiben a harmadik felt´etelcsoportt´ol eltekint¨ unk, u ´gy a hozz´arendel´esi feladathoz ju¯ lehets´eges megold´asa tunk. Ebb˝ol viszont k¨ovetkezik, hogy (1) tetsz˝oleges X egyben lehets´eges megold´asa a C k¨ olts´egm´ atrix´ u H(C) hozz´arendel´esi feladatnak is. Jel¨olje (1) lehets´eges megold´asainak halmaz´at L, H(C) lehets´eges megold´asainak halmaz´at S. Akkor L ⊆ S, ´es ´ıgy min{z(X) : X ∈ S} ≤ min{z(X) : X ∈ L} . A kapott egyenl˝otlens´egb˝ol nyilv´ anval´ oan ad´odnak a k¨ovetkez˝ ok: ¯ optim´ ¯ k¨ ¯ egyben opalis megold´ asa H(C)-nek ´es X or´ ut, akkor X (i) ha X tim´ alis megold´ asa T SP (C)-nek is, ¯ optim´ ¯ als´ (ii) ha X alis megold´ asa H(C)-nek, akkor z(X) o korl´ atja a T SP (C) feladat optimum´ert´ek´enek. A tov´abbiakban olyan speci´alis hozz´arendel´esi feladatok haszn´alunk, melyekre kik¨otj¨ uk, hogy bizonyos v´altoz´ oknak 0 ´ert´eket, a v´altoz´ ok egy m´asik csoportj´anak 1 ´ert´eket kell felvennie. Ism´et I ´es J jel¨ oli azon v´altoz´ ok indexeinek a halmaz´at, amelyekr˝ol kik¨otj¨ uk, hogy ´ert´ek¨ uk 1 illetve 0. Ezen speci´alis hozz´arendel´esi feladatok jel¨ol´es´ere a (H(C), I, J) jel¨ol´est fogjuk haszn´alni.
6 A k¨ovetkez˝okben egy B&B elj´ar´ ast ´ep´ıt¨ unk fel az utaz´o u ¨gyn¨ ok probl´ema megold´as´ara, amelyben a korl´ atoz´ o f¨ uggv´eny defini´al´ as´ ara a fentiekben v´azolt, a H(C) ´es T SP (C) feladatok k¨ozti kapcsolatot fogjuk kihaszn´alni. Az elj´ar´as fel´ep´ıt´es´et ay ´altal´ anos elj´ar´ asnak megfelel˝oen v´egezz¨ uk. Felt´etelezz¨ uk, hogy a C m´atrixban cii = W , (i = 1, . . . , n) teljes¨ ul. I. Az Ω halmaz megad´ asa Legyen Ω a {0, 1} feletti n × n m´atrixok halmaza. Nyilv´anval´ o, hogy 2 n L ⊆ Ω, tov´abb´a |Ω| = 2 , ´ıgy Ω rendelkezik a k´ıv´ ant tulajdons´agokkal. II. A ϕ sz´ etv´ alaszt´ asi ´ es a g korl´ atoz´ o f¨ uggv´ enyek megad´ asa Els˝ok´ent a f¨ uggv´enyeket az Ω halmazon defini´aljuk. Legyen g(Ω) a H(C) hozz´arendel´esi feladat optimum´ert´eke. A ϕ(Ω) defini´al´ as´ ahoz pedig k¨ ul¨onb¨oztess¨ uk meg az al´abbi k´et esetet. (a) Ha H(C) optim´alis megold´asa k¨or´ ut, akkor ez optim´alis megold´asa a T SP (C) feladatnak is. ´Igy z¯ felveszi az optimum´ert´eket ´es Ω nem lesz ´el˝o lev´el, azaz Ω ∈ / F0 . De akkor nem kell a ϕ f¨ uggv´enyt az Ω halmazon defini´alni. ¯ optim´ ¯ disz(b) Ha a H(C) feladat X alis megold´asa nem k¨or´ ut, akkor X junkt r´eszk¨or¨okb˝ol ´all. Legyen ezek k¨oz¨ ul az (i1 , i2 ), . . . , (ik−1 , ik ), (ik , i1 ) ´eleket tartalmaz´o r´eszk¨ or´ ut minim´alis elemsz´am´ u, ´es tekints¨ uk a k¨ovetkez˝ o halmazokat: Ω(0) = {X : X ∈ Ω & xi1 i2 = . . . = xik i1 = 1}, Ω(1) = {X : X ∈ Ω & xi1 i2 = 0}, Ω(2) = {X : X ∈ Ω & xi2 i3 = 0 & xi1 i2 = 1}, .. . Ω(k) = {X : X ∈ Ω & xik i1 = 0 & xi1 i2 = . . . = xik−1 ik = 1}. Egyszer˝ uen bel´athat´ ok a k¨ovetkez˝ ok: (1) az Ω(0) , Ω(1) , . . . , Ω(k) halmazok a felbontand´ o halmaznak (jelenleg Ω) egy val´odi oszt´alyoz´ as´ at alkotj´ ak, (2) b´armely 1 ≤ i ≤ k indexre az Ω(i) defin´ıci´ oj´ aban 1 ´ert´ekkel szerepl˝o v´altoz´oknak megfelel˝o ´elekb˝ ol ´all´ o gr´af nem tartalmaz r´eszk¨ orutat, (3) Ω(0) ∩ L = ∅. Defini´aljuk ϕ(Ω)-t a k¨ovetkez˝ ok szerint. Legyen
7
ϕ(Ω) = {Ω(0) , Ω(1) , . . . , Ω(k) } . A ϕ f¨ uggv´eny defin´ıci´oj´at u ´gy fogjuk kiterjeszteni, hogy az (1),(2),(3) tulajdons´agok ´erv´enyben maradjanak. A tov´ abbiakban az oszt´alyoz´ asok oszt´alyainak le´ır´as´ara azt a technik´ at fogjuk haszn´alni, hogy az I, J halmazokban megadjuk azon v´altoz´ok indexeit, amelyek ´ert´eke r¨ogz´ıtett. P´eld´ aul Ω(2) = ΩI,J , ahol I = {(i1 , i2 )}, J = {(i2 , i3 )}. A r¨ogz´ıtett ´ert´ek˝ u v´altoz´ okat k¨ ot¨ ott v´ altoz´ oknak, a t¨obbi v´altoz´ ot pedig szabad v´ altoz´ oknak fogjuk nevezni ΩI,J -re vonatkoz´oan. V´eg¨ ul speci´alisan azokat az oszt´alyokat, amelyekr˝ ol tudjuk, hogy nem tartalmaznak k¨orutat (Ω felbont´ as´ an´ al Ω(0) ), l´assuk el ∗-gal. Ezek ut´an kiterjesztj¨ uk a ϕ ´es g f¨ uggv´enyek ´ertelmez´es´et. A g korl´atoz´o f¨ uggv´eny defini´al´ as´ ahoz tekints¨ uk a B&B-f´aban valamely ´el˝o lev´el lesz´armazottj´at. Ha a tekintett oszt´aly ∗-gal lett ell´atva, akkor g rendelje ehhez a r´eszhalmazhoz a W korl´ atot. Ellenkez˝ o esetben jel¨olje a tekintett oszt´alyt ΩI,J . Ekkor a (H(C), I, J) hozz´arendel´esi feladat b´armely lehets´eges megold´asa eleme ΩI,J -nek, tov´ abb´ a b´armely olyan k¨or´ ut, amelyben az I-ben szerepl˝o indexekre a v´altoz´ ok ´ert´eke 1, valamint a J-ben szerepl˝o indexekre a v´altoz´ok ´ert´eke 0, lehets´eges megold´asa (H(C), I, J)-nek. Viszont ´ıgy a (H(C), I, J) feladat z˜ optimum´ert´ek´ere z˜ ≤ min{z(X) : X ∈ L ∩ ΩI,J } teljes¨ ul, amennyiben L ∩ ΩI,J 6= ∅. Ennek alapj´an defini´aljuk g(ΩI,J )-t a k¨ovetkez˝ok szerint: (H(C), I, J) optimuma,
g(ΩI,J ) =
¯ z(X), W
ha |ΩI,J | > 1, ¯ ´es X ¯ k¨or´ ha ΩI,J = {X} ut, k¨ ul¨ onben.
A ϕ f¨ uggv´eny defin´ıci´oj´anak kiterjeszt´es´ehez tekints¨ uk a B&B-fa egy ´el˝ o 2 ΩI,J level´et. Mivel ΩI,J ´el˝o lev´el, ez´ert |I| + |J| < n − n, (H(C), I, J) optimuma kisebb, mint W , tov´abb´ a (H(C), I, J) optim´alis megold´asa nem k¨or´ ut. (Ellenkez˝o esetben a lev´el lez´ar´ asra ker¨ ulne.) De akkor (H(C), I, J) optim´alis megold´asa diszjunkt r´eszk¨ orutak uni´oja. V´alasszunk ezen r´eszk¨orutak k¨oz¨ ul egy minim´alis elemsz´am´ ut. Jel¨olje K a v´alasztott r´eszk¨ or´ uthoz tartoz´o v´altoz´ok indexeinek a halmaz´at. Akkor K nem¨ ures halmaz, K ∩J = ∅, ´es a (2) tulajdons´ag miatt K 6⊆ I. Legyen K \ I = {(i1 , j1 ), . . . , (ir , jr )}. Mivel (K\I)∩J = ∅ ´es (K\I)∩I = ∅, ez´ert b´armely xis js (1 ≤ s ≤ r) v´altoz´ o
8 szabad v´altoz´o lesz ΩI,J -re vonatkoz´ oan. K´epezz¨ uk ezek ut´an a k¨ovetkez˝ o halmazokat: ΩI0 ,J0 = {X : X ∈ ΩI,J & xi1 j1 = . . . = xir jr = 1}, ΩI1 ,J1 = {X : X ∈ ΩI,J & xi1 j1 = 0}, ΩI2 ,J2 = {X : X ∈ ΩI,J & xi2 j2 = 0 & xi1 j1 = 1}, .. . ΩIr ,Jr = {X : X ∈ ΩI,J & xir jr = 0 & xi1 j1 = . . . = xir−1 jr−1 = 1}. Mivel xit jt (1 ≤ t ≤ r) szabad v´altoz´ ok ΩI,J -re vonatkoz´ oan, ez´ert a fenti halmazok az ΩI,J halmaznak egy val´ odi oszt´alyoz´ as´ at alkotj´ ak. Nyilv´anval´o, hogy ΩI0 ,J0 ∩ L = ∅, ugyanis ΩI0 ,J0 minden eleme tartalmazza a kiv´alasztott minim´alis elemsz´am´ u r´eszk¨ orutat, mint r´eszgr´ afot. Most legyen 0 ≤ t ≤ r tetsz˝oleges eg´esz. Jel¨olje Gt = (N, Et ) azt a gr´afot, amelyre (i, j) ∈ Et akkor ´es csak akkor teljes¨ ul, ha (i, j) ∈ It , ahol N = {1, . . . , n}. Ekkor G0 tartalmazza a kiv´alasztott minim´alis elemsz´am´ u r´eszk¨ orutat ´es m´as r´eszk¨orutat nem tartalmaz. M´asr´eszt b´armely 1 ≤ t ≤ r indexre Gt el˝o´all´ıthat´o G0 -b´ol u ´gy, hogy G0 egyetlen r´eszk¨ or´ utj´ ab´ ol elhagyunk egy vagy t¨obb ´elet. De akkor Gt nem tartalmaz r´eszk¨ orutat. Ez pontosan azt jelenti, hogy az ΩIt ,Jt -ben 1 ´ert´ekkel r¨ogz´ıtett v´altoz´ oknak megfelel˝o ´elek nem alkotnak r´eszk¨orutat b´armely 1 ≤ t ≤ r indexre. K¨ovetkez´esk´epp, a defini´alt halmazok rendelkeznek az (1),(2),(3) tulajdons´agokkal. Legyen ezek ut´an ϕ(ΩI,J ) = {ΩI0 ,J0 , ΩI1 ,J1 , . . . , ΩIr ,Jr }. A ϕ ´es g f¨ uggv´enyek defin´ıci´ oj´ ab´ ol k¨ovetkezik, hogy rendelkeznek a k´ıv´ ant tulajdons´agokkal. III. Fa´ ep´ıt´ esi strat´ egia Azt a kor´abban m´ar megismert strat´egi´ at fogjuk alkalmazni, miszerint egy minim´alis korl´attal rendelkez˝ o levelet v´alasztunk a fa´ep´ıt´es sor´an.
