Википедија

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

област математике, која изучава графове

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

Означени граф са 6 чворова и 7 грана

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

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

ОсобинеУреди

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

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

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

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

 

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

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

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

 

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

ИсторијаУреди

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

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

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

Види јошУреди

РеференцеУреди

  1. ^ Bender & Williamson 2010, стр. 148.
  2. ^ See, for instance, Iyanaga and Kawada, 69 J, p. 234 or Biggs, p. 4.

ЛитератураУреди

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

Спољашње везеУреди

 
Теорија графова на Викимедијиној остави.

Онлајн уџбенициУреди

Преузето из „https://sr.wikipedia.org/w/index.php?title=Теорија_графова&oldid=25382773”