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).

Werrej

1 Definizzjoni
- 1.1 Definizzjoni ta' Berge
- 1.2 Definizzjoni intwittiva
  - 1.2.1 Grafi
  - 1.2.2 Iżjed definizzjonijet
  - 1.2.3 Ipergrafi

2 Rappreżentazzjoni informali

3 Storja fil-qosor

4 Rappreżentazzjonijiet tal-grafi fl-informatika

5 Interess fid-"dinja ta' kuljum"

6 Noti u referenzi

7 Bibljografija

8 Ħoloq esterni

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 displaystyle (V,E,phi )$ fejn $displaystyle displaystyle phi$ hi funzjoni $displaystyle displaystyle phi :Erightarrow Vtimes V$ .
Il-vokabularju tat-teorija ssellef mill-ġeometrija tal-poliedri. Dawn jikkorrispondu ma' każ partikulari ta' graf fejn fit-tern $displaystyle displaystyle (V,E,phi )$ , $displaystyle displaystyle V$ hu s-sett tal-vertiċi tal-poliedru, $displaystyle displaystyle E$ ix-xfar tal-poliedru u $displaystyle displaystyle phi (e)=(u,v)$ jekk ix-xifer $displaystyle displaystyle e$ jgħaqqad iż-żewġ vertiċi $displaystyle displaystyle u$ u $displaystyle displaystyle v$ . Dan il-vokabularju baqa' jintuża u għal graf ġenerali, $displaystyle displaystyle V$ ngħidulu s-sett tal-"vertiċi" tiegħu, $displaystyle 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

displaystyle displaystyle G

hu par

displaystyle displaystyle (V,A)

, fejn :

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

$displaystyle 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
$displaystyle V=left1,2,3,4,5,6right$
u $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

displaystyle displaystyle G

hu par

displaystyle displaystyle (V,A)

, fejn :

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

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

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

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

Per eżempju, il-kumplament tal-graf fl-ewwel figura għandu xfar

displaystyle left(1,3),(1,4),(1,6),(2,4),(2,6),(3,5),(3,6),(6,5)right

.

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

Per eżempju, jekk

displaystyle V'=left2,3,4,5right

u

displaystyle A'=left(2,3),(4,5),(4,3)right

, il-graf

displaystyle displaystyle G'=(V',A')

hu sottograf tal-graf fil-figura 1. però mhux imissel, waqt li jekk

displaystyle V''=left2,3,4,5right

u

displaystyle A''=left(2,3),(4,5),(4,3),(5,2)right

, il-graf

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'

displaystyle displaystyle G

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

displaystyle displaystyle G

' jew li hu graf għattej ta'

displaystyle 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 displaystyle G$ , żewġ vertiċi $displaystyle displaystyle u$ and $displaystyle displaystyle v$ ngħidulhom konnessi jekk $displaystyle displaystyle G$ fih mogħdija minn $displaystyle displaystyle u$ għal $displaystyle 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 $displaystyle displaystyle G=(V,A)$ , qbil $displaystyle displaystyle Q$ f' $displaystyle 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 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 displaystyle G$ hu sottosett ta' vertiċi minn $displaystyle displaystyle V$ , $displaystyle displaystyle K$ , bil-propjetà li kull xifer ta' $displaystyle displaystyle G$ hu inċidenti mill-inqas ma' vertiċi wieħed minn $displaystyle 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 displaystyle G$ jgħidulu n-numru kromatiku tiegħu, $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 $displaystyle displaystyle omega (G)$ ta' graf $displaystyle displaystyle G$ hu n-numru ta' vertiċi fl-ikbar klikka f' $displaystyle 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 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:

displaystyle V=v_1,v_2,v_3,v_4,v_5,v_6,v_7

,

displaystyle E=e_1,e_2,e_3,e_4

displaystyle =v_1,v_2,v_3,v_2,v_3,

displaystyle 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 displaystyle H$ hu par $displaystyle displaystyle H=(V,A)$ fejn $displaystyle displaystyle V$ hu sett ta' vertiċi u $displaystyle displaystyle A$ hu sett ta' sottosettijiet ta' $displaystyle 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 displaystyle G$ jkun graf mhux orjentat finit u $displaystyle displaystyle u$ u $displaystyle 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 displaystyle u$ u $displaystyle displaystyle v$ huwa daqs l-ikbar numru ta' mgħodijiet minn $displaystyle displaystyle u$ għal $displaystyle 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 $displaystyle textrm P=textrm NPcap textrm co-NP$ fit- Teorija tal-komplessità. It-teorema jgħid hekk:

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

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

[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

搜尋此網誌

Arsthbt

Teorija tal-grafi

Werrej

Definizzjoni |

Definizzjoni ta' Berge |

Definizzjoni intwittiva |

Grafi |

Iżjed definizzjonijet |

Ipergrafi |

Rappreżentazzjoni informali |

Storja fil-qosor |

Rappreżentazzjonijiet tal-grafi fl-informatika |

Interess fid-"dinja ta' kuljum" |

Noti u referenzi |

Bibljografija |

Ħoloq esterni |

Menu ta' navigazzjoni

Għodda personali

Spazji tal-isem

Varjanti

Visti

Aktar

Fittex

Navigazzjoni

Komunità

Għodda

Ipprintja/esporta

F'proġetti oħra

B'lingwi oħrajn

Popular posts from this blog