- Увод
- Основни понятия
- Неориентиран граф
- Ориентиран граф
- Още определения
- Представяне
- Преобразуване
- Обхождане bfs
- Обхождане dfs
Теорията на графите е клон от съвременната математика. Графите са едни от най-полезните структури от данни в информатиката. Много задачи от различни области на науката и практиката могат да бъдат моделирани с граф и решени с помощта на съответен алгоритъм върху него.
Исторически първият проблем, който може да бъде отнесен към теория на графите, е задачата на Кьонигсбергските мостове на Ойлер (1736). През този пруски град минава реката Прегел, на която са построени седем моста. Пет от тях свързвали намиращия се в града остров с двата бряга. Хората си задавали въпроса дали е възможно да бъде извършена такава разходка през града, че всеки мост да бъде преминат точно веднъж. Отговаряйки на този въпрос, Ойлер поставя основите на теория на графите.
Портрет на Ойлер