Portal:Matematika/Vetrina/Jannar 2010

Teorija tal-grafi

Fil-matematika it-terminu graf (li m'għandniex inħalltuh ma' grafiku ta' funzjoni) ifisser oġġett li jiġġeneralizza l-kunċett ta' relazzjoni binarja u ta' poliedru. Dan l-oġġett li niddeskrivu hawn hu utli ħafna fil-mudellar ta' bosta problemi fil-"ħajja ta' kuljum" (jiġifieri li niltaqgħu magħhom barra l-matematika, bħal dawk li għandhom x’jaqsmu ma' l-idea ta'xibka fl-informatika, xjenzi soċjali, problemi tat-traffiku u oħrajn).

Definizzjoni

• Definizzjoni ta' Berge

Nistgħu ngħidu li t-teorija tal-grafi bdiet fis-snin 60, bix-xogħol tal-matematiku Franċiż, Claude Berge (1926 - 2002),Graphe et Hypergraphes (Grafi u ipergrafi), allavolja l-kunċett hu ħafna iżjed antik. Li għamel Berge kien li ġabar f'din it-teorija bosta riżultati tal-kombinatorja li kienu diġà magħrufin, u mmotiva l-istudju tal-grafi b'applikazzjonijiet, rabtiet mat-teorija tal-logħob u b’konġetturi.

Daż-żmien nagħtu definizzjoni intwittiva tal-grafi (ara iżjed l-isfel) li tidher differenti min dik li ta Berge, imma infatti hija ekwivalenti: Berge iddefinixxa graf bħala tern $\displaystyle {(V,E,\phi )}$ fejn $\displaystyle {\phi }$ hi funzjoni $\displaystyle {\phi :E\rightarrow V\times V}$. Il-vokabularju tat-teorija issellef mill-ġeometrija tal-poliedri. Dawn jikkorrispondu ma' każ partikulari ta' graf fejn fit-tern $\displaystyle {(V,E,\phi )}$, $\displaystyle {V}$ hu s-sett tal-vertiċi tal-poliedru, $\displaystyle {E}$ ix-xfar tal-poliedru u $\displaystyle {\phi (e)=(u,v)}$ jekk ix-xifer $\displaystyle {e}$ jgħaqqad iż-żewġ vertiċi $\displaystyle {u}$ u $\displaystyle {v}$. Dan il-vokabularju baqa' jintuża u għal graf ġenerali, $\displaystyle {V}$ ngħidulu s-sett tal-"vertiċi" tiegħu, $\displaystyle {E}$ is-sett tax-"xfar" tiegħu ("arki" jekk il-ġraf ikun orjentat) u $\displaystyle {\phi }$ hi l-funzjoni tal-inċidenza tiegħu li ma' kull xifer (ark) tassoċja par vertiċi.

Aktar fuq it-Teorija tal-grafi...