Инструкция к практической работе
Задача. Для неориентированного графа, изображённого на рисунке, постройте матрицу смежности и матрицу инцидентности.
Решение:
Матрица смежности
Матрица инцидентности
Задача. Дана матрица 
Постройте орграф, для которого данная матрица является матрицей смежности. Найдите матрицу инцидентности орграфа.
Решение: Для построения орграфа его вершине однозначно сопоставим точку на плоскости. Данная матрица смежности имеет четыре строки и четыре столбца, следовательно, в орграфе четыре вершины 1, 2, 3, 4.
Проанализируем элементы матрицы:
при вершине 1 нет петель;
из вершины 1 выходят две стрелки к вершине 2;
из вершины 1 не выходит ни одной стрелки к вершине 3;
из вершины 1 не выходит ни одной стрелки к вершине 4;
из вершины 2 не выходит ни одной стрелки к вершине 1;
при вершине 2 нет петель;
из вершины 2 выходит одна стрелка к вершине 3;
из вершины 2 не выходит ни одной стрелки к вершине 4;
из вершины 3 выходит одна стрелка к вершине 1;
из вершины 3 не выходит ни одной стрелки к вершине 2;
при вершине 3 нет петель;
из вершины 3 выходит одна стрелка к вершине 4;
из вершины 4 выходит 3 стрелки к вершине 1;
из вершины 4 выходит одна стрелка к вершине 2;
из вершины 4 не выходит ни одной стрелки к вершине 3;
при вершине 4 нет петель.
Строим орграф.
Для построения графа запишем матрицу инцидентности:
Здесь четыре строки по числу вершин и 9 столбцов по числу дуг.
|
|
|
Задание:
Для графа заданного матрицей смежности
1. найти матрицу инцидентности
2. построить граф
3. Используя программное обеспечение, изобразите граф и проверьте матрицу.
| Вариант 1 | ||||||||||||||||||||||
|
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 3 | 4 | 5 | 6 | ||
| 1 |
| 1 | 1 | 1 |
| 1 | 1 |
| 1 |
| 1 |
| 1 | 1 |
| 1 | 1 |
|
| 1 | ||
| 2 | 1 |
| 1 |
|
| 1 | 2 |
|
| 1 |
| 1 |
| 2 |
|
| 1 | 1 | 1 |
| ||
| 3 | 1 | 1 |
| 1 | 1 | 1 | 3 |
|
|
| 1 |
| 1 | 3 |
|
|
|
| 1 | 1 | ||
| 4 | 1 |
| 1 |
|
| 1 | 4 |
|
|
|
| 1 |
| 4 |
|
|
|
| 1 |
| ||
| 5 |
|
| 1 |
|
| 1 | 5 |
|
|
|
|
| 1 | 5 |
|
|
|
|
| 1 | ||
| 6 | 1 | 1 | 1 | 1 | 1 |
| 6 |
|
|
|
|
|
| 6 |
|
|
|
|
|
| ||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
| Вариант 2. | ||||||||||||||||||||||
|
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 3 | 4 | 5 | 6 | ||
| 1 |
| 1 | 1 |
|
| 1 | 1 |
| 1 |
| 1 | 1 |
| 1 |
| 1 | 1 |
| 1 |
| ||
| 2 |
|
| 1 |
| 1 |
| 2 |
|
| 1 |
| 1 |
| 2 | 1 |
| 1 | 1 | 1 |
| ||
| 3 |
|
|
| 1 |
| 1 | 3 |
|
|
| 1 | 1 | 1 | 3 | 1 | 1 |
|
| 1 | 1 | ||
| 4 |
|
|
|
| 1 |
| 4 |
|
|
|
| 1 | 1 | 4 |
| 1 |
|
| 1 | 1 | ||
| 5 |
|
|
|
|
| 1 | 5 |
|
|
|
|
| 1 | 5 | 1 | 1 | 1 | 1 |
| 1 | ||
| 6 |
|
|
|
|
|
| 6 |
|
|
|
|
|
| 6 |
|
| 1 | 1 | 1 |
| ||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
| Вариант 3 | ||||||||||||||||||||||
|
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 3 | 4 | 5 | 6 | ||
| 1 |
| 1 |
| 1 |
| 1 | 1 |
| 1 | 1 | 1 | 1 |
| 1 |
| 1 |
| 1 | 1 |
| ||
| 2 |
|
| 1 | 1 | 1 | 1 | 2 |
|
|
|
| 1 |
| 2 | 1 |
| 1 |
| 1 | 1 | ||
| 3 |
|
|
| 1 | 1 | 1 | 3 |
|
|
| 1 | 1 | 1 | 3 |
| 1 |
| 1 |
|
| ||
| 4 |
|
|
|
|
| 1 | 4 |
|
|
|
| 1 | 1 | 4 | 1 |
| 1 |
|
| 1 | ||
| 5 |
|
|
|
|
| 1 | 5 |
|
|
|
|
| 1 | 5 | 1 | 1 |
|
|
| 1 | ||
| 6 |
|
|
|
|
|
| 6 |
|
|
|
|
|
| 6 |
| 1 |
| 1 | 1 |
| ||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
| Вариант 4 | ||||||||||||||||||||||
|
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 3 | 4 | 5 | 6 | ||
| 1 |
| 1 |
| 1 | 1 |
| 1 |
| 1 |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 1 |
| 1 | ||
| 2 |
|
| 1 |
|
| 1 | 2 |
|
| 1 | 1 |
|
| 2 | 1 |
| 1 |
|
|
| ||
| 3 |
|
|
| 1 | 1 |
| 3 |
|
|
| 1 | 1 |
| 3 | 1 | 1 |
| 1 | 1 | 1 | ||
| 4 |
|
|
|
|
| 1 | 4 |
|
|
|
| 1 | 1 | 4 | 1 |
| 1 |
| 1 | 1 | ||
| 5 |
|
|
|
|
| 1 | 5 |
|
|
|
|
|
| 5 |
|
| 1 | 1 |
| 1 | ||
| 6 |
|
|
|
|
|
| 6 |
|
|
|
|
|
| 6 | 1 |
| 1 | 1 | 1 |
| ||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
| Вариант 5 | ||||||||||||||||||||||
|
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 2 | 3
| 4 | 5 | 6 |
| 1 | 2 | 3 | 4 | 5 | 6 | ||
| 1 |
| 1 | 1 |
| 1 | 1 | 1 |
| 1 | 1 | 1 |
|
| 1 |
| 1 |
| 1 | 1 | 1 | ||
| 2 |
|
| 1 | 1 |
| 1 | 2 |
|
| 1 | 1 |
| 1 | 2 | 1 |
| 1 | 1 | 1 |
| ||
| 3 |
|
|
| 1 | 1 |
| 3 |
|
|
| 1 | 1 | 1 | 3 |
| 1 |
| 1 | 1 | 1 | ||
| 4 |
|
|
|
|
| 1 | 4 |
|
|
|
| 1 | 1 | 4 | 1 | 1 | 1 |
| 1 |
| ||
| 5 |
|
|
|
|
| 1 | 5 |
|
|
|
|
| 1 | 5 | 1 | 1 | 1 | 1 |
|
| ||
| 6 |
|
|
|
|
|
| 6 |
|
|
|
|
|
| 6 | 1 |
| 1 |
|
|
| ||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ||
Порядок выполнения работы:
1. Изучить инструкцию к практической работе.
2. Выполнить задание.
3. Оформить отчет.
Содержание отчета:
1. Тема.
2. Цель.
3. Задачи.
4. Материальное обеспечение.
5. Практическое задание.
Вопросы для самоконтроля:
1. Перечислите основные способы представления графов.
2. В чем отличия матричного представления ориентированных и неориентированных графов?
3. В чем особенности представления графа матрицей смежности?
4. В чем особенности представления графа матрицей инцидентности?
Практическая работа № 9
Тема: Решение задач по теории графов. Выделение связных компонентов. Нахождение максимального потока и минимального разреза.
Цель: научиться определять компоненты связности и находить максимальный поток и строить минимальный разрез в сети с использованием алгоритма Форда- Фалкерсона; закрепить навыки моделирования графов в графической среде Grafoanalizator1.3.3 rus.Простой граф.
Задачи:
1. Закрепить знания основных понятий теории графов.
2. Приобрести практические умения использования специального программного обеспечения для моделирования.
3. Использовать математический аппарат теории графов
Материальное обеспечение:
Программы для графического представления графов: Grafoanalizator1.3.3 rus, Прстой граф, практическая работа.
Теоретическая часть:
Дата добавления: 2019-02-22; просмотров: 1021; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!