Teorija tal-grafi

Fil-matematika t-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 huwa utli ħafna fl-immudellar 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 mal-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, però 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 ssellef 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.

### Definizzjoni intwittiva
#### Grafi
Hawn nagħtu definizzjoni iżjed intwittiva (b’formaliżmu inqas tqil minn dak tas-snin 60). Il-grafi mhux orjentati nistgħu niddefinuhom hekk :
: **Graf mhux orjentat** \displaystyle{G} hu par \displaystyle{(V,A)}, fejn :
:* \displaystyle{V} hu sett li l-elementi tiegħu ngħidulhom **vertiċi** ; 
:* \displaystyle{A} hu sett ta' *pari* (mhux ordnati) ta' vertiċi, msejħin **xfar**.
Għall-graf fil-figura 1 murija iżjed 'il fuq, għandna 
V = \left\{ 1, 2, 3, 4, 5, 6 \right\} 
u A = \left\{ (1,2), (2,3), (2,5), (4,5), (1,5), (4,3), (4,6) \right\}.

Bl-istess mod nistgħu niddefinixxu l-grafi orjentati:
: **Graf orjentat** \displaystyle{G} hu par \displaystyle{(V,A)}, fejn :
:* \displaystyle{V} hu sett li l-elementi tiegħu ngħidulhom **vertiċi** ; 
:* \displaystyle{A} hu sett ta' *pari ordnati* ta' vertiċi, msejħin **arki**. 

Għall-graf fil-figura 2 murija hawn, għandna 
V = \left\{ 1, 2, 3, 4, 5 \right\} 
u A = \left\{ (1,2), (2,3), (3,1), (2,5), (4,5), (5,5) \right\}.

Meta \displaystyle{e = (u, v)\in A}, ngħidu li \displaystyle{e} u \displaystyle{u} huma **inċidenti** (l-istess għal \displaystyle{e} u \displaystyle{v}), li \displaystyle{u} u \displaystyle{v} huma **ġirien** u li ż-żewġ vertiċi huma t-**truf** ta' \displaystyle{e}. Żewġ xfar ngħidulhom ġirien jekk hemm vertiċi li t-tnejn huma inċidenti miegħu. Jekk il-graf ikun orjentat, \displaystyle{u} ngħidulu t-**tarf tal-bidu** jew **ras** ta' \displaystyle{e} u \displaystyle{v} t-**tarf tal-aħħar** jew **denb** (fil-każ li mhux orjentat il-vertiċi ngħidulhom sempliċiment truf u m'hemmx bżonn inkunu iżjed eżatti). Fil-grafi orjentati, żewġ xfar ngħidulhom **konsekuttivi** jekk huma ġirien u t-tarf komuni tagħhom huwa r-ras għal wieħed mill-arki u d-denb għall-ieħor. Xifer (ark) ngħidulu **ħolqa** jekk iż-żewġ truf tiegħu huma l-istess. Graf ngħidulu **sempliċi** jekk m'għandu l-ebda ħolqa u l-ebda żewġ xfar bl-istess truf. 

Minn hawn l-isfel f'dan l-artiklu nassumu li l-grafi huma sempliċi.

L-ikbar numru ta' xfar ta' graf sempliċi allura hu \displaystyle{n(n-1)/2} jekk mhux orjentat u \displaystyle{n(n-1)} jekk hu orjentat, fejn \displaystyle{n} hu n-numru ta' vertiċi. Dawn il-grafi jikkorrispondu mar-relazzjonijiet binarji mhux riflessivi.
Il-grafi sempliċi orjentati mingħajr pari t'arki tal-forma \displaystyle{(u, v)} u \displaystyle{(v, u)} jikkorrispondu mar-relazzjonijiet binarji mhux riflessivi
u antisimmetriċi.

#### 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.
:Per 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** \bar{G} ta' graf \displaystyle{G} huwa graf bl-istess sett ta' vertiċi bħal \displaystyle{G}, però s-sett ta' xfar tiegħu fih ix-xfar kollha possibbli (fuq dawn il-vertiċi) li mhumiex xfar ta' \displaystyle{G}.
:Per eżempju, il-kumplament tal-graf fl-ewwel figura għandu xfar \left\{ (1,3), (1,4), (1,6), (2,4), (2,6), (3,5), (3,6), (6,5) \right\}.
* **Sottograf** ta' \displaystyle{G} 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' \displaystyle{G}. Jekk is-sottosett ta' xfar (arki) fih ix-xfar (arki) kollha ta' \displaystyle{G} li jgħaqqdu s-sottosett ta' vertiċi bejniethom, is-sottograf ngħidu li hu **mnissel** minn \displaystyle{G}. 
:Per eżempju, jekk V' = \left\{ 2, 3, 4, 5 \right\} u A' = \left\{ (2,3), (4,5), (4,3) \right\}, il-graf \displaystyle{G'=(V',A')} hu sottograf tal-graf fil-figura 1. però mhux imissel, waqt li jekk V* = \left\{ 2, 3, 4, 5 \right\}</math> u <math>A* = \left\{ (2,3), (4,5), (4,3), (5,2) \right\}, il-graf \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. 
* Graf insejħulu **Eulerjan** jekk hu konness u kull vertiċi għandha grad 2.

* **Siġra** hi graf konness li ma fih l-ebda ċiklu magħluq li ma jaqsamx lilu nfisu.
* 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 mal-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>.
* **Klikka** fi graf hu sett ta' vertiċi fih, li kull tnejn minnhom huma ġirien ta' xulxin. In-**numru tal-klikka** <math>\displaystyle{\omega(G)}</math> ta' graf <math>\displaystyle{G}</math> hu n-numru ta' vertiċi fl-ikbar klikka f' <math>\displaystyle{G}</math>. 
* **Graf perfett** hu graf li għal kull sottograf imnissel minnu, in-numru kromatiku hu daqs in-numru tal-klikka ta' dak is-sottograf. 

Għal grafi iżjed ġenerali (mhux bilfors sempliċi) nissostitwixxu l-arki jew xfar b’familji ta’ arki jew xfar, jiġifieri <math>\displaystyle{A}</math> hu sett ta' familji ta' ''pari'' ta' vertiċi (ordnati jew mhux ordnati skont il-każ).

==== Ipergrafi ====

**Ipergraf** hu ġeneralizzazzjoni ta' graf fis-sens li l-ixfar jistgħu jgħaqqdu kwalunkwe għadd ta' vertiċi mhux tnejn biss. Formalment, ipergraf mhux orjentat <math>\displaystyle{H}</math> hu par <math>\displaystyle{H = (V,A)}</math> fejn <math>\displaystyle{V}</math> hu sett ta' vertiċi u <math>\displaystyle{A}</math> hu sett ta' sottosettijiet ta' <math>\displaystyle{V}</math> mhux vojta li nsejħulhom **iperxfar**. Waqt li l-ixfar ta' graf huma pari ta' vertiċi, l-iperxfar hu sett arbitrarju ta' vertiċi u għalhekk jista' jkun hemm fih numru arbitraru ta' vertiċi. Ċerti kunċetti (bħal konnettività) ma jintrasferrux tajjeb għall-ipergrafi u agħar għall-ipergrafi orjentati.

== Rappreżentazzjoni informali ==

Il-grafi orjentati nistgħu nirrappreżentawhom b’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: L-iżjed riżultat antik kif ukoll l-iżjed magħruf li nistgħu ninkludu fit-teorija tal-grafi huwa l-karatterizzazzjoni tal-grafi Eulerjani minn [[Leonhard Euler|Euler]] fl-1736, li bħala motivazzjoni kellha l-**Problema tas-seba' pontijiet ta' Königsberg**.

1852: Francis Guthrie ippropona l-famuż **problema ta' erba' kuluri** li s-soluzzjoni tiegħu nstabet iżjed minn seklu wara. Dan ir-riżultat tant importanti, taha lit-teorija tal-grafi ċertu prestiġju. Il-vokabularju stess tat-teorija tal-grafi ġej mir-riżoluzzjoni ta' din il-problema fejn jintużaw grafi mnisslin 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 tgħid li l-iżgħar numru ta' vertiċi li rridu nneħħu biex niskonnettjaw <math>\displaystyle{u}</math> u <math>\displaystyle{v}</math> huwa 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**:
:''Fi graf bipartit, in-numru ta' xfar fi qbil massimu hu daqs in-numru ta' vertiċi f'għatja minima tal-vertiċi.''

1935: **It-teorema ta' Hall** (iġġeneralizzat minn Tutte u wara minn Tutte-Berge) fuq il-qbilijiet perfetti fil-grafi bipartiti. Dan ir-riżultat kien il-bidu tal-klassi "co-NP", u wara flimkien mal-algoritmu tal-qbil perfett ta' Edmonds kien il-bidu tal-konġettura <math> \textrm{P} = \textrm{NP}\cap \textrm{co-NP}</math> fit- [[Teorija tal-komplessità]]. It-teorema jgħid hekk:
:''Graf bipartit <math>\displaystyle{G=(U,V;A)}</math>, masqum f' <math>\displaystyle{U}</math> u <math>\displaystyle{V}</math>, għandu qbil perfett jekk u biss jekk għal kull sottosett <math>\displaystyle{X}</math> ta' <math>\displaystyle{U}</math> (rispettivament ta' <math>\displaystyle{V}</math>), in-numru ta' vertiċi f' <math>\displaystyle{V}</math> (rispettivament f' <math>\displaystyle{U}</math>) li huma ġirien ma' xi vertiċi f'<math>\displaystyle{X}</math> hu ikbar jew daqs il-kardinalità ta' <math>\displaystyle{X}</math>.''

1956: Din kienet sena imporanti ħafna. Kienet is-sena tat-**Teorema kurrent-massimu/qtugħ-minimu** li ġġeneralizzat it-teoremi ta' Menger, ta' König u ta' Hall, u kienet il-bidu tal-[[programmazzjoni linjari]]. Kienet ukoll is-sena tal-algoritmu ta' Kruskal, l-ewwel **algoritmu żaqqieq** għall-grafi. Dan ir-riżultat welled mill-ġdid it-teorija tal-matrojdi li Tutte rabat mat-teorija tal-grafi.

1960: **Il-konġetturi ta' Berge**
Berge ippropona żewġ konġetturi li jikkaratterizzaw il-grafi perfetti,
élevées au rang de théorèmes depuis leur démonstration : 

* **Teorema dagħjef tal-grafi pefetti** : 
:''Graph hu perfett jekk u biss jekk il-kumplament tiegħu hu perfett.'' 

* **Teorema qawwi tal-grafi pefetti** : 
:''Graph hu perfett jekk u biss jekk la hu u lanqas il-kumplament tiegħu ma fih ċiklu mnissel ta' tul **fard** inqas minn ħamsa.'' 

1972: László Lovász ipprova t-Teorema dgħ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).

2002: Maria Chudnovsky, Neil Robertson, Paul D. Seymour u Robin Thomas ipprovaw it-Teorema qawwija tal-grafi pefetti ta' Berge.

Fit-tieni nofs tas-seklu XX, it-teorija tal-grafi bdiet tinteraġixxi ma’ bosta oqsma oħra.
Wara l-gwerra, il-problemi tal-kurrenti fil-grafi wasslu għall-programmazzjoni linjari u l-algoritmu tas-simpless. Il-problemi tas-**siġar għattejja** wasslu għall-ġeneralizzazzjoni tal-kunċett ta' graf għall-dak tal-matrojdi u għall-ħafna analoġiji bejn iż-żewġ teoriji, l-iżjed fil-qasam algoritmiku (dan influwenza l-vokabularju taż-żewġ teoriji).

== Rappreżentazzjonijiet tal-grafi fl-informatika ==

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 npoġġ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.

== Interess fid-"dinja ta' kuljum" ==
 
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), hija inġ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 vertikali, u kull sezzjoni tat-triq bejniethom hi żewġ arki jew ark wieħed skont 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.
* Sit tal-[[Internet]] : kull paġna hi vertiċi, kull ħolqa ta' [[ipertest]] hu ark (mill-paġna li qiegħ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 jaqbżu minn stat għall-ieħor b'mod diskontinwu, per eżempju, [[Awtomi bi stati finiti]] u [[Sistemi tat-tranżizzjoni tal-istati]].
* Fil-mekkanika tas-solidi, il-graf tal-fluss tal-enerġija hija għodda utli għall-immudellar ċ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 per 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) ;
* Il-[[kalkulu parallel]] : It-teniki tal-ottimazzjoni tal-algoritmi jew id-determinazzjoni tal-ordni tat-twettieq koerenti f'dan il-qasam (xi kmandi jridu jitwettqu wara l-oħrajn ; xi data tirid tiġi kalkulata wara oħra) sikwit jużaw grafi tad-dipendenza tal-fluss tal-kmandi fejn il-vertiċi huma respettivament kmandi (il-kodiċi tat-twettieq) u data (inizjali jew kalkulata) u l-arki huma relazzjonijiet ta' dipendenza temporali.

== Noti u referenzi ==

== Biblijografija ==
* K. Thulasiraman, M. N. S. Swamy (1992): *Graphs: Theory and Algorithms*, J.Wiley
* Bêla Bollobás (1998): *Modern Graph Theory*, Springer, 
* Lowell W. Beineke, Robin J. Wilson, Peter J. Cameron, eds (2004): *Topics in Algebraic Graph Theory*, Cambridge University Press
* D. Cvetković, P. Rowlison, S. Simic' (1997): *Eigenspaces of Graphs*, Cambridge University Press
* S. Fiorini u R. J. Wilson (1977): *Edge-colourings of graphs'' (Research notes in mathematics  16), Pitman

## Ħoloq esterni

*  Graph Theory with Applications (1976) ta' Bondy and Murty
*  Kors tat-teorija tal-grafi ta' Marc Beveraggi (INSA Rouen)
*  Théorie des Graphes Kors tat-teorija tal-grafi
*  Kors interattiv tal-Ensem fuq it-teorija tal-grafi
*  Kors tal-Polytechnique
*  Kors tal-ESIEE
*  Diestel - Graph Theory, Electronic Edition
*  Teorija tal-Grafi 1.0 - Desmatron
*  Teorija tal-Grafi - Appunti
*  Graph Theory Software