Графы

Балаковский Институт Техники Технологии и Управления Саратовский Государственный Технический Университет

Лабораторная работа №4

ГРАФЫ

Выполнила ст. гр. УИТ-3 В Проверила Соколова Т.В.

Балаково 2008

Цель работы: приобрести навыки математического описания САУ с помощью графов, а также оптимизации ориентированных и неориентированных графов и составления матриц смежности и инцидентности.

Задание № 1. По заданной схеме уравнений составить граф и провести его преобразование.

граф матрица дифференциал Избавимся от дифференциалов, перейдя к операторному виду.

Задание № 2. По заданным схемам ориентированного и неориентированного графов составить матрицы смежности и инцидентности, а также провести оптимизацию графов.

Неориентированный граф.

Составляем список ребер в порядке увеличения их весов:

, ,, ,, , .

Отбрасываем те ребра, которые образуют цикл:

, , .

Оставшиеся ребра образуют минимально покрывающее дерево.

Составляем матрицу смежности:

Составляем матрицу инцидентности:

Ориентированный граф.

Минимальный путь от истока к стоку — последовательность вершин

.

Вес пути .

Составим матрицу смежности:

Составим матрицу инцидентности: