|
[[Датотека:6n-graf.svg|мини|десно|Означени граф са 6 чворова и 7 грана]]
'''Теорија графова''' је област [[математика|математике]], веома заступљена и у [[информатика|информатици]], чија је област истраживање особина [[граф]]ова. Неформално говорећи, графови су састављени од тачака, односно чворова (врхова), и линија међу њима, односно грана.
Веома је честа употреба графова за опис модела или структура података. Структура једне веб презентације се може представити сликовито употребом графа. Чворови тог графа су поједине странице а гране графа су везе којима се може са једне странице прелазити на другу.
== Особине ==
Ако се може сматрати да је грана која спаја чворове '''''А''''' и '''''Б''''' исто што и грана која спаја чворове '''''Б''''' и '''''А''''', онда је граф ''неусмерен''. Ако се пак сматра да су то две различите гране онда је граф ''усмерен''.{{sfn|Bender|Williamson|2010|p=148}}<ref>See, for instance, Iyanaga and Kawada, ''69 J'', p. 234 or Biggs, p. 4.</ref>
Појам графа може бити проширен додавањем особине тежине свакој грани. Овакви графови се зову ''тежински графови'' и они су згодни за представљање неких проблема, на пример мреже путева где се тежина односи на дужину пута између два чвора. Тежински граф који је усмерен зове се ''мрежа''.
Први проблем и његово решење изнесени на начин који је другачији у односу на претходне и може се сматрати претечом теорије графова јесте рад [[Леонард Ојлер|Леонарда Ојлера]] под називом ''[[Седам мостова Кенигсберга]]'', објављен [[1736]]. Ово је први резултат из области топологије у геометрији; што ће рећи не зависи од неке мере односно величине. Ово приказује дубоке везе између теорије графова и [[топологија|топологије]].
[[Густаф Кирхоф|Густав Кирхоф]] је [[1845]]. године објавио нешто што је касније названо [[Кирхофови закони|Кирхофов закон]], а односило се на проблем рачуна [[електрични напон|напона]] и [[електрична струја|струје]] у електричном колу.
Френсис Гутри је [[1852]]. године је изложио [[проблем четири боје]] који поставља питање да ли је могуће обојити земље на географској карти са само четири боје, а да се не појаве две суседне земље обојене истом бојом. Овај проблем су решили тек [[1976]]. године Кенет Апел и Волфганг Хекен, али се постављање овог проблема сматра рођењем теорије графова. Током покушаја решавања овог проблема откривене су многе теореме и постављени многи теоретски појмови и концепти.
== Литература ==
{{refbegin|30em}}
* {{citeCite book |last1 ref = harv | last=Bender |first1first=Edward A. |last2=Williamson |first2=S. Gill |date year=2010 |title=Lists, Decisions and Graphs. With an Introduction to Probability |url=https://books.google.fr/books?id=vaXv_yhefG8C |location= |page= |isbnid=ISBN |author-link= }}
* {{citeCite book | ref = harv | last=Claude |first=Claude |date year=1958 |title=Théorie des graphes et ses applications |url= |location=Paris |publisher=Dunod |page= |isbnid=ISBN |author-link= }} 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.
* {{citeCite book |last1 ref = harv | last=Biggs |first1first=N. |last2=Lloyd |first2=E. |last3=Wilson |first3=R. |date year=1986 |title=Graph Theory, 1736–1936|url= |location= |publisher=Oxford University Press |page= |isbnid=ISBN |author-link= }}
* {{citeCite book |last1 ref = harv | last=Bondy |first1first=J. A. |last2=Murty |first2=U. S. R. |date year=2008 |title=Graph Theory |url= |location= |publisher=Springer |page= |isbn=978-1-84628-969-9 |author-link= }}
* {{citeCite book |last1 ref = harv | last=Bollobás |first1first=Béla |first2=O. M. |last2=Riordan |date year=2003 |title=Mathematical results on scale-free random graphs in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)) |url= |edition=1st |location=Weinheim |publisher=Wiley VCH |page= |isbnid=ISBN |author-link= }}
* {{citeCite book | ref = harv | last=Chartrand |first=Gary |date year=1985 |title=Introductory Graph Theory |url= |location= |publisher=Dover |page= |isbnid=ISBN 0-486-24775-9 |author-link= }}
* {{citeCite book | ref = harv | last=Gibbons |first=Alan |date year=1985 |title=Algorithmic Graph Theory |url= |location= |publisher=[[Cambridge University Press]] |page= |isbnid=ISBN |author-link= }}
* {{citeCite book | ref = harv | last=Reuven Cohen |first=Shlomo Havlin |date year=2010 |title=Complex Networks: Structure, Robustness and Function |url=https://books.google.com/?id=1ECLiFrKulIC&pg=PR5&dq=%22Complex+Networks:+Structure,+Robustness+and+Function%22#v=onepage&q=graph&f=false |location= |publisher=Cambridge University Press |page= |isbn= 9781139489270|author-link= }}
* {{citeCite book | ref = harv | last=Golumbic |first=Martin |date year=1980 |title=Algorithmic Graph Theory and Perfect Graphs |url= |location= |publisher=[[Academic Press]] |page= |isbnid=ISBN |author-link= }}
* {{citeCite book | ref = harv | last=Harary |first=Frank |date year=1969 |title=Graph Theory |url= |location=Reading, Massachusetts |publisher=Addison-Wesley |page= |isbnid=ISBN |author-link= }}
* {{citeCite book |last1 ref = harv | last=Harary |first1first=Frank |last2=Palmer |first2=Edgar M. |date year=1973 |title=Graphical Enumeration |url= |location=New York, New York |publisher=Academic Press |page= |isbnid=ISBN |author-link= }}
* {{citeCite book |last1 ref = harv | last=Mahadev |first1first=N. V. R. |last2=Peled |first2=Uri N. |date year=1995 |title=Threshold Graphs and Related Topics |url= |location= |publisher=[[North-Holland Publishing Company|North-Holland]] |page= |isbnid=ISBN |author-link= }}
* {{citeCite book | ref = harv | last=Newman |first=Mark |date year=2010 |title=Networks: An Introduction |url= |location= |publisher=Oxford University Press |page= |isbnid=ISBN |author-link= }}
{{refend}}
{{DEFAULTSORT:Теорија графова}}
[[Категорија:Теорија графова | ]] ▼
▲[[Категорија:Теорија графова]]
[[Категорија:Математичке теорије]]
| 