Практическая работа №1 по МДК 01.02: Математический аппарат для построения компьютерных сетей наименование работы: Решение задач по теории графов. Построение матриц смежностей и инцидентностей.

Смоленский колледж телекоммуникаций
(филиал) федерального государственного
бюджетного образовательного учреждения высшего образования
«Санкт-Петербургский государственный университет телекоммуникаций
им. проф. М.А. Бонч-Бруевича»















Практическая работа №1
по МДК 01.02: Математический аппарат для построения компьютерных сетей
наименование работы: Решение задач по теории графов. Построение матриц смежностей и инцидентностей.
для специальности: 09.02.02
работа рассчитана на 2 часа
составлена преподавателем: Скряго О.С.



Смоленск, 2016

1. Цель работы: получить практические навыки по построению графов и определению матриц смежности для решения конкретных задач. Научиться составлять матрицы инцидентности.
2. Литература:
2.1. Асанов, М. О. Дискретная математика: графы, матроиды, алгоритмы: Учебное пособие. 2-е изд. / М.О. Асанов , В.А.Баранский , В.В. Расин - СПб. : Издательство «Лань» 2012 г. 368с. - ISBN 978-5-8114-1068-2
2.2. Мельников, О.И. Теория графов в занимательных задачах. Изд.4, испр. и доп./О.И. Мельников 2012. 240 с. М.: Книжный дом "Либриком" ISBN978-5-9775-0232-0
2. 3. Новиков, Ф.А. Дискретная математика: Учебник для вузов. 2-е изд. Стандарт третьего поколения: учебник / Ф.А. Новиков. - СПб. : Питер 2012, 400с.- ISBN 978-5-496-00015-4

3. Подготовка к работе:
3.1. Повторить тему «Основные понятия графа».
3.2. Подготовить бланк отчета (см.п.7).
3.3. Ответить на вопросы допуска:
3.3.1. Сформулируйте определения графа?
3.3.2. Сформулируйте определение ориентированного графа?
3.3.3. Сформулируйте определение неориентированного графа ?

4. Основное оборудование:
4.1. не используется.

5. Задание:
Выполните задания согласно варианту.

Задание 1. Постройте матрицы смежности и инцидентности для неориентированного и ориентированного графов:

Вариант 1







Вариант 2






Вариант 3






Вариант 4




Вариант 5





Вариант 6






Вариант 7





Вариант 8




Вариант 9






Вариант 10









Задание 2. Восстановите геометрическое представление графа по матрице
инцидентности.
Вариант 1






Вариант 2





Вариант 3








Вариант 4







Вариант 5







Вариант 6 Вариант 7






Вариант 8 Вариант 9







Вариант 10









Задание 3. Восстановите геометрическое представление графа по матрице
смежности.

Вариант 1 Вариант 2







Вариант 3




Вариант 4 Вариант 5









Вариант 6







Вариант 7








Вариант 8 Вариант 9








Вариант 10








6. Порядок выполнения работы:
6.1. Ознакомиться с заданием.
6.2. Определить номер варианта (в соответствии с номером в журнале).
6.3. Выполнить задания в соответствии с вариантом.
6.4. Ответьте на контрольные вопросы.

7. Содержание отчёта:
7.1. Название и цель работы.
7.2 Ответы на вопросы допуска.
7.2. Указать номер варианта, привести условия заданий своего варианта.
7.3. Представить результат выполнения заданий.
7.4. Ответы на контрольные вопросы.
7.5. Вывод о проделанной работе.

8. Контрольные вопросы:
8.1. Какой граф называют конечным?
8.2. Сформулируйте определение смежных ребер и вершин?
8.3. Что называют степенью вершины?
8.4. Какой граф называют нулевым?
8.5. Сформулируйте определение простого графа?



Составил преподаватель __________________________Скряго О.С.



9. Приложение:

Граф - Пара объектов G = ( X , Г ) ,где Х - конечное множество ,а Г –конечное подмножество прямого произведения Х*Х . При этом Х называется множеством вершин , а Г - множеством дуг графа G .
Любое конечное множество точек (вершин), некоторые из которых попарно соединены стрелками , (в теории графов эти стрелки называются дуга-ми), можно рассматривать как граф.
Если в множестве Г все пары упорядочены, то такой граф называют ориентированным .
Дуга- ребро ориентированного графа.
Граф называется вырожденным, если у него нет рёбер.
Вершина Х называется инцидентной ребру G , если ребро соединяет эту вершину с какой-либо другой вершиной.
Подграфом, порождённым множеством вершин U называется подграф, множество вершин которого – U, содержащий те и только те рёбра, оба конца которых входят в U.
Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.
Вершины называются смежными , если существует ребро , их соединяющее.
Два ребра G1 и G2 называются смежными, если существует вершина, инцидентная одновременно G1 и G2.
Каждый граф можно представить в пространстве множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам (или дугам - в последнем случае направление обычно указывается стрелочками). - такое представление называется укладкой графа.
Доказано, что в 3-мерном пространстве любой граф можно представить в виде укладки таким образом, что линии, соответствующие ребрам (дугам) не будут пересекаться во внутренних точках. 2
Гранью графа, изображенного на некоторой поверхности, называется часть поверхности, ограниченная рёбрами графа.
Данное понятие грани, по - существу, совпадает с понятием грани многогранника. В качестве поверхности в этом случае выступает поверхность многогранника. Если многогранник выпуклый, его можно изобразить на плоскости, сохранив все грани. Это можно наглядно представить следующим образом: одну из граней многогранника растягиваем, а сам многогранник «расплющиваем» так, чтобы он весь поместился внутри этой грани. В результате получим плоский граф. Грань, которую мы растягивали «исчезнет», но ей будет соответствовать грань, состоящая из части плоскости, ограничивающей граф.
Таким образом, можно говорить о вершинах, рёбрах и гранях многогранника, а оперировать соответствующими понятиями для плоского графа.
Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежные.
Конечная последовательность необязательно различных рёбер E1,E2,...En называется маршрутом длины n, если существует последовательность V1, V2, ... Vn необязательно различных вершин, таких, что Ei = (Vi-1,Vi ).
Если совпадают, то маршрут замкнутый.
Маршрут, в котором все рёбра попарно различны, называется цепью.
Замкнутый маршрут, все рёбра которого различны, называется цик-лом. Если все вершины цепи или цикла различны, то такая цепь или цикл называются простыми.
Маршрут, в котором все вершины попарно различны, называется простой цепью.
Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.
Граф называется связным, если для любых двух вершин существует путь, соединяющий эти вершины.
Любой максимальный связный подграф (то есть, не содержащийся в других связных подграфах) графа G называется компонентой связности. Несвязный граф имеет, по крайней мере, две компоненты связности.
Граф называется k - связным (k - реберно - связным), если удаление не менее k вершин (ребер) приводит к потере свойства связности.
Маршрут, содержащий все вершины или ребра графа и обладающий определенными свойствами, называется обходом графа.
Длина маршрута (цепи, простой цепи) равна количеству ребер а порядке их прохождения. Длина кратчайшей простой цепи, соединяющей вершины vi и vj в графе G, называется расстоянием d (vi, vj) между vi и vj.
Степень вершины - число ребер, которым инцидентна вершина V, обозначается D(V).
С помощью различных операций можно строить графы из более простых, переходить от графа к более простому, разбивать графы на более простые и т.д.
Среди одноместных операций наиболее употребительны: удаление и добавление ребра или вершины, стягивание ребра (отождествление пары смежных вершин), подразбиение ребра (т.е. замена ребра (u, v) на пару (u, w), (w, v), где w - новая вершина) и др.
Известны двуместные операции: соединение, сложение, различные виды умножений графов и др. Такие операции используются для анализа и синтеза графов с заданными свойствами.
Два графа G1=(V1;E1), G2=(V2;E2),называются изоморфными, если существует взаимнооднозначное соответствие между множествами вершин V1 и V2 и между множествами рёбер Е1 и Е2, такое, чтобы сохранялось отношение инцидентности.
Понятие изоморфизма для графов имеет наглядное толкование. Представим рёбра графов эластичными нитями, связывающими узлы – вершины. Тогда, изоморфизм можно представить как перемещение узлов и растяжение нитей.
Связный граф без циклов называется деревом.
Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярные генеалогические деревья.
Способы задания графов:
1. Геометрический:


































2. Матрица смежности:








Матрица смежности - квадратная матрица, размерности, равной количеству вершин. При этом а[ i, j ]-целое число, равное количеству рёбер, связывающих i-ю, j-ю вершину. Если в графе нет петель, то диагональные элементы равны 0 .
Если рёбра не повторяются, то все элементы 0 или 1. Если граф неориентированный, то матрица симметрична.
3. Матрица инцидентности:
















Приложенные файлы

  • doc 106
    Скряго О.С.
    Размер файла: 466 kB Загрузок: 4

Добавить комментарий