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). 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 formula_1 fejn formula_2 hi funzjoni formula_3. Il-vokabularju tat-teorija ssellef mill-ġeometrija tal-poliedri. Dawn jikkorrispondu ma' każ partikulari ta' graf fejn fit-tern formula_1, formula_5 hu s-sett tal-vertiċi tal-poliedru, formula_6 ix-xfar tal-poliedru u formula_7 jekk ix-xifer formula_8 jgħaqqad iż-żewġ vertiċi formula_9 u formula_10. Dan il-vokabularju baqa' jintuża u għal graf ġenerali, formula_5 ngħidulu s-sett tal-"vertiċi" tiegħu, formula_6 is-sett tax-"xfar" tiegħu ("arki" jekk il-ġraf ikun orjentat) u formula_2 hi l-"funzjoni tal-inċidenza" tiegħu li ma' kull xifer (ark) tassoċja par vertiċi. 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 : Għall-graf fil-figura 1 murija iżjed 'il fuq, għandna formula_18 u formula_19. Bl-istess mod nistgħu niddefinixxu l-grafi orjentati: Għall-graf fil-figura 2 murija hawn, għandna formula_24 u formula_25. Meta formula_26, ngħidu li formula_8 u formula_9 huma inċidenti (l-istess għal formula_8 u formula_10), li formula_9 u formula_10 huma ġirien u li ż-żewġ vertiċi huma t-truf ta' formula_8. Żewġ xfar ngħidulhom ġirien jekk hemm vertiċi li t-tnejn huma inċidenti miegħu. Jekk il-graf ikun orjentat, formula_9 ngħidulu t-tarf tal-bidu jew ras ta' formula_8 u formula_10 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 formula_37 jekk mhux orjentat u formula_38 jekk hu orjentat, fejn formula_39 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 formula_40 u formula_41 jikkorrispondu mar-relazzjonijiet binarji mhux riflessivi u antisimmetriċi. Għal grafi iżjed ġenerali (mhux bilfors sempliċi) nissostitwixxu l-arki jew xfar b'familji ta' arki jew xfar, jiġifieri formula_17 hu sett ta' familji ta' "pari" ta' vertiċi (ordnati jew mhux ordnati skont il-każ). 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 formula_81 hu par formula_82 fejn formula_5 hu sett ta' vertiċi u formula_17 hu sett ta' sottosettijiet ta' formula_5 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. 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. 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. 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: 1931: It-teorema ta' König: 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 formula_93 fit- Teorija tal-komplessità. It-teorema jgħid hekk: 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 : 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). Nistgħu naħżnu graf fuq il-kompjuter bl-għajnuna ta' bosta strutturi differenti. Il-grafi jintużaw għall-mudellar, fost oħrajn, ta' : 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 :