Fig. 1: Graf mhux orjentat b'6 vertiċi u b'7t ixfar.

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)^[1], 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^[2](V,E,ϕ)displaystyle displaystyle (V,E,phi ) fejn ϕdisplaystyle displaystyle phi hi funzjoni ϕ:E→V×Vdisplaystyle displaystyle phi :Erightarrow Vtimes V.
Il-vokabularju tat-teorija ssellef mill-ġeometrija tal-poliedri. Dawn jikkorrispondu ma' każ partikulari ta' graf fejn fit-tern (V,E,ϕ)displaystyle displaystyle (V,E,phi ), Vdisplaystyle displaystyle V hu s-sett tal-vertiċi tal-poliedru, Edisplaystyle displaystyle E ix-xfar tal-poliedru u ϕ(e)=(u,v)displaystyle displaystyle phi (e)=(u,v) jekk ix-xifer edisplaystyle displaystyle e jgħaqqad iż-żewġ vertiċi udisplaystyle displaystyle u u vdisplaystyle displaystyle v. Dan il-vokabularju baqa' jintuża u għal graf ġenerali, Vdisplaystyle displaystyle V ngħidulu s-sett tal-"vertiċi" tiegħu, Edisplaystyle displaystyle E is-sett tax-"xfar" tiegħu ("arki" jekk il-ġraf ikun orjentat) u ϕdisplaystyle 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 Gdisplaystyle displaystyle G hu par (V,A)displaystyle displaystyle (V,A), fejn :

• 
  Vdisplaystyle displaystyle V hu sett li l-elementi tiegħu ngħidulhom vertiċi ;


• 
  Adisplaystyle 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=1,2,3,4,5,6displaystyle V=left1,2,3,4,5,6right
u A=(1,2),(2,3),(2,5),(4,5),(1,5),(4,3),(4,6)displaystyle A=left(1,2),(2,3),(2,5),(4,5),(1,5),(4,3),(4,6)right.

Fig. 2: Graf orjentat b'5 vertiċi u 6 arki li fosthom hemm ħolqa waħda.

Bl-istess mod nistgħu niddefinixxu l-grafi orjentati:

Graf orjentat Gdisplaystyle displaystyle G hu par (V,A)displaystyle displaystyle (V,A), fejn :

• 
  Vdisplaystyle displaystyle V hu sett li l-elementi tiegħu ngħidulhom vertiċi ;


• 
  Adisplaystyle displaystyle A hu sett ta' pari ordnati ta' vertiċi, msejħin arki.

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

Meta e=(u,v)∈Adisplaystyle displaystyle e=(u,v)in A, ngħidu li edisplaystyle displaystyle e u udisplaystyle displaystyle u huma inċidenti (l-istess għal edisplaystyle displaystyle e u vdisplaystyle displaystyle v), li udisplaystyle displaystyle u u vdisplaystyle displaystyle v huma ġirien u li ż-żewġ vertiċi huma t-truf ta' edisplaystyle displaystyle e. Żewġ xfar ngħidulhom ġirien jekk hemm vertiċi li t-tnejn huma inċidenti miegħu. Jekk il-graf ikun orjentat, udisplaystyle displaystyle u ngħidulu t-tarf tal-bidu jew ras ta' edisplaystyle displaystyle e u vdisplaystyle 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 n(n−1)/2displaystyle displaystyle n(n-1)/2 jekk mhux orjentat u n(n−1)displaystyle displaystyle n(n-1) jekk hu orjentat, fejn ndisplaystyle 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 (u,v)displaystyle displaystyle (u,v) u (v,u)displaystyle 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 G¯displaystyle bar G ta' graf Gdisplaystyle displaystyle G huwa graf bl-istess sett ta' vertiċi bħal Gdisplaystyle displaystyle G, però s-sett ta' xfar tiegħu fih ix-xfar kollha possibbli (fuq dawn il-vertiċi) li mhumiex xfar ta' Gdisplaystyle displaystyle G.

Per eżempju, il-kumplament tal-graf fl-ewwel figura għandu xfar (1,3),(1,4),(1,6),(2,4),(2,6),(3,5),(3,6),(6,5)displaystyle left(1,3),(1,4),(1,6),(2,4),(2,6),(3,5),(3,6),(6,5)right.

• 
  Sottograf ta' Gdisplaystyle 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' Gdisplaystyle displaystyle G. Jekk is-sottosett ta' xfar (arki) fih ix-xfar (arki) kollha ta' Gdisplaystyle displaystyle G li jgħaqqdu s-sottosett ta' vertiċi bejniethom, is-sottograf ngħidu li hu mnissel minn Gdisplaystyle displaystyle G.

Per eżempju, jekk V′=2,3,4,5displaystyle V'=left2,3,4,5right u A′=(2,3),(4,5),(4,3)displaystyle A'=left(2,3),(4,5),(4,3)right, il-graf G′=(V′,A′)displaystyle displaystyle G'=(V',A') hu sottograf tal-graf fil-figura 1. però mhux imissel, waqt li jekk V″=2,3,4,5displaystyle V''=left2,3,4,5right u A″=(2,3),(4,5),(4,3),(5,2)displaystyle A''=left(2,3),(4,5),(4,3),(5,2)right, il-graf G″=(V″,A″)displaystyle displaystyle G''=(V'',A'') 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' Gdisplaystyle displaystyle G, ngħidu li s-sottograf jgħatti 'l Gdisplaystyle displaystyle G' jew li hu graf għattej ta' Gdisplaystyle displaystyle G.

• 
  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 Gdisplaystyle displaystyle G, żewġ vertiċi udisplaystyle displaystyle u and vdisplaystyle displaystyle v ngħidulhom konnessi jekk Gdisplaystyle displaystyle G fih mogħdija minn udisplaystyle displaystyle u għal vdisplaystyle displaystyle v. 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.

Fig. 3: Siġra b'6 vertiċi u 5 xfar

• 
  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 G=(V,A)displaystyle displaystyle G=(V,A), qbil Qdisplaystyle displaystyle Q f'Gdisplaystyle displaystyle G 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 Adisplaystyle displaystyle A 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 Gdisplaystyle displaystyle G hu sottosett ta' vertiċi minn Vdisplaystyle displaystyle V, Kdisplaystyle displaystyle K, bil-propjetà li kull xifer ta' Gdisplaystyle displaystyle G hu inċidenti mill-inqas ma' vertiċi wieħed minn Kdisplaystyle displaystyle K. 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 Gdisplaystyle displaystyle G jgħidulu n-numru kromatiku tiegħu, χ(G)displaystyle displaystyle chi (G).


• 
  Klikka fi graf hu sett ta' vertiċi fih, li kull tnejn minnhom huma ġirien ta' xulxin. In-numru tal-klikka ω(G)displaystyle displaystyle omega (G) ta' graf Gdisplaystyle displaystyle G hu n-numru ta' vertiċi fl-ikbar klikka f' Gdisplaystyle displaystyle G.


• 
  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 Adisplaystyle displaystyle A hu sett ta' familji ta' pari ta' vertiċi (ordnati jew mhux ordnati skont il-każ).

Ipergrafi |

Fig. 4: Eżempju ta' ipergraf: V=v1,v2,v3,v4,v5,v6,v7displaystyle V=v_1,v_2,v_3,v_4,v_5,v_6,v_7, E=e1,e2,e3,e4displaystyle E=e_1,e_2,e_3,e_4 =v1,v2,v3,v2,v3,displaystyle =v_1,v_2,v_3,v_2,v_3, v3,v5,v6,v4displaystyle v_3,v_5,v_6,v_4.

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 Hdisplaystyle displaystyle H hu par H=(V,A)displaystyle displaystyle H=(V,A) fejn Vdisplaystyle displaystyle V hu sett ta' vertiċi u Adisplaystyle displaystyle A hu sett ta' sottosettijiet ta' Vdisplaystyle displaystyle V 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 Euler fl-1736, li bħala motivazzjoni kellha l-Problema tas-seba' pontijiet ta' Königsberg^[3].

1852: Francis Guthrie ippropona l-famuż problema ta' erba' kuluri^[4] 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 Gdisplaystyle displaystyle G jkun graf mhux orjentat finit u udisplaystyle displaystyle u u vdisplaystyle displaystyle v żewġ vertiċi mhux ġirien. It-teorema tgħid li l-iżgħar numru ta' vertiċi li rridu nneħħu biex niskonnettjaw udisplaystyle displaystyle u u vdisplaystyle displaystyle v huwa daqs l-ikbar numru ta' mgħodijiet minn udisplaystyle displaystyle u għal vdisplaystyle displaystyle v 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 P=NP∩co-NPdisplaystyle textrm P=textrm NPcap textrm co-NP fit- Teorija tal-komplessità. It-teorema jgħid hekk:

Graf bipartit G=(U,V;A)displaystyle displaystyle G=(U,V;A), masqum f' Udisplaystyle displaystyle U u Vdisplaystyle displaystyle V, għandu qbil perfett jekk u biss jekk għal kull sottosett Xdisplaystyle displaystyle X ta' Udisplaystyle displaystyle U (rispettivament ta' Vdisplaystyle displaystyle V), in-numru ta' vertiċi f' Vdisplaystyle displaystyle V (rispettivament f' Udisplaystyle displaystyle U) li huma ġirien ma' xi vertiċi f'Xdisplaystyle displaystyle X hu ikbar jew daqs il-kardinalità ta' Xdisplaystyle displaystyle X.

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 |

Graf mhux orjentat	Matriċi tal-ġirien
	(110010101010010100001011110100000100)displaystyle beginpmatrix1&1&0&0&1&0\1&0&1&0&1&0\0&1&0&1&0&0\0&0&1&0&1&1\1&1&0&1&0&0\0&0&0&1&0&0\endpmatrix

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 (i,j)displaystyle displaystyle (i,j)) tiegħu npoġġu 1 jekk u biss jekk hemm ark mill-vertiċi idisplaystyle displaystyle i għall-vertiċi jdisplaystyle displaystyle j, 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^[5].


• 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 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ż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 |

Bibljografija |

• K. Thulasiraman, M. N. S. Swamy (1992): Graphs: Theory and Algorithms, J.Wiley


• Bêla Bollobás (1998): Modern Graph Theory, Springer, ISBN 0-387-98841-7
  


• 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 |

Wikimedia Commons għandha fajls multimedjali li għandhom x'jaqsmu ma': Teorija tal-grafi

Portal Matematika

• (EN) Graph Theory with Applications (1976) ta' Bondy and Murty


• (FR) Kors tat-teorija tal-grafi ta' Marc Beveraggi (INSA Rouen)
  


• (FR) Théorie des Graphes Kors tat-teorija tal-grafi


• (FR) Kors interattiv tal-Ensem fuq it-teorija tal-grafi
  


• (FR) Kors tal-Polytechnique
  


• (FR) Kors tal-ESIEE
  


• (EN) Diestel - Graph Theory, Electronic Edition
  


• (IT) Teorija tal-Grafi 1.0 - Desmatron
  


• (IT) Teorija tal-Grafi - Appunti
  


• (EN) Graph Theory Software