Teorija tal-grafi: Differenza bejn il-verżjonijiet
Content deleted Content added
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-
== 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,
Il-vokabularju tat-teorija
=== 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.
:
* 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>,
:
* '''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>.
:
: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
* '''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
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:
Il-'''-problema tas-seba' pontijiet ta' Königsberg'''
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
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
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
1972: László Lovász ipprova
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
* 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),
* Xibka stradali ta' belt : kull fejn jiltaqgħu t-toroq huma
* 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
* Fil-mekkanika tas-solidi, il-graf tal-fluss tal-enerġija
* 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
* 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) ;
|