Portal:Matematika/Vetrina/Jannar 2010

Minn Wikipedija, l-enċiklopedija l-ħielsa

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 fejn hi funzjoni . Il-vokabularju tat-teorija issellef mill-ġeometrija tal-poliedri. Dawn jikkorrispondu ma' każ partikulari ta' graf fejn fit-tern , hu s-sett tal-vertiċi tal-poliedru, ix-xfar tal-poliedru u jekk ix-xifer jgħaqqad iż-żewġ vertiċi u . Dan il-vokabularju baqa' jintuża u għal graf ġenerali, ngħidulu s-sett tal-"vertiċi" tiegħu, is-sett tax-"xfar" tiegħu ("arki" jekk il-ġraf ikun orjentat) u hi l-funzjoni tal-inċidenza tiegħu li ma' kull xifer (ark) tassoċja par vertiċi.

Aktar fuq it-Teorija tal-grafi...