Matematika | Diszkrét Matematika » Mátrix reprezentációk

Mátrix reprezentációk Az illeszkedési mátrix Definíció: A G ( E , ϕ ,V ) irányítás nélküli gráf illeszkedési ill. incidencia mátrixa An,m ai , j , ahol ai,j=1, ha a vi csúcs illeszkedik az ej. élre és 0 egyébként, ha az ej él hurokél a j. oszlop minden eleme 0 di  e1 e2  v1  0 1 v2  0 1  v3  0 0 A = v4  0 0  v5  0 0 v6  0 0  v7  0 0  v8  0 0 e3 e4 0 0 1 0 e5 e6 0 0 e7 0 e8 0 e9 0 e10 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 e11   0 0  0 0  0 1  0  1 A fenti definícióban a csúcsok számát n az élek számát m jelölte, azaz |V|=n és |E|=m. Hurokélekrôl nem ad használható információt a gráf illeszkedési e1 e9 mátrixa. Irányítatlan v3 gráfok illeszkedési v1 mátrixainak a sorai ill. az e3 e10 oszlopainak a v8 e4 permutálásával e2 e11 egymásba átvihetôk. Ha a e6 e8

G1 és a G2 gráfok v7 v6 izomorfak, akkor az e7 v2 v5 v4 e5 illeszkedési mátrixaik A1 ill. A2 a soraik ill. oszlopaik alkalmas permutálásával egymásba átvihetôk. Ha a mátrixok egyformák, akkor nem tudjuk, hogy a megfelelô gráfok izomorfak e, mivel az illeszkedési mátrix nem ad felvilágosítást arról, hogy egy hurokél melyik csúcspontra illeszkedik és melyikre nem. A továbbiakban csak olyan irányítatlan gráfok illeszkedési mátrixairól beszélünk, melyeknek nincs hurokélük. A definíció alatti mátrix a szövegbe rajzolt gráf illeszkedési mátrixa. A mátrix 2 blokkból áll, mivel a gráfunk két komponense van, és elôször az elsô komponensbe tartozó csúcsokat ill. éleket adtuk meg Általában is igaz, ha valamely G gráf k komponensbôl áll alkalmas módon indexelve a G csúcsait és oszlopait az 44 illeszkedési mátrixa k blokkból fog állni, azaz a mátrixa az  A1 0 . 0    0 A2 . 0   , ahol az Ai a G mátrix i.

alábbi alakú lesz A =  . .    0 . An   0 komponensének az illeszkedési mátrixa. Tétel: Ha a G gráf rendje n és k komponensbôl áll és illeszkedési mátrixa A, akkor rg(A)=n-k, ( a mátrixot a Z2 test fölöttinek tekintjük ( azaz mod(2) számolunk)). Bizonyítás: A bizonyítást a komponensek száma szerinti teljes indukcióval végezzük. Lényegében a tétel elôtt említett blokk felbontás miatt elegendô az állítást k=1 esetén belátni, mivel a "fôátlón" kívül mindenütt 0 áll és emiatt a blokkokból álló hipermátrix rangja megegyezik a fôátlóban álló blokk rangjainak összegével. Legyen G1 elsô komponense G-nek és legyen csúcsainak száma n1, s illeszkedési mátrixa A1. Az A1 mátrix rangja legfeljebb n1-1 lehet. Valóban adjuk az A1 mátrix minden sorát az A1 mátrix utolsó sorához. Ekkor az utolsó sor minden eleme 0 lesz, mivel minden oszlopban 2 darab egyes van ( egy él pontosan két csúcsra

illeszkedik. Ha n1-nél kevesebb s1 sor összege is 0-t adna, például az i1,i2,.,is1 , akkor v1,v2,.,vs1 csúcsok egyikébôl sem vezetne él valamely másik a v1,v2,.,vs1 pontoktól különbözô csúcspontba, ellentmondva annak, hogy G1 összefüggô volt. Az elôbb mondottak megismételhetôk G bármely komponensére vonatkozólag, s figyelembe véve, hogy a speciális alakú A hipermátrixunk Ai blokkjainak rangjainak az összege magának a hipermátrixnak a rangjával egyezik meg, az állítást bebizonyítottuk. Ha a G gráf A illeszkedési mátrixából komponensenként egy-egy sort elhagyunk, akkor G ún. redukált incidencia mátrixát kapjuk. Nem nehéz belátni, hogy ha valamely kvadratikus (n-k)⋅(n-k)-as részmátrix determinánsa nem 0 ,akkor a részmátrix oszlopaihoz tartozó élek G minden komponensének kijelölik egy-egy feszítô fáját. Tétel: Ha a G gráf e1,e2,.,ek1 élei kört alkotnak, akkor az incidencia mátrix (a redukált incidencia mátrix)

e1,e2,.,ek1 által kijelölt oszlopai lineárisan függôk Bizonyítás: A kijelölt oszlopoknak megfelelô élek közül kettô vagy 0 illeszkedik bármely csúcspontra, ezért a kijelölt oszlopok bármely sorában 2 vagy 0 darab 1-es áll , s ezek összege mod(2) valóban 0. Azaz a szóban forgó vektorok összege 0, s ez pontosan azt jelenti, hogy lineárisan függôk. Definició: A irányított gráf illeszkedési G ( E , ϕ ,V ) mátrixának nevezem az An , m ai , j , ahol ai,j=1, ha a vi csúcsba fut ( ) 45 be az ej. él, ai,j=-1 ha vi csúcsból fut ki az ej él és 0 egyébként, ha az ej. él hurokél a j oszlop minden eleme 0 Írányított gráf incidencia mátrixára is hasonló állítások igazolhatók, mint amilyeneket az írányítás nélküli gráfokra igazoltunk, de H.Poincare alábbi tétele rávílágít bizonyos eltérésekre. Tétel: Ha az A kvadratikus mátrix valamely G gráf incidencia mátrixának nem nulla determinánsú részmátrixa, akkor |det(A)|=1

. Bizonyítás: Természetesen itt a valós test fölött számoltuk a determinánst. Legalább egy oszlop van a szóban forgó determinánsban, amelyben csak egy elem különbözik 0-tól. fejtsük ki e sor szerint, és az eggyel alacsonyabb rendű aldeterminánsra ismételjük meg az elôbbi okoskodást. Ezt az eljárást megismételve annyiszor, mint amennyi a determináns rendje végezetül a bizonyítandó állítás adódik. A körmátrix A K (ki,j ) körmátrix azt mutatja, hogy a G ( E , ϕ ,V ) gráf élei mely körökben szerepelnek. Definició szerint 1, ha e j é le a ki körnek ki , j =  ki körnek . 0, ha ej nem é le a Irányított G gráfhoz, ha minden körhöz már kijelöltünk egy-egy bejárási irányt, akkor az alábbi utasítással rendelünk körmátrixot:  1, ha e é le a k körnek é s irá nyuk egyezô j i   . ki , j = −1 ha e j é le a ki körnek é s irá nyuk különbözô   0, ha e j nem é le a ki körnek Felírjuk az

alábbi irányított (irányítatlan) gráf K1,(K2) körmátrixát. Folytonos vonallal rajzoltuk a G gráf F feszitô fájának ( favázának) éleit. v5 v1 e3 e6 e1 e2 v2 e7 e8 v3 e9 v4 e4 e5 46 A körök ill. élek sorrendjét az alábbi szabály szerint adjuk meg. Kijelöljük a G gráf egy F favázát ( ha G nem volt összefüggô, akkor minden egyes komponensének megadjuk egy favázát). Elôször az F fára vonatkozó ei kötôéleket indexeljük ( itt i-vel) és az általuk meghatározott köröket ki-vel. Itt jegyezük meg, hogy a G gráf F favázára vonatkozóan az e él kötôél, ha nem éle F-nek. A G gráf F feszítôfája és e kötôéle egyértelműen meghatározza G-nek egy k körét, mivel F maximális összefüggô kört nem tartalmazó részgráfja volt G-nek. Írányított gráfok elôbb említett alapköreit F-re vonatkozó kötôéleinek megfelelôen írányítjuk 1  0 0  0 0  1 K1 =  1  1  0 0  0

1  0 0 0 0 0 1 1 0 0  1 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0  0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0  1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0  0 0 1 0 1 0 1 0  1 1 0 0 0 1 1 0 1 0 1 0 1 0 1 0  0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0  1 1 1 0 0 0 0 0 1 0 0 0  0 1 0 0 0 0 1 0  0 0 0 1 0 0 0 0  1 1 0 0 K2 =  −1 0 1 0  1 0 0 1  0 1 1 0  0 −1 0 1   0 0 1 −1  1 0 −1 1   0 1 1 −1 0 1 −1 0 0  0 −1 1 0 0 0 1 0 1 0  0 0 1 1 0 1 0 0 0 0  1 0 0 0 0 0 0 1 1 0  0 1 0 1 0  0 0 1 1 0 0 1 0 1 0  0 1 −1 0 0 0 0 0 0 0  0 0 0 0 0 Írjuk fel a korábban lerajzolt G ill. G írányított gráf illeszkedési A1, ill. A2 mátrixát is 1  1 A1 =  0  0  0 1 1 0 0 0 1 0 0 1 0  −1 1 −1 0   1 −1 0 −1 A2 =  0 0 0 0  0 0 1 1  0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0

0 0 1 0 −1 −1 0 0 0 0 0 0 0 0 1 1 0 0  0 0 ,  1  1 0  0 0,  −1 1   0 −1 0 0 1 Vegyük észre, hogy A*KT=N513 zérus mátrix és ABT=N135 is. Tétel: Ha A G gráfnak az A illeszkedési illetve K körmátrixának oszlopai ugyanazon élsorozat szerint 47 rendezettek, akkor A*KT=N1 és KAT=N2 (mod(2)) ( itt N1 és N2 is zérus mátrixokat jelöl). Bizonyítás: Az irányítás nélküli esetet tárgyaljuk és ott is csak az elsôt, mivel abból a második transzponálással megkapható. Ha az A ai sorához tartozó vi csúcs nem illeszkedik szorzatmátrix nij eleme 0, mivel a vi-re a kj körre, akkor a illeszkedô élek nem élei a kj körnek.Ha az A ai sorához tartozó vi csúcs illeszkedik a kj körre, akkor a szorzatmátrix nij eleme 0, mivel a vi-re illeszkedô élek közül pontosan 2 éle a kj körnek. A csúcsmátrix Irányított és irányítás nélküli gráfok esetén egyformán definiálhatjuk a csúcs- ( vagy

szomszédossági) mátrixot. A mátrix aij eleme azoknak az éleknek a számával egyezik meg amelyek vi-bôl futnak vj-be, természetesen ha az e él irányítás nélküli és ϕ (e) = v i,v j = v j,v i , akkor úgy tekintjük, hogy e vibôl megy vj-be és fordítva is azaz e vj-bôl megy vi-be. Azaz n csúcspontú irányítás nélküli G gráf csúcsmátrixa szimmetrikus n*n-es kvadratikus mátrix. Ha adott A G(E,ϕ,V) gráf, és |V|=n, akkor csúcsmátrixa n*n-es valós elemű mátrix. ) ( ( ) ( ) Definició: A G(E,ϕ,V) gráfnak Vn *n = ai , j ai , j = ∑1 ( ϕ ( e ) = vi , v j ) csúcsmátrixa, ha . Példa: Írjuk fel az alábbi írányított gráf szomszédossági (vagy adjecencia mátrixát ). v3 v1  0 0 0 0 0 0 0 0   v2  1 0 0 0 0 0 0 0 v 3  0 1 0 1 1 0 0 0   v7 v6 r v 4  0 0 0 0 1 0 0 0 v2 v5 v4 Érdemes V =  v5 0 1 0 0 0 0 0 0   v 6  0 0 0 0 0 0 1 1 v 7  0 0 0 0 0 0 0 2   v8  0 0 0 0 0

0 0 0 megjegyezni, hogy a csúcsmátrix a hurokélekrôl is informál. Továbbá, ha a G gráf csúcsaitr A módon indexelve, csúcs mátrixa r ill. B módon indexelve VB , akkor a sorok és az oszlopok VA alkalmas cseréjével elérhetô, hogy az egyik mátrixot átvisszük v1 v8 48 a másikba. Mivel ugyanazokat a sorokat és oszlopokat kell felcserélni, ezért van olyan P permutáció mátrix, melyre r r V A = P −1VBP . A fentiekben lényegében beláttuk a következô tételt Tétel: Ha a G1 gráfnak a csúcsmátrixa A, és a G2 gráfnak csúcsmátrixa B, akkor a G1 és a G2 mátrixok izomorfiájának szükséges és elégséges feltétele az, hogy létezzék olyan P permutáció mátrix melyre teljesül, hogy A = P −1BP . A csúcsmátrix hatványairól nem nehéz belátni az alábbi tételt. r n r Tétel: Legyen a G gráf csúcsmátrixa V A . V A -nek v in,j eleme megadja G vi. és vj. csúcsát összekötô irányított élsorozatoknak a számát. ( ) Bizonyítás:

Teljes indukcióval bizonyítunk n=1 esetén az állítás adódik a csúcsmátrix definiciójából. Teggyük fel, hogy n=m-re igaz az állítás és igazoljuk (m+1)-re. Jelölje vi(,k ) az indukciós feltevés szerint azon m hosszúságú irányított élsorozatok számát, melyek az i. csúcsot a k csúccsal kötik m össze. Továbbá jelölje vk( ,)j 1 az k. csúcsot a j. csúccsal összekötô élek számát. A vi(, k ) ⋅ vk( ,)j szorzat megadja az i csúcsból a j. csúcsba vezetô olyan irányított m+1 hosszúságú élsorozatok számát, melyek a k. pontra illeszkednek ( mikor m 1 is k, j szomszédja). k szerint összegezve a szorzatokat, megkapjuk az i. csúcsból a j csúcsba vi(, k ) ⋅ vk( ,)j vezetô m 1 k =n irányított élsorozatok számát, másrészrôl 1 m +1 m vi(, j ) = ∑ vi(, k ) ⋅ vk( ,)j , ami k =1 nem más mint a csúcsmátrix (m+1). hatványának i,j eleme r n I.Megjegyzés: Ha valamilyen n-re V A =0, akkor a gráf nem ( )

tartalmazhat írányított kört. II.Megjegyzés: A csúcsmátrix jól alkalmazható valamely A halmazon adott, ρ bináris reláció tulajdonságainak a jellemzésére. A Gρ(E,ϕ,V) gráfot a következô módon rendeljük az A halmazon adott ρ binér relációhoz: (i) G csúcspontjai A elemei lesznek, azaz A=V, (ii) (e = ( v , v ) ∈ E ⊆ ( A ⊗ A)) ⇔ ( v ρv ) , i j i j más szóval vi-t vj-vel , akkor és csak akkor köti él össze, ha vi ρ relációban áll vjvel. A ρ binér reláció, akkor és csak akkor reflexív, ha r Gρ ( E , ϕ ,V ) gráf V A csúcsmátrixának fôátlójában mindenütt 1 áll. 49 A ρ binér reláció, akkor és csak akkor r Gρ ( E , ϕ , V ) gráf V A csúcsmátrixa szimmetrikus. szimmetrikus, ha Matroidok A matroidelméletet Hassler Whitney alapozta meg a lineáris függőség algebrai elméletét vizsgáló 1935-ös dolgozatával. Az elmúlt 62 esztendőben több könyv is megjelent e tárgykörben. A matroidelmélet sok

alkalmazásra talált az áramkörök analízisében, kapcsolás elméletben, lineáris programozásban, hálóelméletben és gráfelméletben. Definíció: Az M=(E, I) rendezett párt matroidnak nevezzük, ha rendelkezik a következő tulajdonságokkal, E véges halmaz és I rendelkezik a következő tulajdonságokkal: (1) ∅ ∈ I azaz az üres halmaz eleme I -nek (2) ha x∈ I és y⊆x akkor y∈I-nek azaz I bármely x elemének bármely részhalmaza ismét eleme I -nek (3) ha olyan, hogy jelenti). Ip,Ip+1∈ I (I ∪ {x}) ∈ I . p -nek és Ip+1=Ip+1, ( e definíciónál az akkor I ∃x ∈ I p + 1 és I ugyanazt Példák: (i) Legyen G(E,ϕ, V) egy egyszerű gráf és I jelölje G E éleinek olyan részhalmazait, amelyek G-nek körmentes részgráfjait jelölik ki, ekkor az (E, I) pár rendelkezni fog a matroidoktól megkövetelt tulajdonságokkal. (ii) Legyen E az M mátrix oszlopvektorainak a halmaza azaz E={ m1,m2,m3,., mj,,ms}, E lineárisan

független oszlopvektorainak a halmazát jelöljük I -vel, ekkor az (E, I) pár matroidot alkot. Azokat az M=(E, I) matroidokat, amelyeknél E tekinthető valamely G gráf élei halmazának és ( I) elemei a G körmentes részgráfjai élei halmazának, grafikus matroidoknak mondjuk. Azokat az M=(E, I) matroidokat, amelyeknél E tekinthető valamely mátrix oszlopvektorai halmazának és I a független oszlopvektorok halmazának a halmazaként mátrixmatroidnak mondjuk. A matroidelmélet sok elnevezést, fogalmat vett át a lineáris algebrából ill. a gráfelméletből Kedves Olvasónknak ezekből nyújtunk át egy csokorra valót. Kicsit ömlesztve 50 mellőzve ez egyszer a formákat, reméljük ez nem vezet félreértésre. Az I elemeit független halmazoknak nevezzük Az I halmaz B elemét bázisnak nevezzük, ha maximálisan független. Itt a maximális jelző nyilván abban az értelemben értendő, hogy E bármelyik olyan A részhalmazát is vegyük, amelyik valódi módon

tartalmazza B-t (B⊂A) , akkor az A nem eleme Inek. Az E tetszőleges A részhalmazának a rangján r(A)-n az A maximálisan független részhalmazának az elemeinek a számát értjük. Ha E valamely A részhalmaza nem eleme I -nek, akkor azt függőnek mondjuk. Az A ( A ⊆ E ) részhalmaz lezártján ( vagy A által feszített ) azt az sp(A) halmazt értjük, melynek rangja megegyezik A rangjával és maximális. Maximális abban az értelemben, hogy nem létezik olyan sp(A)’ halmaz melynek a rangja ugyancsak megegyezne A rangjával és valódi módon tartalmazná sp(A)-t. Egy minimálisan függő K halmazt körnek nevezzünk. Minimálisan függő nyilván abban az értelemben, hogy K-nak semelyik valódi részhalmaza sem lesz függő, azaz K bármely valódi részhalmaza már eleme I -nek, de maga K nem eleme I nek. Tétel: Legyen X, Y független részhalmazok M-ben. Ha X elemeinek a száma kevesebb mint Y elemeinek a száma azaz X < Y , akkor létezik olyan Z⊆Y-X, hogy X

∪ Z = Y és X∪Z független M-ben. Bizonyítás: Legyen Z0 olyan, hogy tulajdonságokkal: rendelkezzék az alábbi (i) Z0⊆Y-X. (ii) X∪ Z0 független M-ben. (iii) Ha X ∪ Z0 ≥ X ∪ Z . X∪Z független M-ben és Tegyük fel, hogy létezik olyan Z0, hogy Z⊆Y-X akkor X ∪ Z 0 < Y . ekkor létezik egy olyan Y0⊆Y, melyre Y0 = X ∪ Z 0 + 1 . Mivel Y0 független lehet alkalmaz a matroidok 3. axiómáját Létezik y ∈Y0 − ( X ∪ Z 0 ) olyan, hogy X ∪ Z 0 ∪ { y} független M-ben, de a Z 0 ∪ { y} létezése ellentmond (iii)-nek. Ezért kész. X ∪ Z 0 ≥ Y , s ezzel a bizonyítás Következmény: Az M matroid bármely B bázisának az elem száma megegyezik M rangjával. 51 Bizonyítás: Legyen  B1  < B2 , akkor az szerint létezik olyan Z⊆ { B2 - B1 } olyan , független, ami viszont ellentmond  B1  maximális. előző tétel hogy Z∪ B1  Következmény: Ha  B1  és  B2  bázisai M-nek és x ∈ B 1

− B 2 , akkor létezik olyan y ∈ B2 − B1 melyre teljesül, hogy bázisa M-nek. (B ∪ {y}) − {x} 1 Bizonyítás nélkül megemlítjük itt néhány tulajdonságát a rang függvénynek. Tétel: Legyen adott az M=(E, I) x∈E, ekkor: matroid és A,B⊆E és 1. 0 ≤ r ( A) ≤ A 2. Ha A⊆B, akkor r(A) ≤ r(B) 3. r ( A) ≤ r ( A ∪ {x}) ≤ r ( A) + 1 4. Részmoduláris egyenlőtlenség r ( A) + r ( B) ≥ r ( A ∪ B) + r ( A ∩ B) 5. Ha r ( A ∪ {x}) = r ( A ∪ { y}) =r(A), akkor r ( A ∪ {x} ∪ { y}) =r(A) Ha az E n elemű halmaz k (0 ≤ k ≤ n) elemű részhalmazainak a halmazát választjuk I -nek, akkor egy M matroidot kapunk, melyet uniform matroidnak szokás nevezni. Jele: Un,k Az Un,n matroidot szabad matroidnak mondjuk, mivel E bármely részhalmaza független, az Un,0 matroidot triviális matroidnak nevezzük , mivel csak az üres halmaz ∅ független benne. Nem nehéz belátni, U4,2 nem lehet grafikus matroid, mivel nincs olyan 4 élű gráf, hogy

bármely 3 éle kört alkosson. A körökkel kapcsolatos következő állítások közvetlenül a definíció következményei. (1) Bármely kör bármely valódi részhalmaza független. Ha C1 és C2 különböző körök, akkor C1⊄C2. (2) Ha C kör , akkor r(C)=C-1. (3) Az M matroidban, akkor és csak akkor nincs kör, ha E minden részhalmaza független, ekkor M-nek csak egy bázisa van ti. maga E Gráfok színezése 52 A nóban soha ne feledjük kezdôi mivoltunkat. Vekerdy Tamás: A színészi hatás eszközei-Zeami mester művei szerint, Gondolat, 1988. , 221 o Gráfok síkba rajzolhatóságáról beszélve definiáltuk, a tartomány (illetve, "ország") fogalmát. Térképek színezésénél szokásos eljárás az, hogy szomszédos országokat különbözô színekkel színeznek ki. Két országot szomszédosnak szokás nevezni, ha a közös határuk hossza 0-nál nagyobb szám, azaz van közös élük. A G síkbeli gráfot k színezhetônek mondjuk, ha

G tartományait ki lehet festeni k színnel oly módon, hogy bármely két szomszédos ország különbözô színű. Ha az adott síkba rajzolható G gráf duálisa G, akkor a G k színnel való színezhetôsége, G-re vonatkozólag azt jelenti, hogy G csúcsait ki lehet színezni k színnel oly módon, hogy szomszédos csúcsok színei különbözôek. Azaz G bármely élének két végpontja különbözô színű. A színezési probléma duális gráfra való átfogalmazása lehetôséget ad arra, hogy tetszôleges gráf színezhetôségérôl beszéljünk. Definíció: A G gráf kromatikus száma k, ha G csúcsai k színnel kiszínezhetôk, de kevesebbel (k-1)-el már nem. 1840.-ben Möbius egy elôadásában, megfogalmazta a négyszínsejtést, mely azt állítja, hogy bármely síkbeli térkép kiszínezhetô 4 színnel. A sejtést De Morgan tette ismerté Ô a problémát Franci Guthrietól vette át 1850 körül. Cayley 1879ben jelentet meg egy dolgozatot a

négyszínsejtésrôl a Proc Royal Geographical Society elsô kötetében. 1890-ben Heawood egy Kempetôl származó hibás bizonyítást vizsgál és sikerül bebizonyítania, hogy síkgráfoknál öt szín elegendô a színezéshez. A négyszínsejtésre K Appel és W Haken 1976-ban számítógép felhasználásával adtak bizonyítást. Bizonyításukban azonban azóta többen és többször is találtak hibát, de azok javíthatónak bizonyultak. A matematikusok egyrésze vitatja azt, hogy egy tételnek a számítógépes "bizonyítása" elfogadható e. A továbbiakban síkbeli gráfokról szeretnénk megmutatni, hogy öt színnel mindig ki színezhetôk. Azt belátni, hogy legalább 4 szín szükséges, könnyű. Például a tetraéder síkba rajzolt gráfja csak 4 színnel színezhetô ki. A D B C 53 Ha a G gráfunk v pontja másodfokú és v-re e1,e2 illeszkedett ( ϕ(e1)=(u,v) és ϕ(e2)=(v,w), akkor v-t törölve és v e1,e2 élek, helyett egy e élt

bevezetve ( ϕ(e)=(u,w)) a színezés módja változatlan marad viszont az új gráfunkban eggyel kevesebb másodfokú pont lesz. Elérhetô , hogy olyan síkbeli gráfokkal foglalkozunk amelyeknek nincsen másodfokú csúcspontjai. Ha valamely pont foka 3-nál nagyobb, akkor a G gráfunkat átalakíthatjuk, oly módon, hogy a kiszínezhetôsége "ne változzék", de legfeljebb csak harmadfokú pontja legyen. Legyen az a pont például az ábrának megfelelôen ötödfokú pont. Rajzoljunk körülötte egy C kört. S az a pont helyett vezessünk be 5 új pontot, melyek mindegyike már harmadfokú. Ha ez utóbbi gráf kiszínezhetô, akkor kiszínezhetô lesz az eredeti is. Elegendô azt látni, hogy ha az új gráf C körét ponttá zsugorítjuk, s a kört határoló tartományok színezését változatlanul, hagyjuk, akkor a régi gráfnak egy jó színezését kapjuk. Ezek szerint síkbeli gráfok színezhetôségét sikerült vissza vezetni arra az esetre, mikor is a gráf

minden pontja harmadfokú. Az alábbiakban bebizonyítunk egy tételt, mely azt mondja, hogy bármely síkba rajzolható gráfnak van olyan tartománya, melyet 5 vagy ötnél kevesebb él határol. Ha sikerül megmutatnunk, hogy az öt vagy ötnél kevesebb éllel, határolt tartományok mindig elhagyhatók, anélkül, hogy a megváltozott gráf színezhetôsége változna, akkor végezetül is megoldottuk az ötszíntétel bizonyítását. A 38. oldalon szereplô (D1) formula szerint 2q = 2 ⋅ ϕ 2 + 3 ⋅ ϕ 3 + 4 ⋅ ϕ 4 + . + k ⋅ ϕ k + , ahol is q az élek számát, ϕi az "i" darab él által határolt tartományok számát jelölte. Ha a G gráfunk csúcsainak a számát "n" jelöli, akkor ( S 2) 3n = 2 ⋅ ϕ 2 + 3 ⋅ ϕ 3 + 4 ⋅ ϕ 4 +.+ k ⋅ ϕ k + , továbbá mivel t az bg összes tartomány számát jelölte S 3 t = ϕ 2 + ϕ 3 + ϕ 4 + . + ϕ k + Szorozzuk meg a D1-t 3-mal S2-t 2-vel és S3-t 6-tal, ekkor 6q = 6 ⋅ ϕ 2 + 9 ⋅ ϕ 3 +

12 ⋅ ϕ 4 + . +3k ⋅ ϕ k + bS 2g6n = 4 ⋅ ϕ 2 + 6 ⋅ ϕ 3 + 8 ⋅ ϕ 4 + . +2k ⋅ ϕ k + 54 bS 3g6t = 6ϕ 2 + 6ϕ 3 + 6ϕ 4 + . +6ϕ k + a C C kapjuk. Ha az euler-formulát végigszorozzuk 6-tal, akkor 12 = 6n − 6q + 6t adódik, s a fenti képleteket behelyettesítve bS 4g12 = 4ϕ 2 + 3ϕ 3 + 2 ϕ 4 + ϕ 5 − ϕ 7 − 2 ϕ 8 − . − (k − 6) ϕ k + adódik Az S4-es formula jobb oldalának pozitívnek kell lennie, ezért harmadfokú reguláris gráfnak van legalább egy olyan tartománya, melyet 5 vagy 5-nél kevesebb él határol. Azaz bebizonyítottuk a következô tételt. Tétel: Ha a G gráf síkba rajzolható harmadfokú reguláris gráf, akkor van olyan tartománya, melyet legfeljebb 5 él határol. Az ötszín-tétel bizonyításához rendre megmutatjuk, hogy ha a G gráfunknak kettô, három, négy vagy öt él által határolt tartományát "elhagyjuk", és az új G gráf öt színnel jól színezhetô, akkor G is színezhetô

legfeljebb ötszínnel. S mivel a G-bôl származtatott gráfok tartományainak a száma rendre csökkenni fog elôbb vagy utóbb eljutunk egy olyan G(n) gráfhoz melynek legfeljebb öt tartománya van, s akkor az már triviálisan színezhetô ötszínnel. Tehát az ötszíntétel bizonyításához elegendô megmutatni, hogy ha a G gráfnak "elhagyjuk" egy "k" (2 ≤ k ≤ 5) éllel határolt tartományát, s a nyert G gráf legfeljebb 5 színnel jól színezhetô, akkor G is jól színezhetô 5 színnel. (I) Tegyük fel, a G harmadfokú reguláris síkba rajzolható gráfunknak van egy A tartománya, melyet az "a"és "b" csúcsokra illeszkedô 2 él határol. Legyen az "a" csúcs másik szomszédos csúcsa "c" ,és "b" szomszédja "d". Töröljük az "a" ill "b" csúcsokat és a rájuk illeszkedô éleket. A "c" ill "d" csúcsokat kössük össze egy új éllel B Ha

az A, a B és C tartományokkal volt határos, melyeket az I ill. II I színre festettünk, és A-t III-ra, c a b A akkor. Ha az új G gráf B ill C d III C tartományának a színezése I ill. II II. akkor az eredeti állapot helyreállítása esetén A színe újra lehet III. s nem kell változtatni a G gráfnak esetleg meglévô többi tartományának a színezésén. 55 (II) Ha a G gráf a D háromszögtartományt tartalmazza, melyet az A, B, C tartományok A határolnak, akkor az a,b csúcsokat I törölve egyesítsük a D és a C B b IV D tartományt, s jelöljük mondjuk D+C II a -vel. Az így nyert G gráfnak, ha C III az A I-vel,B II-vel és D+C tartománya III-vel van színezve, akkor a C tartományt a visszaállítás után IV-vel színezzük. (III) Tartalmazza most a G gráfunk az F tartományt, melyet négy oldal, és így négy tartomány határol, s jelölje azokat rendre A,B,C,D. A négy tartomány közül a szembe fekvôk közül feltétlenül van kettô m n

olyan, melyek nem szomszédosak. Az ábránknak megfelelôen legyen B II a az a kettô most B és D. r b Egyesítsük a B,F, és D p III V tartományokat oly módon, hogy a A F C I c "b","p","u","c" pontokat és a u rájuk illeszkedô éleket d v D IV töröljük. Valamint az "a"ill d csúcsokat és az r ill. v csúcsokat egy-egy új éllel kötjük össze. Az ily módon nyert G gráfnak kettôvel kevesebb tartománya van mint G-nek, és harmadfokú reguláris gráf. Ha G színezésében A ill C színe I ill. III, és B+F+D színe II, akkor a vissza állítás után F színe legyen IV és D színe II. (IV) Legyen most G olyan, hogy tartalmazza az A,B,C,D,E E e D A b a F d c B C tartományok által határolt ötszögtartományt. Hasonló okoskodással mint az elôbb belátható, hogy van olyan két tartomány az A,B,C,D,E tartományok között melyek nem szomszédosak legyenek azok például B és D. Töröljük G-nek (b,c)-t

ill. (e,d)-t összekötô éleit Itt elôfordulhat, hogy az A,C,E tartományok szomszédosak és színezésükhöz három különbözô szín kell, mondjuk legyenek azok rendre I,II,III a negyedik IV szín D+F+B színezéséhez kell. S az eredeti gráf visszaállításánál a D és B tartományok színe lehet IV, de F színezéséhez már fel kell használni az V. ötödik színt Ily módon bebizonyítottuk az alábbi tételt. Tétel( ötszín-tétel): Bármely síkba rajzolható sokszög gráf kiszínezhetô öt színnel. 56 Ramsey-féle problémák Definició: Az n(m,k) számot Ramsey-féle számnak nevezzük, ha rendelkezik az alábbi tulajdonságokkal (i) ha a G(E,ϕ,V) gráfnak a csúcspontjainak a száma V = n ≥ n(m, k ) , akkor vagy G -nek van egy m csúcspontú teljes részgráfja, vagy G komplementere tartalmaz egy k csúcspontú teljes gráfot, (ii) van olyan G(E,ϕ,V) gráf, melynek csúcspontjainak a száma V = n(m, k ) − 1 és G-nek nincs m pontú teljes

részgráfja, és a komplementerének sincs k pontú teljes részgráfja, Az (ii) tulajdonsággal rendelkezô gráfokat extrém gráfoknak nevezzük. Szemléletesebb megfogalmazása a Ramseyféle számoknak a következô: Ha az n(m,k) pontú teljes gráf éleit tetszés szerint pirosra vagy zöldre színezzük, akkor vagy egy piros színű teljes m gráfot vagy egy zöld színű k teljes gráfot kapunk, továbbá az n(m,k)-1 pontú teljes gráf éleit piros illetve zöld színnel lehet úgy színezni, hogy sem piros színű teljes m csúcspontú, sem zöld színű teljes k csúcspontú gráfot nem tartalmaz. (RT1) Tétel: Ha ∀m , k ∈ N ,akkor n(m, k ) = n( k , m) . Bizonyítás: A színek felcserélésével adódik az állítás. (RT2) Tétel: Ha ∀m , k ∈ N ,akkor n(1, k ) = n(m,1) = 1 n(2, k ) = k , n(m,2) = m . Bizonyítás: Az egy pontból álló gráf nem létezô élét egyaránt tekinthetjük pirosnak ill. zöldnek is Ha a k pontú teljes gráfnak minden színe zöld,

akkor tartalmaz egy zöld színű teljes gráfot, ha csak egy éle is piros, akkor tartalmaz egy 2 pontú teljes piros gráfot. Ha az m pontú teljes gráfnak minden színe piros, akkor tartalmaz egy piros színű teljes gráfot, ha csak egy éle is zöld, akkor tartalmaz egy 2 pontú teljes zöld gráfot. (RT3) Tétel: Ha n(m-1,k) és (m,k-1) létezik, akkor n(m,k) is létezik és n(m,k)≤n(m-1,k)+n(m,k-1). 57 Bizonyítás: Legyen adott a Kn(m-1,k)+n(m,k-1) teljes gráf és élei tetszôlegesen színezve pirossal ill. zölddel, és legyen u valamely csúcspontja. Jelölje a G1 az u-ból induló pirosélek és G2 az u-ból induló zöld élek végpontjai által felfeszített részgráfjait Kn(m-1,k)+n(m,k-1)-nak. Legyen G1 csúcspontjainak a száma n1 és G2 csúcspontjainak a száma n2 , ekkor n1 + n2 + 1 = n( m - 1,k ) + n( m ,k - 1) piros élek és vagy (I) n1 ≥ n( m - 1,k ) vagy zöld élek (II) n2 ≥ n( m ,k - 1). Az (I) esetben G1 vagy egy m-1 pontú teljes G1 G2 piros

gráfot tartalmaz és G1-hez hozzávéve u-t és az u-ból G1-be u futó, piros éleket Kn(m-1,k)+n(m,kegy m pontú teljesen 1)-nek piros részgráfját kapjuk, ha G1ben k pontú teljes zöld részgráfunk volt, akkor az nyilván részgráfja Kn(m-1,k)+n(m,k-1)nek is. Így az (I) esetben Kn(m-1,k)+n(m,k-1)-tartalmaz vagy egy m pontú teljes piros, vagy egy k pontú teljes zöld gráfot. A (II) esetben is teljesen hasonlóan belátható, hogy Kn(m1,k)+n(m,k-1)-tartalmaz vagy egy m pontú teljes piros, vagy egy k pontú teljes zöld gráfot, s ezzel a bizonyítás kész. (RT4) Tétel( Erdôs Pál és Szekeres György): Ha ∀m , k ∈ N  m + k − 2 ,akkor n(m, k ) ≤  .  m−1  Bizonyítás: k szerinti teljes indukcióval bizonyítunk. k=1 esetén tetszôleges m-re n(m,1)=1 (R1) szerint, és mivel  m + 1 − 2 1≤   ezért, ekkor az állítás igaz. Tételezzük fel, hogy  m−1  az állításunk tetszôleges m-re igaz k=h-1 esetén és

bizonyítsuk k=h-ra. Ez utóbbi állítást m szerinti teljes  1 + h − 2 indukcióval bizonyítjuk, m=1 esetén 1 ≤   . Tegyük fel,  1−1  hogy (m-1)-re már igaz az állítás , bizonyítsuk m-re. Ezek szerint tudjuk, hogy  m + h − 3  m + h − 3 (i) n(m − 1, h) ≤  .  és n(m, h − 1) ≤   m−1   m−2  Az (RT2) szerint ekkor létezik n(m,k) és kisebb egyenlô, mint az n(m-1,k)+n(m,k-1). Felhasználva az (i) becsléseket  m + k − 3  m + k − 3 (m + k − 3)! + (m + k − 3)! n(m, k ) ≤   + =  m − 2   m − 1  ( k − 1)!(m − 2)! ( k − 2)!(m − 1)! 58    m + k − 2 m−1 k −1  = = (m + k − 3)! +   ( k − 1)!(m − 1)! ( k − 1)!(m − 1)!  m − 1  megkapjuk a tétel állítását. Legyenek r, q1, q2,., qt egynél nagyobb vagy eggyel egyenlô egész számok. Az N (q1 , q2 ,, qt , r ) (általános) Ramsey-szám, ha eleget

tesz a következô feltételeknek: 1; Ha S ≥ N (q1 , q2 ,., qt , r ) , akkor bármilyen esetén létezik olyan i ∈{1,2,., t } , és Pr ( S ) = A1 ∪ A2 ∪.∪ At S , ⊆ S , hogy S , = qi és hogy Pr ( S , ) ⊆ Ai 2; az N (q1 , q2 ,., qt , r ) -nél kisebb szám nem rendelkezik az 1.-es tulajdonsággal ( azaz N (q1 , q2 ,, qt , r ) egész, amelyre az 1 tulajdonság teljesül. a legkisebb olyan Tétel: Az N (q1 , q2 ,., qt ,1) = q1 + q2 ++ qt − t + 1 Megjegyzés: Az előbbiekben szereplô n(m,k) az N (m, k ,2) speciális esetnek felel meg. A Pr ( S ) az S halmaz r elemű részhalmazainak a halmazát jelölte. Generátorfüggvények, rekurzív sorozatok Természetes számok halmazán gyakran értelmeznek olyan valós esetleg komplex értékű f(n) függvényeket, melyeknek az n helyen felvett értékei az 1,2,.,(n-1) helyeken felvett értékeitôl függnek. Például egy 10 éve fennálló vállalkozás alaptôkéje nyilván függ, az elôzô években az

alaptôke növelésére esetleg csökkentésére fordított összegek nagyságától, bár ezen összefüggések kiváltképp napjainkban eléggé ködösek lehetnek. Mi itt csupán olyan rekurzív összefüggésekkel fogunk foglakozni, melyet matematikán belül lineárisan rekurzív sorozatoknak szokás nevezni. Definíció: Az (RKI) u n + k = a k −1 u n + ( k −1) + a k − 2 u n + ( k − 2 ) +.+ a1 u n +1 + a 0 u n 59 ( az ai- k valˇs vagy komplex konstansok ) képlettel és az u0 ,u1 ,u2 ,.,uk − 2 ,uk −1 kezdô értékekkel adott sorozatot k-ad rendű lineárisan rekurzív sorozatnak nevezzük. Másodrendű lineáris rekurzív sorozatok körébôl máig a legnépszerűbb, s valószínűleg a legrégibb példa a Fibonaccisorozat u0 = 0, u1 = 1, u2 = 1, u3 = 2 , u4 = 3, u5 = 8, ., un + 2 = un +1 + un Leonardo Fibonacci ( eredeti neve Leonardo Pisano,(pisai Leonardo)) Liber Abaki ( könyv az abakuszról ) c. művében jelenik meg elôször. A Fibonacci-sorozat a

következô problémából keletkezett: Hány pár nyúl származhat egyetlen pártól, ha (i) minden pár havonta egy párt nemz, amely a második hónaptól kezdve lesz nemzôképes és (ii) mindegyik nyúl halhatatlan? Definíció: Az (RKI) k-ad rendű lineáris rekurzív sorozat karakterisztikus polinomjának nevezzük a következô polinomot (RK2) f ( x ) = x k − a k −1 x k −1 − a k − 2 x k − 2 −.− a 2 x 2 − a 1 x − a 0 Ha az (RK2) gyökei α 1 , α 2 ,., α k páronként különbözôek, akkor a sorozat n. tagja felírható, (RK3) u n = c k α nk + c k −1α nk −1 +.+ c2 α 2n + c1α 1n alakban Ha azonban csak m<n gyökünk van, s az i. gyök multiplicitása si, akkor sorozatunk n. tagja az alábbi alakban írható: (RK4) un = i=m α in (ci ∑ i =0 s −1 ,0 + ci,1α i +. + ci, si −1α isi − 2 + ci, si α i i ) Látható, hogy a sorozat általános alakja teljesen analóg az állandó együtthatójú lineáris differenciál egyenletek

megoldásával. Tétel: Ha az u n + k = a k −1 u n + ( k −1) + a k − 2 u n + ( k − 2 ) +.+ a1 u n +1 + a 0 u n összefüggést a Z1 (z1,1 ,z1,2 ,.,z1,j ,) ,Z2 (z2,1 ,z2,2 ,,z2,j ,) ,,Zk (zk ,1 ,zk ,2 ,,zk ,j ,) sorozatok kielégítik, akkor tetszôleges c1 ,c2 ,.,ck konstansok esetén kielégíti, a sorozat is, ahol V (v 1 ,v 2 ,.,v j ,) v j = c1 z1, j + c2 z 2 , j +.+ c k z k , j , ( j = 0,1, 2 ,, n ,) Bizonyítás: A tétel feltételei szerint bármely i = 1, 2 ,., k és (n = k , k + 1, k + 2 ,., h,) esetén teljesülnek az alábbi azonosságok, 60 (RK5) z i ,n + k = a k −1 zi ,n + ( k −1) + a k − 2 zi ,n + ( k − 2 ) +.+ a1 zi ,n +1 + a 0 zi ,n Szorozzuk meg az i.-t ci-vel majd adjuk össze ôket , ekkor felhasználva azt, hogy v j = c1z1,j + c2z2,j + . +ckzk ,j adódik, hogy v n + k = a k −1 v n + ( k −1) + a k − 2 v n + ( k − 2 ) +.+ a1 v n +1 + a 0 v n s ez az amit bizonyítani kellett. Nem okoz különösebb nehézséget megmutatni, hogy ha az

(RK1) rekurzív összefüggés karakterisztikus polinomjának αi gyöke, akkor zi,j = α ij ( j = 0, 1, 2 ,., n ,) sorozat megoldása (RK1)-nek Ha αi gyöke (RK2)-nek k k −1 k −2 2 , akkor α i = a k −1α i + a k − 2 α i +.+ a 2 α i + a1α i + a 0 azonosságot végig szorozhatjuk, α i n-nel és látható, hogy az (RK1) teljesül. Példa: A Fibonacci-sorozat karakterisztikus egyenlete x 2 = x + 1, gyökei α 1,2 = 1± 5 . 2 Mivel un-t un = c1α 1n + c2 α n2 alakban keressük írjunk be n helyére n=0 és n=1-t, c1 ,c2 -re kapjuk az alábbi lineáris egyenletrendszert c1 + c2 =0 1 , melynek megoldása c1 = −c2 = . A Fibonacci5 5 (c1 − c2 ) = 1 2 sorozat n. elemét ezek szerint írhatjuk az n 1 1+ 5 1 1− 5   −   (RK6) un = 5 2  5 2  n alakban, mely távolról sem tűnik triviálisnak. Megemlítjük, hogy külön folyóirata van a Fibonacci-féle számoknak. Rekurzív sorozatokra vonatkozólag, nemzetközileg is elismert,

szép eredmények, kapcsolódnak Kiss PÚterés Peth˘ Atilla nevéhez, mindketten a Gy˘ry Kßlmßn által létrehozott debreceniszámelméleti-iskola jeles személyiségei. A generátor függvény elnevezést többféle értelemben is használják a matematika különbözô területein. Mi itt kétféle lehetséges értelmezést fogunk megemlíteni. Elôször az úgy nevezett partíciós problémákra vonatkozó generátor függvényekrôl beszélünk. Legyenek adottak az n1 , n2 ,, nk pozitív egészek. Kérdezzük, hogy az m szám hányféleképpen állítható elô az n1 , n2 ,., nk -k összegeiként oly módon, hogy bármely n1 , n2 ,., nk számot többször is felhasználhatunk és a sorrend nem számít. A partíciós problémának az elôbbi változatát szokás pénzváltási problémának is nevezni. Vizsgáljuk meg, például, hogy valamely számot, hányféleképpen lehet elôállítani az 1,2,3,5 számok összegeként. Tekintsük a következô függvényt 61 ( )( )

f ( x ) = 1 + x 1 + x 2 +.+ x n + ⋅ 1 + x 2 + x 4 ++ x 2 n + ( )( ) ⋅ 1 + x 3 + x 6 +.+ x 3n + ⋅ 1 + x 5 + x 10 ++ x 5n + = (GK1) = (1 − x )(1 − x 1 2 )(1 − x )(1 − x ) 3 5 Az f(x) függvény lesz ez esetben a generátor függvény. Nem vizsgáljuk, hogy az f(x) elôállításában szereplô hatványsorok konvergensek e vagy sem. Ha az f(x)-t hatványsorba fejtjük f ( x) = (GK2) (1 − x )(1 − x 1 2 )(1 − x )(1 − x ) 3 5 = A0 + A1 x + A2 x 2 +.+ Am x m + ,akkor az Am együttható fogja megmutatni, hogy m-t, hányféleképpen lehet felírni az 1,2,3,5 számok összegeiként. Az Am együtthatók meghatározására különbözô módszerek léteznek. Egy lehet a következô: A (GK2) nevezôjében a szorzásokat elvégezve adódik (GK3) f ( x ) = (1 − x − x 1 2 +x +x −x −x +x 4 7 9 10 11 ) = A0 + A1 x + A2 x 2 +.+ Am x m + A nevezôvel végig szorozva, s figyelembe véve, hogy xm együtthatója 0 a baloldalon, ha m>0 az Am

együtthatókra az alábbi rekurzív összefüggést nyerjük. (GK4) A m = A m −1 + A m −2 − A m −4 − A m −7 + A m −9 + A m −10 − A m −11 A kezdeti értékekre, ha m<0, akkor Am =0 és ha m=0, akkor A0=1. Más módon is meghatározhatjuk a (GK3) formula oldalán álló hatványsor együtthatóit. A (GK4) formula oldalán végezzük, el az osztást! (GK4) f ( x) = (1 − x − x 1 2 + x 4 + x 7 − x 9 − x 10 + x 11 ( jobb jobb ) ) 1 : 1 − x − x 2 + x 4 + x 7 − x 9 − x 10 + x 11 = 1 + x + 2 x 2 + 3x 3 + 4 x 4 + 6 x 5 +. x + x 2 − x 4 − x 7 + x 9 + x 10 − x 11 2 x 2 + x 3 − x 4 − x 5 − x 7 − x 8 + x 9 + 2 x 10 − x 12 3x 3 + x 4 − x 5 − 2 x 6 − x 7 − x 8 − x 9 + 2 x 10 + 2 x 11 + x 12 − 2 x 13 4 x 4 + 2 x 5 − 2 x 6 − 4 x 7 − x 8 − x 9 − x 10 + 2 x 11 + 4 x 12 + x 13 − 3x 14 6 x 5 + 2 x 6 − 4 x 7 − 5x 8 − x 9 − x 10 − 2 x 11 + 4 x 12 + 5x 13 + x 14 − 4 x 15 62 Az alábbi definícióban egy

sorozathoz más módon rendelünk generátor függvényt. Definíció: Adott A=(a0 , a1 ,., an ,) sorozat 2 m generátorfüggvénye az f ( x ) = a 0 + a1 x + a 2 x +.+ a m x + hatványsor Az esetek túlnyomó többségében itt sem érdekes, hogy a definícióban szereplô hatványsor milyen intervallumon konvergens. Érdemes megvizsgálni a generátorfüggvények segítségével a Fibonacci-sorozatot. Legyen (GK5) G( x ) = u0 + u1 x + u2 x 2 +.+ un x n + a Fibonacci-sorozat generátorfüggvénye az elôzô definíció értelmében, s szorozzuk meg x-xel, majd x2-tel, nyerjük az alábbi képleteket: (GK6) xG( x ) = u0 x + u1 x 2 + u2 x 3 +.+ un x n +1 + (GK7) x 2 G( x ) = u0 x 2 + u1 x 3 + u2 x 4 +.+ un x n + 2 + Ha a (GK5)-bôl rendre levonjuk (GK6)-t és (GK7)-t adódik, hogy: (GK8) =x. (1 − x − x )G( x) = u 2 A (GK8)-ból megkapható (GK9) G( x ) = 0 + (u1 − u0 ) x + (u2 − u1 − u0 ) x 2 +.+ (un − un −1 − un − 2 ) x n + G(x) zárt alakja egyszerű

osztással x . 1− x − x2 A G(x) jobboldalán álló racionális-tört-függvényt bontsuk parciális törtek összegére a valós test felett. Figyelembe 1 véve, hogy a nevezôben szereplô polinom gyökei −1 ± 5 : 2 ( (GK10) G( x ) = ahol ) x 1  1 1  = +  , 2 1− x − x 5  1 − αx 1 − α x  α =1−α = ( ) 1 1− 5 . 2 A (GK10) jobb oldalán szereplô 1 1 függvények az , 1 + α x + α 2x 2 +. + α nx n +, 1 − αx 1 − αx 1 + α x + α 2x 2 +. + α nx n + mértani sorokkal egyeznek meg Figyelembe véve, hogy abszolút konvergensek alkalmas módon átrendezve, megkapjuk, hogy a Fibonacci-sorozat tagjai írhatók 63 n 1  n  α − α  alakban összhangban a korábbi eredménnyel (RK6) 5 tal. Megjegyezzük, hogy a Fibonacci-sorozatnak ezt az alakját a fenti levezetési technika használatával L. de Moivre már 1730.-ban közölte un = 64