Teorija tal-grafi: Differenza bejn il-verżjonijiet

Content deleted Content added
m Bot: Migrating 54 interwiki links, now provided by Wikidata on d:Q131476
No edit summary
Linja 1:
[[Stampa:6n-graf.svg|thumb|200px|Fig. 1: Graf mhux orjentat b'6 vertiċi u b'7t ixfar.]]
 
Fil-matematikaMatematika itt-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 huhuwa utli ħafna fl-immudellar ta' bosta problemi fil-"ħajja ta' kuljum" (jiġifieri li niltaqgħu magħhom barra l-matematikaMatematika, bħal dawk li għandhom x’jaqsmu ma' lmal-idea ta'[[xibka]] fl-informatika, xjenzi soċjali, problemi tat-traffiku u oħrajn).
 
== Definizzjoni ==
Linja 7:
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)<ref>Berge C., "Graphes et hypergraphes" Monographies Universitaires de Mathématiques, No. 37. Dunod, Pariġi, 1970. xviii+502 pp. (edizzjoni Ingliża, North-Holland 1973)</ref>, 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, immaperò infatti hija ekwivalenti: Berge iddefinixxa graf bħala tern<ref>Sett ta' tliet oġġetti</ref> <math>\displaystyle{(V, E, \phi)}</math> fejn <math>\displaystyle{\phi}</math> hi funzjoni <math>\displaystyle{\phi:E\rightarrow V\times V}</math>.
Il-vokabularju tat-teorija issellefssellef mill-ġeometrija tal-poliedri. Dawn jikkorrispondu ma' każ partikulari ta' graf fejn fit-tern <math>\displaystyle{(V, E, \phi)}</math>, <math>\displaystyle{V}</math> hu s-sett tal-vertiċi tal-poliedru, <math>\displaystyle{E}</math> ix-xfar tal-poliedru u <math>\displaystyle{\phi(e) = (u, v)}</math> jekk ix-xifer <math>\displaystyle{e}</math> jgħaqqad iż-żewġ vertiċi <math>\displaystyle{u}</math> u <math>\displaystyle{v}</math>. Dan il-vokabularju baqa' jintuża u għal graf ġenerali, <math>\displaystyle{V}</math> ngħidulu s-sett tal-"vertiċi" tiegħu, <math>\displaystyle{E}</math> is-sett tax-"xfar" tiegħu ("arki" jekk il-ġraf ikun orjentat) u <math>\displaystyle{\phi}</math> hi l-''funzjoni tal-inċidenza'' tiegħu li ma' kull xifer (ark) tassoċja par vertiċi.
 
=== Definizzjoni intwittiva ===
Linja 40:
==== Iżjed definizzjonijet ====
* L-'''ordni''' ta' graf huwa numru ta' vertiċi u d-'''daqs''' tiegħu huwa n-numru ta' xfar (jew arki) fih. Il-'''grad''' ta' vertiċi huwa n-numru ta' xfar (arki) mqabbdin miegħu.
:PereżempjuPer eżempju, il-graf fil-figura 1 għandu ordni 7 u daqs 6; il-vertiċi 2, 4 u 5 għandhom grad 3, il-vertiċi 1 u 3 għandhom grad 2 u l-vertiċi 6 għandha 1 bħala grad.
 
* Il-'''kumplament''' <math>\bar{G}</math> ta' graf <math>\displaystyle{G}</math> huwa graf bl-istess sett ta' vertiċi bħal <math>\displaystyle{G}</math>, immaperò s-sett ta' xfar tiegħu fih ix-xfar kollha possibbli (fuq dawn il-vertiċi) li mhumiex xfar ta' <math>\displaystyle{G}</math>.
:PereżempjuPer eżempju, il-kumplament tal-graf filfl-figuraewwel 1figura għandu xfar <math>\left\{ (1,3), (1,4), (1,6), (2,4), (2,6), (3,5), (3,6), (6,5) \right\}</math>.
* '''Sottograf''' ta' <math>\displaystyle{G}</math> hu graf li s-sett ta' vertiċi tiegħu hu sottosett tas-sett ta' vertiċi ta' ''G'', u li s-sett ta' xfar (arki) tiegħu hu sottosett tax-xfar (arki) ta' <math>\displaystyle{G}</math>. Jekk is-sottosett ta' xfar (arki) fih ix-xfar (arki) kollha ta' <math>\displaystyle{G}</math> li jgħaqqdu s-sottosett ta' vertiċi bejniethom, is-sottograf ngħidu li hu '''mnissel''' minn <math>\displaystyle{G}</math>.
:PereżempjuPer eżempju, jekk <math>V' = \left\{ 2, 3, 4, 5 \right\}</math> u <math>A' = \left\{ (2,3), (4,5), (4,3) \right\}</math>, il-graf <math>\displaystyle{G'=(V',A')}</math> hu sottograf tal-graf fil-figura 1. però mhux imissel, waqt li jekk <math>V'' = \left\{ 2, 3, 4, 5 \right\}</math> u <math>A'' = \left\{ (2,3), (4,5), (4,3), (5,2) \right\}</math>, il-graf <math>\displaystyle{G''=(V'',A'')}</math> hu sottograf imnissel tal-graf fil-figura 1.
:Jekk is-sett ta' vertiċi tas-sottograf hu l-istess bħas-sett ta' vertiċi ta' <math>\displaystyle{G}</math>, ngħidu li s-sottograf '''jgħatti''' 'l <math>\displaystyle{G}</math>' jew li hu graf '''għattej''' ta' <math>\displaystyle{G}</math>.
* '''Mogħdija''' fi graf hi sekwenza ta' vertiċi li għal kull vertiċi fiha hemm xifer minn din il-vertiċi għall-vertiċi li jmiss. Fi graf mhux orjentat <math>\displaystyle{G}</math>, żewġ vertiċi <math>\displaystyle{u}</math> and <math>\displaystyle{v}</math> ngħidulhom '''konnessi''' jekk <math>\displaystyle{G}</math> fih mogħdija minn <math>\displaystyle{u}</math> għal <math>\displaystyle{v}</math>. Inkella ngħidulhom '''skonnessi'''. Graf insejħulu '''konness''' jekk kull par ta' vertiċi distinti fil-graf hu konness. Mogħdija hi '''mnissla''' jekk hi sottograf imnissel. '''Ċiklu''' hu mogħdija magħluqa. Bl-istess mod ċiklu hu '''mnissel''' jekk hu sottograf imnissel.
Linja 53:
* Graf '''bipartit''' hu graf mhux orjentat li l-vertiċi tiegħu nistgħu naqsmuhom f’żewġ sottosettijiet b'mod li kull vertiċi f'sett wieħed hi mqabbda biss ma' vertiċi tas-sett l-ieħor.
* Graf ngħidulu '''regolari''' jekk il-vertiċi kollha għandhom l-istess numru ta' ġirien.
* Fi graf <math>\displaystyle{G=(V,A)}</math>, '''qbil''' <math>\displaystyle{Q}</math> f'<math>\displaystyle{G}</math> hu sett ta' xfar li l-ebda tnejn minnhom m'huma ġirien, jiġifieri l-ebda żewġ truf m'għandhom l-istess vertiċi. '''Qbil massimu''' hu qbil li fih l-ikbar numru ta' xfar possibbli. Jista' jkun hemm ħafna qbilijiet massimi. Graf ikollu '''qbil perfett''' jekk <math>\displaystyle{A}</math> stess hu qbil, jiġifieri jekk għall-kull par ta' vertiċi jkun hemm xifer bihom bħala truf u dan ix-xifer ma jkun inċidenti ma' lmal-ebda vertiċi ieħor.
* '''Għatja tal-vertiċi''' tal-graf <math>\displaystyle{G}</math> hu sottosett ta' vertiċi minn <math>\displaystyle{V}</math>, <math>\displaystyle{K}</math>, bil-propjetà li kull xifer ta' <math>\displaystyle{G}</math> hu inċidenti mill-inqas ma' vertiċi wieħed minn <math>\displaystyle{K}</math>. Għatja tal-vertiċi hija '''minima''' jekk m'hemm l-ebda għatja tal-vertiċi b'inqas vertiċi.
* '''Kulurazzjoni ta' graf''' jew '''tilwin ta' graf''' hu tqassim ta' tikketti, tradizzjonalment imsejħin "kuluri" jew "lwien", fuq il-vertiċi tal-graf b'mod li l-ebda żewġ ġirien ma jingħataw l-istess kulur. L-iżgħar numru ta' lwien meħtieġa biex niżbgħu graf <math>\displaystyle{G}</math> jgħidulu n-'''numru kromatiku''' tiegħu, <math>\displaystyle{\chi(G)}</math>.
Linja 72:
== Rappreżentazzjoni informali ==
 
Il-grafi orjentati nistgħu nirrappreżentawhom b’disinb’disinn, kif turi l-figura 2.
Fid-disinn nuru l-vertiċi b’tikek (jew ċrieki) u l-arki bi vleġeġ li jmorru mir-ras tal-ark għad-denb. Fil-grafi mhux orjentati, minflok vleġeg inpinġu linji bħal ma turi l-figura 1.
 
== Storja fil-qosor ==
 
1736: IrL-iżjed riżultat l-iżjed antik ukif forsiukoll l-iżjed magħruf li nistgħu ninkludu fit-teorija tal-grafi huhuwa l-karatterizzazzjoni tal-grafi Eulerjani minn [[Leonhard Euler|Euler]] fl-1736, li kellha bħala motivazzjoni kellha l-'''Problema tas-seba' pontijiet ta' Königsberg'''<ref>
Il-'''-problema tas-seba' pontijiet ta' Königsberg''' huhija problema ispiratispirata minn sitwazzjoni verareali. Ix-xmara Pregel u l-friegħi tagħha jifformaw żewġ gżejjer fil-belt ta' Königsberg. Dawn il-gżejjer huma magħqudin flimkien ukif ukoll mal-belt prinċipali b'seba' pontijiet. Kien hemm ilid-mistoqsijadomanda jekk huxhuwiex possiblipossibbli li wieħed jagħmel passiġġata billi jsegwi triq li taqsam kull pont darba u darba biss u jerġa' lura minn fejn beda. Fl-1736 [[Leonhard Euler]] studja l-problema u wera li din il-passiġġata mhux possibbli.</ref>.
 
1852: Francis Guthrie ippropona l-famuż '''problema ta' erba' kuluri'''<ref> It-'''teorema ta' erba’ kuluri''' jgħid li nistgħu niżbgħu kull mappa b'erba' kuluri biss mingħajr ma jkun hemm żewġ pajjiżi ġirien bl-istess kulur. Żewġ pajjiżi jitqisu ġirien jekk ikollhom mill-inqas segmentsezzjoni komuni tal-fruntiera. </ref> li s-soluzzjoni tiegħu instabetnstabet iżjed minn seklu wara. Dan ir-riżultat tant importanti, taha lit-teorija tal-grafi taha ċertu prestiġju. Il-vokabolarjuvokabularju stess tat-teorija tal-grafi ġej mir-riżoluzzjoni ta' dandin il-problema fejn jintużaw biss grafi imnisslinmnisslin minn poliedri biss.
 
1914: "Kull graf bipartit regolari għandu qbil perfett" (mħabbra minn König (ippublikata 1916)).
 
1927: '''It-teorema ta' Menger''', l-ewwel riżultat fuq il-konnettività fi graf, u, a posteriori, l-ewwel teorema min-mass:
:''Ħalli <math>\displaystyle{G}</math> jkun graf mhux orjentat finit u <math>\displaystyle{u}</math> u <math>\displaystyle{v}</math> żewġ vertiċi mhux ġirien. It-teorema jgħidtgħid li l-iżgħar numru ta' vertiċi li rridu nnaħħunneħħu biex niskonnettjaw <math>\displaystyle{u}</math> u <math>\displaystyle{v}</math> huhuwa daqs l-ikbar numru ta' mgħodijiet minn <math>\displaystyle{u}</math> għal <math>\displaystyle{v}</math> li m'għandhomx vertiċi komuni bejniethom.''
 
1931: '''It-teorema ta' König''':
Linja 103:
 
* '''Teorema qawwi tal-grafi pefetti''' :
:''Graph hu perfett jekk u biss jekk la hu u lanqas il-kumplament tiegħu ma fih ċiklu imnisselmnissel ta' tul '''fard''' inqas minn ħamsa.''
 
1972: László Lovász ipprova itt-Teorema dagħjefdgħajjef tal-grafi pefetti ta' Berge.
 
1976: '''It-teorema tal-erba' kuluri''' (riżoluzzjoni tal-problema li kien ippropona Guthrie miż-żewġ matematiċi Kenneth Appel u Wolfgang Haken).
Linja 131:
Nistgħu naħżnu graf fuq il-kompjuter bl-għajnuna ta' bosta strutturi differenti.
* Nistgħu ninnumeraw il-vertiċi, imbagħad nagħtu l-arki taħt forma ta' lista ta' koppji.
* Nistgħu nużaw il-'''matriċi tal-ġirien''', li fil-post <math>\displaystyle{(i,j)}</math>) tiegħu inpoġġunpoġġu 1 jekk u biss jekk hemm ark mill-vertiċi <math>\displaystyle{i}</math> għall-vertiċi <math>\displaystyle{j}</math>, inkella npoġġu 0. Fil-każ ta' graf mhux orjentat il-matriċi hu simmetriku. Dan il-metodu hu iżjed mgħaġel imma jieħu iżjed spazju fil-memorja.
* Ma' kull vertiċi nistgħu nassoċjaw '''lista tal-ġirien''', jiġifieri lista li fiha l-vertiċi kollha li jippuntaw lejhom ix-xfar li jibdew minnha.
 
Linja 137:
Il-grafi jintużaw għall-mudellar, fost oħrajn, ta' :
* Xibka stradali ta' pajjiż : kull belt hi vertiċi, kull triq bejn xewġt ibliet (jekk ma tgħaddix minn belt oħra), hihija in ġeneraliinġenerali żewġ arki, waħda f’kull direzzjoni jekk ma tkunx f’direzzjoni waħda biss li f'dak il-każ tkun ark wieħed.
* Xibka stradali ta' belt : kull fejn jiltaqgħu t-toroq huma vertiċivertikali, u kull sezzjoni tat-triq bejniethom hi żewġ arki jew ark wieħed skondskont tkunx f'żewġ direzzjonijiet jew f'waħda.
* Xibka tar-rotot tal-karozzi ta-linja, ferroviji, …
* Fl-analiżi tax-xbieki soċjali, il-grafi jippermettu d-deskrizzjoni tal-aspetti formali tagħhom biex wara ssir l-analiżi soċjoloġika<ref>Idea ta' Alain Degenne u Michel Forsé (1994): ''Les réseaux sociaux'' p. 75</ref>.
* Sit tal-[[Internet]] : kull paġna hi vertiċi, kull ħolqa ta' [[ipertest]] hu ark (mill-paġna li qegħda fih għall-paġna li tqabbad magħha).
* Ix-xibka tal-[[Internet]] stess hi graf fejn il-vertiċi huma s-servers u l-utenti, u x-xfar huma l-interkonnessjonijiet differenti.
* Ħafna sistemi diskreti :li minn ħin għall-ieħor jaqbsujaqbżu minn stat għall-ieħor b'mod diskontinwu, pereżempjuper eżempju, [[Awtomi bi stati finiti]] u [[Sistemi tat-tranżizzjoni tal-istati]].
* Fil-mekkanika tas-solidi, il-graf tal-fluss tal-enerġija huhija għodda utli għall-mudellarimmudellar ċinetiku tal-mekkaniżmi. Il-proprjetajiet tal-graf jista' jkollhom tifsira (numru ta' ċikli, klassi, etc.).
* Fl-elettronika, jirrapreżentaw iċ-ċirkwiti integrati.
* Xibka [[newronu|newrali]] nistgħu nirrappreżentawha bi graf orjentat fejn kull ark jkollu "valur" u kull vertiċi jkollu bħala valur, l-"għadba ta' aktivazzjoni" tiegħu.
Il-grafi jintużaw ħafna fl-informatika. Minħabba l-effiċjenza tagħhom fil-mudellar programmatiku ta' strutturi ta' data komplessa, niltaqgħu magħhom pereżempjuper eżempju fi :
* Il-[[baż ta' data|bażi ta' data]] : mudell relazzjonali ta' data nistgħu nirrappreżentawh bi graf orjentat, fejn ir-relazzjonijiet huma vertiċi tal-graf u d-dipendenzi huma l-arki. Insemmu speċjalment il-grafi semantiċi normalizzati għad-disinn ta’ skemi ta' data relazzjonali li tirriżulta mill-proċedura tan-normalizzazzjoni ;
* il-[[Web semantiku]] : ontoloġija hi sett ta' kunċetti (vertiċi ta' graf) u relazzjonijiet bejniethom (arki tal-graf) ;