Teorija tal-grafi

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] $\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\}

u

A''=\left\{(2,3),(4,5),(4,3),(5,2)\right\}

, il-graf

\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'

\displaystyle {G}

, ngħidu li s-sottograf jgħatti 'l

\displaystyle {G}

' jew li hu graf għattej ta'

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

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 $\displaystyle {G=(V,A)}$ , qbil $\displaystyle {Q}$ f' $\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 $\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 $\displaystyle {G}$ hu sottosett ta' vertiċi minn $\displaystyle {V}$ , $\displaystyle {K}$ , bil-propjetà li kull xifer ta' $\displaystyle {G}$ hu inċidenti mill-inqas ma' vertiċi wieħed minn $\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 $\displaystyle {G}$ jgħidulu n-numru kromatiku tiegħu, $\displaystyle {\chi (G)}$ .
Klikka fi graf hu sett ta' vertiċi fih, li kull tnejn minnhom huma ġirien ta' xulxin. In-numru tal-klikka $\displaystyle {\omega (G)}$ ta' graf $\displaystyle {G}$ hu n-numru ta' vertiċi fl-ikbar klikka f' $\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 $\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=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}\}$ , $E=\{e_{1},e_{2},e_{3},e_{4}\}$ $=\{\{v_{1},v_{2},v_{3}\},\{v_{2},v_{3}\},$ $\{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 $\displaystyle {H}$ hu par $\displaystyle {H=(V,A)}$ fejn $\displaystyle {V}$ hu sett ta' vertiċi u $\displaystyle {A}$ hu sett ta' sottosettijiet ta' $\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 $\displaystyle {G}$ jkun graf mhux orjentat finit u $\displaystyle {u}$ u $\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 $\displaystyle {u}$ u $\displaystyle {v}$ huwa daqs l-ikbar numru ta' mgħodijiet minn $\displaystyle {u}$ għal $\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 ${\textrm {P}}={\textrm {NP}}\cap {\textrm {co-NP}}$ fit- Teorija tal-komplessità. It-teorema jgħid hekk:

Graf bipartit $\displaystyle {G=(U,V;A)}$ , masqum f' $\displaystyle {U}$ u $\displaystyle {V}$ , għandu qbil perfett jekk u biss jekk għal kull sottosett $\displaystyle {X}$ ta' $\displaystyle {U}$ (rispettivament ta' $\displaystyle {V}$ ), in-numru ta' vertiċi f' $\displaystyle {V}$ (rispettivament f' $\displaystyle {U}$ ) li huma ġirien ma' xi vertiċi f' $\displaystyle {X}$ hu ikbar jew daqs il-kardinalità ta' $\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
	${\begin{pmatrix}1&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\\\end{pmatrix}}$

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 $\displaystyle {(i,j)}$ ) tiegħu npoġġu 1 jekk u biss jekk hemm ark mill-vertiċi $\displaystyle {i}$ għall-vertiċi $\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

^ 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)
^ Sett ta' tliet oġġetti
^ Il--problema tas-seba' pontijiet ta' Königsberg hija problema ispirata minn sitwazzjoni reali. 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 kif ukoll mal-belt prinċipali b'seba' pontijiet. Kien hemm id-domanda jekk huwiex possibbli 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.
^ 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 sezzjoni komuni tal-fruntiera.
^ Idea ta' Alain Degenne u Michel Forsé (1994): Les réseaux sociaux p. 75

Biblijografija

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^{[ISBN invalidu]}
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

[1] 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)

[2] Sett ta' tliet oġġetti

[3] Il--problema tas-seba' pontijiet ta' Königsberg hija problema ispirata minn sitwazzjoni reali. 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 kif ukoll mal-belt prinċipali b'seba' pontijiet. Kien hemm id-domanda jekk huwiex possibbli 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.

[4] 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 sezzjoni komuni tal-fruntiera.

[5] Idea ta' Alain Degenne u Michel Forsé (1994): Les réseaux sociaux p. 75

[1]

[2]

[3]

[4]

[5]