Варианты к лабораторной работе
Практическая работа №2
Элементы теории графов.
Постановка задачи.
Изучить основные элементы теории графов посредством восстановления таблицы смежности по заданному графу и восстановлению графа по заданной таблице смежности.
Теоретический материал.
Теория графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E - подмножество V.
Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
Терминология теории графов поныне не определена строго. В частности, в монографии Гудман, Хидетниеми, 1981 сказано: «В программистском мире нет единого мнения о том, какой из двух терминов „граф“ или „сеть“. Мы выбрали термин «сеть», так как он, по-видимому, чаще встречается в прикладных областях». Аналогичная ситуация с терминами «вершина/точка».
|
|
|
Виды графов:
- неориентированный (неорграф)
- ориентированный (орграф).
При изображении графов на рисунках чаще всего используется следующая система обозначений: вершины графа изображаются точками или, при конкретизации смысла вершины, прямоугольниками, овалами и др., где внутри фигуры раскрывается смысл вершины (графы блок-схем алгоритмов). Если между вершинами существует ребро, то соответствующие точки (фигуры) соединяются линией или дугой. В случае ориентированного графа дуги заменяют стрелками, они явно указывают направленность ребра. Иногда рядом с ребром размещают поясняющие надписи, раскрывающие смысл ребра, например, в графах переходов конечных автоматов. Различают планарные и не планарные графы. Планарный граф — это граф, который можно изобразить на рисунке (плоскости) без пересечения рёбер (простейшие — треугольник или пара связанных вершин), иначе граф не планарный. В том случае, если граф не содержит циклов (содержащих, по крайней мере, один путь однократного обхода рёбер и вершин с возвратом в исходную вершину), его принято называть «деревом». Важные виды деревьев в теории графов — бинарные деревья, где каждая вершина имеет одно входящее ребро и ровно два выходящих, или является конечной — не имеющей выходящих рёбер и содержит одну корневую вершину, в которую нет входящего ребра.
|
|
|
Не следует путать изображение графа собственно с графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет (другими словами, изоморфны ли соответствующие изображениям графы). В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.
Последовательность выполнения работы.
1. Получить задание согласно своему варианту.
2. По заданному изображению графа удалить у него указанные в варианте рёбра и вершины.
3. Изобразить полученный граф и составить по нему таблицу смежности.
4. По заданной таблице смежности изобразить граф на плоскости с заданными вершинами.
5. Оформить отчет по лабораторной работе в соответствии с требуемым содержанием (см. далее).
|
|
|
Содержание отчета (отчет оформляется в электронном виде)
1. Титульный лист согласно требованиям Университета.
2. Содержание.
3. Постановка задачи.
4. Вопросы, заданные преподавателем.
5. Выводы.
6. Список информационных источников.
Примеры дополнительных вопросов, которые могут возникнуть на защите лабораторной работы:
– Что такое граф?
– Классификация графов?
– Чем отличаются орграф и неорграф?
– Где используются графы?
– Основные задачи, связанные с теорией графов.
– Другие вопросы по теме работы.
Варианты к лабораторной работе
Пример выполнения задания 1.
Граф:
Матрица смежности:
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 | 0 |
Матрица инцидентности:
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
Пример выполнения задания 2.
Пример выполнения задания №3.
Неориентированный граф (1) Ориентированный граф (2)
|
|
|
Матрица смежности (1)
| 1 | 2 | 3 | 4 | |
| 1 | 0 | 1 | 1 | 1 |
| 2 | 1 | 0 | 1 | 1 |
| 3 | 1 | 1 | 0 | 1 |
| 4 | 1 | 1 | 1 | 0 |
Матрица инцидентности (1)
| 1-2 | 1-3 | 1-4 | 2-3 | 2-4 | 3-4 | |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 2 | 1 | 0 | 0 | 1 | 1 | 0 |
| 3 | 0 | 1 | 0 | 1 | 0 | 1 |
| 4 | 0 | 0 | 1 | 0 | 1 | 1 |
Матрица смежности (2)
| 1 | 2 | 3 | 4 | |
| 1 | 0 | 0 | 1 | 1 |
| 2 | 1 | 0 | 0 | 1 |
| 3 | 1 | 1 | 0 | 0 |
| 4 | 0 | 1 | 1 | 0 |
Матрица инцидентности (2)
| 0 | 0 | 1 | 0 | 1 | -1 | -1 | 0 |
| 1 | -1 | -1 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | -1 | 1 | 0 | -1 |
| -1 | 1 | 0 | -1 | 0 | 0 | 1 | 0 |
Пример выполнения задания №4.
Количество вершин: 8;
Число рёбер: 13;
Степень 1, 2, 6 = 4;
Степень 4, 5, 7 и 8 = 2;
Степень 3 = 6;
При построении графов следует избегать пересечений ребер
Матрица смежности:
0, 1, 1, 0, 1, 1, 0, 0,
1, 0, 1, 1, 0, 1, 0, 0,
1, 1, 0, 1, 1, 0, 1, 1,
0, 1, 1, 0, 0, 0, 0, 0,
1, 0, 1, 0, 0, 0, 0, 0,
1, 1, 0, 0, 0, 0, 1, 1,
0, 0, 1, 0, 0, 1, 0, 0,
0, 0, 1, 0, 0, 1, 0, 0
Матрица инцидентности:
1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0
1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0
0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0
0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0
0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0
0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1
Матрица смежности:
0, 1, 1, 0, 1, 1, 0, 0,
0, 0, 1, 1, 0, 1, 0, 0,
0, 0, 0, 1, 1, 0, 1, 1,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 1,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0
Матрица инцидентности:
1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0
-1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0
0, -1, 0, 0, -1, 0, 0, 1, 1, 1, 1, 0, 0
0, 0, 0, 0, 0, -1, 0, -1, 0, 0, 0, 0, 0
0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0
0, 0, 0, -1, 0, 0, -1, 0, 0, 0, 0, 1, 1
0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1, 0
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, -1
Дата добавления: 2020-12-12; просмотров: 92; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!