Графы
Математическое описание системы автоматического управления с помощью графов. Составление графа и его преобразование, избавление от дифференциалов. Оптимизации ориентированных и неориентированных графов, составления матриц смежности и инцидентности.
| Рубрика | Математика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 11.03.2012 |
| Размер файла | 42,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Балаковский Институт Техники Технологии и Управления
Саратовский Государственный Технический Университет
Лабораторная работа №4
ГРАФЫ
Выполнила
ст. гр. УИТ-3в
Проверила
Соколова Т.В.
Балаково 2008
Цель работы: приобрести навыки математического описания САУ с помощью графов, а также оптимизации ориентированных и неориентированных графов и составления матриц смежности и инцидентности.
Задание №1. По заданной схеме уравнений составить граф и провести его преобразование.
граф матрица дифференциал
Избавимся от дифференциалов, перейдя к операторному виду.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Задание №2. По заданным схемам ориентированного и неориентированного графов составить матрицы смежности и инцидентности, а также провести оптимизацию графов.
Неориентированный граф.
Размещено на http://www.allbest.ru/
Составляем список ребер в порядке увеличения их весов:
, , , , , , , .
Отбрасываем те ребра, которые образуют цикл:
, , , .
Оставшиеся ребра образуют минимально покрывающее дерево.
Размещено на http://www.allbest.ru/
Составляем матрицу смежности:
|
А = |
a |
b |
c |
d |
e |
||
|
a |
0 |
1 |
0 |
1 |
0 |
||
|
b |
1 |
0 |
0 |
0 |
0 |
||
|
c |
0 |
1 |
0 |
0 |
1 |
||
|
d |
1 |
0 |
0 |
0 |
0 |
||
|
e |
0 |
0 |
1 |
0 |
0 |
Составляем матрицу инцидентности:
|
В = |
ad |
ab |
bc |
ce |
||
|
a |
1 |
1 |
0 |
0 |
||
|
b |
0 |
1 |
1 |
0 |
||
|
c |
0 |
0 |
1 |
1 |
||
|
d |
1 |
0 |
0 |
0 |
||
|
e |
0 |
0 |
0 |
1 |
Ориентированный граф.
Размещено на http://www.allbest.ru/
Минимальный путь от истока к стоку - последовательность вершин
.
Вес пути .
Составим матрицу смежности:
|
R = |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
||
|
X1 |
0 |
1 |
1 |
1 |
0 |
0 |
||
|
X2 |
0 |
0 |
0 |
0 |
0 |
0 |
||
|
X3 |
0 |
1 |
0 |
0 |
1 |
0 |
||
|
X4 |
0 |
0 |
0 |
0 |
1 |
0 |
||
|
X5 |
0 |
0 |
0 |
0 |
0 |
1 |
||
|
X6 |
0 |
0 |
0 |
0 |
0 |
0 |
Составим матрицу инцидентности:
|
S = |
X1X2 |
X1X3 |
X3X2 |
X3X5 |
X4X5 |
X5X6 |
X1X4 |
||
|
X1 |
-1 |
-1 |
0 |
0 |
0 |
0 |
-1 |
||
|
X2 |
+1 |
0 |
+1 |
0 |
0 |
0 |
0 |
||
|
X3 |
0 |
+1 |
-1 |
-1 |
0 |
0 |
0 |
||
|
X4 |
0 |
0 |
0 |
0 |
-1 |
0 |
+1 |
||
|
X5 |
0 |
0 |
0 |
+1 |
+1 |
-1 |
0 |
||
|
X6 |
0 |
0 |
0 |
0 |
0 |
+1 |
0 |
Размещено на Allbest.ru
Подобные документы
Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
лабораторная работа [85,5 K], добавлен 09.01.2009Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.
курсовая работа [636,2 K], добавлен 20.12.2015Понятие и матричное представление графов. Ориентированные и неориентированные графы. Опеределение матрицы смежности. Маршруты, цепи, циклы и их свойства. Метрические характеристики графа. Применение теории графов в различных областях науки и техники.
курсовая работа [423,7 K], добавлен 21.02.2009Ориентированные и неориентированные графы: общая характеристика, специальные вершины и ребра, полустепени вершин, матрицы смежности, инцидентности, достижимости, связности. Числовые характеристики каждого графа, обход в глубину и в ширину, базис циклов.
курсовая работа [225,5 K], добавлен 14.05.2012Понятие "граф" и его матричное представление. Свойства матриц смежности и инцидентности. Свойства маршрутов, цепей и циклов. Задача нахождения центральных вершин графа, его метрические характеристики. Приложение теории графов в областях науки и техники.
курсовая работа [271,1 K], добавлен 09.05.2015Теория графов как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Основные понятия теории графов. Матрицы смежности и инцидентности и их практическое применение при анализе решений.
реферат [368,2 K], добавлен 13.06.2011Спектральная теория графов. Теоремы теории матриц и их применение к исследованию спектров графов. Определение и спектр предфрактального фрактального графов с затравкой регулярной степени. Связи между спектральными и структурными свойствами графов.
дипломная работа [272,5 K], добавлен 05.06.2014Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.
курсовая работа [1006,8 K], добавлен 23.12.2007Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.
дипломная работа [145,5 K], добавлен 19.07.2011
