logo
Графы

Пояснительная записка

Первая глава содержит основные понятия и определения орграфа, встречающиеся в заданиях, методы решения и подробное пояснение к заданиям 1.1-1.6

  • Вторая глава содержит основные понятия и определения неориентированного графа, встречающиеся в заданиях, методы решения и подробное пояснение к заданиям 1.7-1.13.
  • Третья глава содержит основные понятия, определения и примеры неориентированных и ориентированных деревьев.
  • Четвертая глава содержит подробное описание алгоритмов нахождения кротчайших путей в графе.
  • Задание 1. По заданной матрице весов графа G (Вариант №3) выполнить:
  • 1. Преобразовать матрицу весов в матрицу смежности орграфа. По полученной матрице:
  • 2. Построить орграф.
  • 3. Указать для каждой вершины ее степень входа и степень выхода.
  • 4. Построить матрицу инцидентности орграфа.
  • 5. Добавить в орграф дугу таким образом, чтобы одна из сильных компонент орграфа, содержала 3 вершины. Разложить полученный орграф на сильные компоненты по алгоритму.
  • 6. Построить матрицу достижимостей и контрдостижимостей.
  • 7. Преобразовать полученный орграф в неориентированный граф.
  • 8. Построить неориентированный граф.
  • 9. Перечислить смежные вершины и ребра,
  • 10. Составить для него матрицу смежности.
  • 11. Указать степени вершин графа.
  • 12. Составить матрицу Кирхгофа и матрицу инцидентности.
  • 13. Изменить граф таким образом, чтобы получить: полный граф, мультиграф, псевдограф, дерево. Построить полученные графы.
  • Задание 2. По заданной матрице весов графа G (Вариант №3) найти величину минимального пути и сам путь от вершины до конечной вершины или по алгоритму Дейкстры.
  • Задание 3. По заданной матрице весов графа G (Вариант №3) найти минимальный путь и сам путь по алгоритму Беллмана-Мура между начальной вершиной и конечной вершиной или .