Теорија графова — разлика између измена
Садржај обрисан Садржај додат
м Бот: уклоњен шаблон: Link FA |
м Бот: исправљена преусмерења; козметичке измене |
||
Ред 1:
[[
'''Теорија графова''' је област [[математика|математике]], веома заступљена и у [[информатика|информатици]], чија је област истраживање особина [[граф]]ова. Неформално говорећи, графови су састављени од тачака, односно чворова (врхова), и линија међу њима, односно грана.
Ред 15:
[[Степен (теорија графова)|Степен чвора]] v<sub>i</sub>=d(v<sub>i</sub>) је једнак броју грана које улазе/излазе из њега, с тим да се петља рачуна као две гране. Тотални степен графа је збир свих степени графа, и једнак је двоструком броју грана. Није могуће нацртати граф са непарним степеном.
[[
Граф G'=(V',E') је подграф графа G=(V, E) ако је скуп његових чворова (V') подскуп скупа чворова графа G (V), а скуп његових грана (E') је подскуп скупа грана вектора G (E). Ако је овим графовима скуп чворова једнак, онда се граф G' назива разапињујућим графом, или скелетом.
[[
Ако је степен сваког чвора исти, онда је граф регуларан. Комплетан граф је прост граф, код кога су свака два чвора спојена граном.
[[
Два графа, G<sub>1</sub>, и G<sub>2</sub> су изоморфна ако и само ако постоји „[[инјективно пресликавање|1-1]]“ и „[[
== Историја ==
Први проблем и његово решење изнесени на начин који је другачији у односу на претходне и може се сматрати претечом теорије графова јесте рад [[Леонард Ојлер|Леонарда Ојлера]] под називом ''[[Седам мостова Кенигсберга]]'', објављен [[1736]]. Ово је први резултат из области топологије у геометрији; што ће рећи не зависи од неке мере односно величине. Ово приказује дубоке везе између теорије графова и [[топологија|топологије]].
[[Густаф Кирхоф|Густав Кирхоф]] је [[1845]]. године објавио нешто што је касније названо [[Кирхофови закони|Кирхофов закон]], а односило се на проблем рачуна [[електрични напон|напона]] и [[електрична струја|струје]] у електричном колу.
Френсис Гутри је [[1852]]. године је изложио [[проблем четири боје]] који поставља питање да ли је могуће обојити земље на географској карти са само четири боје, а да се не појаве две суседне земље обојене истом бојом. Овај проблем су решили тек [[1976]]. године Кенет Апел и Волфганг Хекен, али се постављање овог проблема сматра рођењем теорије графова. Током покушаја решавања овог проблема
== Види још ==
* [[Граф (структура података)]]
* [[Судоку]] - игра слагалица која се заснива на овој теорији
* [[Проблем трговачког путника]]
== Спољашње везе ==
| |||