Понятия и определения орграфа и неориентированного графа, методы решения. Неориентированные и ориентированные деревья. Подробное описание алгоритмов нахождения кратчайших путей в графе: мультиграф, псевдограф. Матрица достижимостей и контрдостижимостей.
Аннотация к работе
Понятие неориентированного графа 2.1 Определения 2.2 Решение заданий 1.7-1.13 Глава 3. Алгоритмы нахождения кротчайших путей в графе 4.1 Алгоритм Дейкстры (алгоритм расстановки меток) 4.2 Алгоритм Беллмана-Мура (алгоритм корректировки меток) Заключение Список используемой литературы Приложение Пояснительная записка Первая глава содержит основные понятия и определения орграфа, встречающиеся в заданиях, методы решения и подробное пояснение к заданиям 1.1-1.6 Вторая глава содержит основные понятия и определения неориентированного графа, встречающиеся в заданиях, методы решения и подробное пояснение к заданиям 1.7-1.13. По заданной матрице весов графа G (Вариант №3) выполнить: 1. Добавить в орграф дугу таким образом, чтобы одна из сильных компонент орграфа, содержала 3 вершины. Понятие орграфа 1.1 Основные определения Пусть V - конечное непустое множество, V2 - его декартов квадрат. Множества вершин и дуг орграфа G обозначаются через VG и AG соответственно.