Теорија графова

Теорија графова је област математике, веома заступљена и у информатици, чија је област истраживање особина графова. Неформално говорећи, графови су састављени од тачака, односно чворова (врхова), и линија међу њима, односно грана.

Веома је честа употреба графова за опис модела или структура података. Структура једне веб презентације се може представити сликовито употребом графа. Чворови тог графа су поједине странице а гране графа су везе којима се може са једне странице прелазити на другу.

Проучавање алгоритама који решавају проблеме употребом графова представља веома значајан део информатичке науке. Мреже имају много примена у проучавању практичних аспеката теорије графова и то се зове анализа мрежа. Анализа мрежа је посебно значајна за проблеме моделирања и анализирање мрежног саобраћаја, рецимо интернета.

Особине

Ако се може сматрати да је грана која спаја чворове А и Б исто што и грана која спаја чворове Б и А, онда је граф неусмерен. Ако се пак сматра да су то две различите гране онда је граф усмерен.^[1]^[2]

Појам графа може бити проширен додавањем особине тежине свакој грани. Овакви графови се зову тежински графови и они су згодни за представљање неких проблема, на пример мреже путева где се тежина односи на дужину пута између два чвора. Тежински граф који је усмерен зове се мрежа.

Две (или више) гране графа су паралелне ако спајају два иста темена. Грана може да спаја врх са самим собом, и тада се назива петљом. Граф који нема петље нити паралелне гране се назива простим графом. Граф је празан ако нема ниједну грану, а нулти граф нема ниједан врх.

Степен чвора v_i=d(v_i) је једнак броју грана које улазе/излазе из њега, с тим да се петља рачуна као две гране. Тотални степен графа је збир свих степени графа, и једнак је двоструком броју грана. Није могуће нацртати граф са непарним степеном.

Граф G'=(V',E') је подграф графа G=(V, E) ако је скуп његових чворова (V') подскуп скупа чворова графа G (V), а скуп његових грана (E') је подскуп скупа грана вектора G (E). Ако је овим графовима скуп чворова једнак, онда се граф G' назива разапињујућим графом, или скелетом.

Комплетан граф, прост граф, и његов комплемент

Ако је степен сваког чвора исти, онда је граф регуларан. Комплетан граф је прост граф, код кога су свака два чвора спојена граном.

Изоморфни и неизоморфни графови

Два графа, G₁, и G₂ су изоморфна ако и само ако постоји „1-1“ и „на“ пресликавање врхова и грана, тако да се очувава суседност свих врхова, тј. да су везе између врхова начињене на аналоган начин. Изоморфни графови су од великог значаја у електроници, при конструисању штампаних кола, где гране графа (струјни водови) не смеју да се секу осим у чворовима. Зато је битно да се пронађе изоморфан граф жељеном графу, али такав да му се гране не секу.

Историја

Први проблем и његово решење изнесени на начин који је другачији у односу на претходне и може се сматрати претечом теорије графова јесте рад Леонарда Ојлера под називом Седам мостова Кенигсберга, објављен 1736. Ово је први резултат из области топологије у геометрији; што ће рећи не зависи од неке мере односно величине. Ово приказује дубоке везе између теорије графова и топологије.

Густав Кирхоф је 1845. године објавио нешто што је касније названо Кирхофов закон, а односило се на проблем рачуна напона и струје у електричном колу.

Френсис Гутри је 1852. године је изложио проблем четири боје који поставља питање да ли је могуће обојити земље на географској карти са само четири боје, а да се не појаве две суседне земље обојене истом бојом. Овај проблем су решили тек 1976. године Кенет Апел и Волфганг Хекен, али се постављање овог проблема сматра рођењем теорије графова. Током покушаја решавања овог проблема откривене су многе теореме и постављени многи теоретски појмови и концепти.

Апликације

Мрежни граф који су формирали уредници Википедије (ивице) који су допринели различитим језичким верзијама Википедије (врховима) током једног месеца лета 2013.^[3]

Графови се могу користити за моделовање многих типова односа и процеса у физичким, биолошким,^[4]^[5] друштвеним и информационим системима.^[6] Многи практични проблеми могу бити представљени графиконима. Наглашавајући њихову примену на системе у стварном свету, термин мрежа се понекад дефинише да означава граф у коме су атрибути (нпр. имена) повезани са врховима и ивицама, а субјект који изражава и разуме системе у стварном свету као мрежу се назива наука о мрежи.

Информатика

У оквиру рачунарске науке, узрочне и некаузалне повезане структуре су графови који се користе за представљање мрежа комуникације, организације података, рачунарских уређаја, тока рачунања, итд. На пример, граф у коме врхови представљају веб странице, а усмерене ивице представљају везе са једне странице на другу. Сличан приступ се може применити на проблеме у друштвеним медијима,^[7] путовању, биологији, дизајну компјутерских чипова, мапирању прогресије неуро-дегенеративних болести,^[8]^[9] и многим другим пољима. Стога је развој алгоритама за руковање графовима од великог интереса у рачунарској науци. Трансформација графова је често формализована и представљена системима за преписивање графова. Комплементарни системима трансформације графова који се фокусирају на манипулацију графовима у меморији заснованој на правилима су базе података графова усмерене на безбедне трансакције, перзистентно складиштење и испитивање графно структурираних података.

Физика и хемија

Теорија графова се такође користи за проучавање молекула у хемији и физици. У физици кондензоване материје, тродимензионална структура компликованих симулираних атомских структура може се квантитативно проучавати прикупљањем статистичких података о графно теоретским својствима у вези са топологијом атома. Такође, „Фејнманови графови и правила израчунавања сумирају квантну теорију поља у облику у блиском контакту са експерименталним бројевима које неко жели да разуме.“^[10] У хемији граф чини природни модел за молекул, где врхови представљају атоме и ивице везе. Овај приступ се посебно користи у компјутерској обради молекуларних структура, у распону од хемијских едитора до претраживања базе података. У статистичкој физици, графови могу представљати локалне везе између делова система у интеракцији, као и динамику физичког процеса на таквим системима. Слично, у рачунарској неуронауци графови се могу користити за представљање функционалних веза између области мозга које су у интеракцији да би довеле до различитих когнитивних процеса, где врхови представљају различите области мозга, а ивице представљају везе између тих области. Теорија графова игра важну улогу у електричном моделовању електричних мрежа, овде се тежине повезују са отпором сегмената жице да би се добила електрична својства мрежних структура.^[11] Графови се такође користе за представљање микро-канала порозних медија, у којима врхови представљају поре, а ивице представљају мање канале који повезују поре. Хемијска теорија графова користи молекуларни граф као средство за моделовање молекула. Графови и мреже су одлични модели за проучавање и разумевање фазних прелаза и критичних феномена. Уклањање чворова или ивица доводи до критичне транзиције где се мрежа распада у мале кластере што се проучава као фазни прелаз. Овај слом се проучава кроз теорију перколације.^[12]

Биологија

Исто тако, теорија графова је корисна у биологији и конзервационим напорима где врх може представљати регионе у којима одређене врсте постоје (или их насељавају), а ивице представљају путеве миграције или кретања између региона. Ове информације су важне када се посматрају модели размножавања или праћење ширења болести, паразита или како промене кретања могу утицати на друге врсте.

Графови се такође обично користе у молекуларној биологији и геномици за моделовање и анализу скупова података са сложеним односима. На пример, методе засноване на графовима се често користе за 'груписање' ћелија заједно у типове ћелија у анализи транскриптома једне ћелије. Друга употреба је моделовање гена или протеина у биолошком путу и проучавање односа између њих, као што су метаболички путеви и мреже регулације гена.^[13] Еволуциона стабла, еколошке мреже и хијерархијско груписање образаца експресије гена су такође представљени као структуре графова.

Теорија графова се такође користи у конектомици;^[14] нервни системи се могу посматрати као граф, где су чворови неурони, а ивице везе између њих.

Види још

Граф (структура података)
Судоку - игра слагалица која се заснива на овој теорији
Проблем трговачког путника
Бојење грана графа

Референце

^ Bender & Williamson 2010, стр. 148.
^ See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.
^ Hale, Scott A. (2013). „Multilinguals and Wikipedia Editing”. Proceedings of the 2014 ACM Conference on Web Science - WebSci '14: 99—108. Bibcode:2013arXiv1312.0976H. ISBN 9781450326223. S2CID 14027025. arXiv:1312.0976  . doi:10.1145/2615569.2615684.
^ Mashaghi, A.; et al. (2004). „Investigation of a protein complex network”. European Physical Journal B. 41 (1): 113—121. Bibcode:2004EPJB...41..113M. S2CID 9233932. arXiv:cond-mat/0304207  . doi:10.1140/epjb/e2004-00301-0.
^ Shah, Preya; Ashourvan, Arian; Mikhail, Fadi; Pines, Adam; Kini, Lohith; Oechsel, Kelly; Das, Sandhitsu R; Stein, Joel M; Shinohara, Russell T (2019-07-01). „Characterizing the role of the structural connectome in seizure dynamics”. Brain (на језику: енглески). 142 (7): 1955—1972. ISSN 0006-8950. PMC 6598625  . PMID 31099821. doi:10.1093/brain/awz125.
^ Adali, Tulay; Ortega, Antonio (мај 2018). „Applications of Graph Theory [Scanning the Issue]”. Proceedings of the IEEE. 106 (5): 784—786. ISSN 0018-9219. doi:10.1109/JPROC.2018.2820300.
^ Grandjean, Martin (2016). „A social network analysis of Twitter: Mapping the digital humanities community” (PDF). Cogent Arts & Humanities. 3 (1): 1171458. S2CID 114999767. doi:10.1080/23311983.2016.1171458  .
^ Vecchio, F (2017). „"Small World" architecture in brain connectivity and hippocampal volume in Alzheimer's disease: a study via graph theory from EEG data”. Brain Imaging and Behavior. 11 (2): 473—485. PMID 26960946. S2CID 3987492. doi:10.1007/s11682-016-9528-3.
^ Vecchio, F (2013). „Brain network connectivity assessed using graph theory in frontotemporal dementia”. Neurology. 81 (2): 134—143. PMID 23719145. S2CID 28334693. doi:10.1212/WNL.0b013e31829a33f8.
^ Bjorken, J. D.; Drell, S. D. (1965). Relativistic Quantum Fields . New York: McGraw-Hill. стр. viii.
^ Kumar, Ankush; Kulkarni, G. U. (2016-01-04). „Evaluating conducting network based transparent electrodes from geometrical considerations”. Journal of Applied Physics. 119 (1): 015102. Bibcode:2016JAP...119a5102K. ISSN 0021-8979. doi:10.1063/1.4939280.
^ Newman, Mark (2010). Networks: An Introduction (PDF). Oxford University Press. Архивирано из оригинала (PDF) 2020-07-28. г. Приступљено 2019-10-30.
^ Kelly, S.; Black, Michael (2020-07-09). „graphsim: An R package for simulating gene expression data from graph structures of biological pathways”. Journal of Open Source Software. The Open Journal. 5 (51): 2161. Bibcode:2020JOSS....5.2161K. ISSN 2475-9066. S2CID 214722561. doi:10.21105/joss.02161  .
^ Shah, Preya; Ashourvan, Arian; Mikhail, Fadi; Pines, Adam; Kini, Lohith; Oechsel, Kelly; Das, Sandhitsu R; Stein, Joel M; Shinohara, Russell T (2019-07-01). „Characterizing the role of the structural connectome in seizure dynamics”. Brain (на језику: енглески). 142 (7): 1955—1972. ISSN 0006-8950. PMC 6598625  . PMID 31099821. doi:10.1093/brain/awz125.

Литература

Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability. ISBN.
Claude, Claude (1958). Théorie des graphes et ses applications. Paris: Dunod. ISBN. English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition, Dover, New York 2001.
Biggs, N.; Lloyd, E.; Wilson, R. (1986). Graph Theory, 1736–1936. Oxford University Press. ISBN.
Bondy, J. A.; Murty, U. S. R. (2008). Graph Theory. Springer. ISBN 978-1-84628-969-9.
Bollobás, Béla; Riordan, O. M. (2003). Mathematical results on scale-free random graphs in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)) (1st изд.). Weinheim: Wiley VCH. ISBN.
Chartrand, Gary (1985). Introductory Graph Theory. Dover. ISBN 978-0-486-24775-5.
Gibbons, Alan (1985). Algorithmic Graph Theory. Cambridge University Press. ISBN.
Reuven Cohen, Shlomo Havlin (2010). Complex Networks: Structure, Robustness and Function. Cambridge University Press. ISBN 9781139489270.
Golumbic, Martin (1980). Algorithmic Graph Theory and Perfect Graphs. Academic Press. ISBN.
Harary, Frank (1969). Graph Theory. Reading, Massachusetts: Addison-Wesley. ISBN.
Harary, Frank; Palmer, Edgar M. (1973). Graphical Enumeration. New York, New York: Academic Press. ISBN.
Mahadev, N. V. R.; Peled, Uri N. (1995). Threshold Graphs and Related Topics. North-Holland. ISBN.
Newman, Mark (2010). Networks: An Introduction. Oxford University Press. ISBN.

Додатна литература

Hartmann, Alexander K.; Weigt, Martin (2006). „Phase Transitions in Combinatorial Optimization Problems, Section 3: Introduction to Graphs”. arXiv:cond-mat/0602129  .

Спољашње везе

Hazewinkel Michiel, ур. (2001). „Graph theory”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104.
Graph theory tutorial Архивирано на сајту Wayback Machine (16. јануар 2012)
A searchable database of small connected graphs
Image gallery: graphs на сајту Wayback Machine (архивирано фебруар 6, 2006)
Concise, annotated list of graph theory resources for researchers
rocs — a graph theory IDE
The Social Life of Routers — non-technical paper discussing graphs of people and computers
Graph Theory Software Архивирано на сајту Wayback Machine (13. март 2013) — tools to teach and learn graph theory
Online books, and library resources in your library and in other libraries about graph theory
A list of graph algorithms Архивирано на сајту Wayback Machine (13. јул 2019) with references and links to graph library implementations

Онлајн уџбеници

Digraphs: Theory Algorithms and Applications 2007 by Jorgen Bang-Jensen and Gregory Gutin
Graph Theory, by Reinhard Diestel

[FOOTNOTEBenderWilliamson2010148-1] Bender & Williamson 2010, стр. 148.

[2] See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.

[3] Hale, Scott A. (2013). „Multilinguals and Wikipedia Editing”. Proceedings of the 2014 ACM Conference on Web Science - WebSci '14: 99—108. Bibcode:2013arXiv1312.0976H. ISBN 9781450326223. S2CID 14027025. arXiv:1312.0976  . doi:10.1145/2615569.2615684.

[4] Mashaghi, A.; et al. (2004). „Investigation of a protein complex network”. European Physical Journal B. 41 (1): 113—121. Bibcode:2004EPJB...41..113M. S2CID 9233932. arXiv:cond-mat/0304207  . doi:10.1140/epjb/e2004-00301-0.

[5] Shah, Preya; Ashourvan, Arian; Mikhail, Fadi; Pines, Adam; Kini, Lohith; Oechsel, Kelly; Das, Sandhitsu R; Stein, Joel M; Shinohara, Russell T (2019-07-01). „Characterizing the role of the structural connectome in seizure dynamics”. Brain (на језику: енглески). 142 (7): 1955—1972. ISSN 0006-8950. PMC 6598625  . PMID 31099821. doi:10.1093/brain/awz125.

[6] Adali, Tulay; Ortega, Antonio (мај 2018). „Applications of Graph Theory [Scanning the Issue]”. Proceedings of the IEEE. 106 (5): 784—786. ISSN 0018-9219. doi:10.1109/JPROC.2018.2820300.

[7] Grandjean, Martin (2016). „A social network analysis of Twitter: Mapping the digital humanities community” (PDF). Cogent Arts & Humanities. 3 (1): 1171458. S2CID 114999767. doi:10.1080/23311983.2016.1171458  .

[8] Vecchio, F (2017). „"Small World" architecture in brain connectivity and hippocampal volume in Alzheimer's disease: a study via graph theory from EEG data”. Brain Imaging and Behavior. 11 (2): 473—485. PMID 26960946. S2CID 3987492. doi:10.1007/s11682-016-9528-3.

[9] Vecchio, F (2013). „Brain network connectivity assessed using graph theory in frontotemporal dementia”. Neurology. 81 (2): 134—143. PMID 23719145. S2CID 28334693. doi:10.1212/WNL.0b013e31829a33f8.

[10] Bjorken, J. D.; Drell, S. D. (1965). Relativistic Quantum Fields . New York: McGraw-Hill. стр. viii.

[11] Kumar, Ankush; Kulkarni, G. U. (2016-01-04). „Evaluating conducting network based transparent electrodes from geometrical considerations”. Journal of Applied Physics. 119 (1): 015102. Bibcode:2016JAP...119a5102K. ISSN 0021-8979. doi:10.1063/1.4939280.

[12] Newman, Mark (2010). Networks: An Introduction (PDF). Oxford University Press. Архивирано из оригинала (PDF) 2020-07-28. г. Приступљено 2019-10-30.

[13] Kelly, S.; Black, Michael (2020-07-09). „graphsim: An R package for simulating gene expression data from graph structures of biological pathways”. Journal of Open Source Software. The Open Journal. 5 (51): 2161. Bibcode:2020JOSS....5.2161K. ISSN 2475-9066. S2CID 214722561. doi:10.21105/joss.02161  .

[14] Shah, Preya; Ashourvan, Arian; Mikhail, Fadi; Pines, Adam; Kini, Lohith; Oechsel, Kelly; Das, Sandhitsu R; Stein, Joel M; Shinohara, Russell T (2019-07-01). „Characterizing the role of the structural connectome in seizure dynamics”. Brain (на језику: енглески). 142 (7): 1955—1972. ISSN 0006-8950. PMC 6598625  . PMID 31099821. doi:10.1093/brain/awz125.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]