Применение теории графов в информатике

Родоначальником теории графов считается Леонард Эйлер. В 1736 г. в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них.
Вначале теория графов казалась довольно незначительным разделом математики, т.к. она имела дело в основном с математическими развлечениями и головоломками. Однако уже в XIX столетии графы использовались при построении схем электрических цепей и молекулярных схем.

Введение……………………………………………………………………..……….3
Теоретическая часть……………………………………………………….….4
Основные понятия теории графов………………………………………..4
Основные теоремы теории графов……………………………………….6
Способы и требования к представлению графов в компьютере……….8
Типовые задачи теории графов………………..………..……………….10
Заключение……………………………………………………………………….…12
Практическая часть………………………………………………………….13
Общая характеристика задачи…………………………………………..13
Описание алгоритма решения задачи………………………………….16
Список используемой литературы………………………………………………..20