4 Теория графов 47

4.1 ИСТОРИЯ ТЕОРИИ ГРАФОВ 47

4.2 ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ 47

4.3 СПОСОБЫ ПРЕДСТАВЛЕНИЯ ГРАФОВ 49

4.3.1 Матрицей смежности 50

4.3.2 Матрицей инцидентности 50

4.4 ПУТИ В ГРАФАХ 51

4.4.1 Задача о кратчайшем пути 51

4.4.2 Алгоритм Дейкстры нахождения кратчайшего пути в графе 51

4.5 ТРАНСПОРТНЫЕ СЕТИ 53

4.5.1 Потоки в транспортных сетях 53

4.5.2 Задача нахождения наибольшего потока в транспортной сети 55

4.5.3 Алгоритм Форда и Фалкерсона нахождения максимального потока транспортной сети 55

4.5.4 Транспортная задача 58

4.6 ОБХОДЫ В ГРАФАХ 64

4.6.1 Эйлеровы графы 64

4.6.2 Алгоритм Флёри нахождения эйлерова цикла 66

4.6.3 Гамильтоновы циклы 67

4.6.4 Метод ветвей и границ. 69

4.6.5 Метод ветвей и границ в задаче о коммивояжёре 70

4.7 ДЕРЕВЬЯ 76

4.7.1 Построение экономического дерева 77

4.7.2 Алгоритм Краскала 78