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

Граф со 6 јазли и 7 гранки

Теоријата на графови е област на математиката, мошне застапена во информатиката, која се занимава со истражување на особеностите на графот. Графовите се математички објекти што често ги среќаваме во секојдневниот живот како:

• Географска мапа со многу градови кои се поврзани со патишта;
• Собир на луѓе со меѓусебни познанства;
• Структурна формула на некоја молекула или соединение;
• Шема на некое електрично коло.

Графовите се составени од точки односно јазли (врвови) и од линии меѓу нив односно гранки.

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

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