материал для практического занятия по теме «Графы»


Федеральное агентство железнодорожного транспорта
ФГБОУ ВПО «Московский государственный университет путей сообщения
Императора Николая II» (МГУПС (МИИТ)Институт прикладных технологий
Московский колледж железнодорожного транспорта
РАССМОТРЕНО
на заседании цикловой комиссии
от «___»_________2016 г.
Протокол №__________
Председатель___________ УТВЕРЖДАЮ
Зам.директора института по УМ и НР
___________ Н.И. Воронова
«___»_____________2016 г.
Специальность 23.02.06
Дисциплина МАТЕМАТИКА
РУКОВОДСТВО К ВЫПОЛНЕНИЮ
Практическое занятие 2
Построение графа по условию ситуационной задачи
Преподаватель Тракич Н.В.
Москва 2016
Тема: Построение графа по условию ситуационной задачи.
Цель: Закрепить навыки работы с графами.
Формируемые компетенции:
OK 1. Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес.
ОК 2. Организовывать собственную деятельность, выбирать типовые методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.
ОК 3. Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность.
ОК 4. Осуществлять поиск и использование информации, необходимой для эффективного выполнения профессиональных задач, профессионального и личностного развития.
ОК 5. Использовать информационно-коммуникационные технологии в профессиональной деятельности.
ОК 6. Работать в коллективе и команде, эффективно общаться с коллегами, руководством, потребителями.
ОК 7. Брать на себя ответственность за работу членов команды (подчиненных), результат выполнения заданий.
ОК 8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации.
ПК 2.2. Планировать и организовывать мероприятия по соблюдению норм безопасных условий труда.
ПК 2.3. Контролировать и оценивать качество выполняемых работ.
ПК 3.1. Оформлять техническую и технологическую документацию.
ПК 3.2. Разрабатывать технологические процессы на ремонт отдельных деталей и узлов подвижного состава железных дорог в соответствии с нормативной документацией.
Порядок выполнения:
Задача 1. Построить граф по матрице смежности :
Задача 2. Для графа задать матрицу смежности:
3
2
1
4
5

Задача 3. Построить граф по матрице инцидентности:
*Задача 4. Для графа задать матрицу инцидентности:
4
3
2
5
6
1

Задача 5. Построить ориентированный граф по матрице инцидентности:

1
3
4
5
2
*Задача 6. Для ориентированного графа задать матрицу инцидентности:
Критерии оценки: «3» - любые четыре верно решенные задачи
«4» - любые пять верно решенные задачи
«5» - все верно решенные задачи
Методические указания:
Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали.
Примеры
Ниже приведён пример неориентированного графа и соответствующей ему матрицы смежности A. Этот граф содержит петлю вокруг вершины 1, при этом в зависимости от конкретных приложений элемент  может считаться равным либо одному (как показано ниже), либо двум.
ГрафМатрица смежности

aij — число рёбер, связывающих вершины  и , причем в некоторых приложениях каждая петля (ребро  при некотором ) учитывается дважды.
Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.
Свойства
Матрица смежности неориентированного графа симметрична, а значит обладает действительными собственными значениями и ортогональным базисом из собственных векторов. Набор её собственных значений называется спектром графа, и является основным предметом изучения спектральной теории графов.
Два графа G1 и G2 с матрицами смежности A1 и A2 являются изоморфными если и только если существует перестановочная матрица P, такая что
PA1P-1 = A2.
Из этого следует, что матрицы A1 и A2 подобны, а значит имеют равные наборы собственных значений,определители и характеристические многочлены. Однако обратное утверждение не всегда верно — два графа с подобными матрицами смежности могут быть неизоморфны.
Степени матрицы
Если A — матрица смежности графа G, то матрица  HYPERLINK "https://ru.wikipedia.org/w/index.php?title=%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%87%D0%BD%D0%B0%D1%8F_%D1%81%D1%82%D0%B5%D0%BF%D0%B5%D0%BD%D1%8C&action=edit&redlink=1" \o "Матричная степень (страница отсутствует)" Am обладает следующим свойством: элемент в i-й строке, j-м столбце равен числу путей из i-й вершины в j-ю, состоящих из ровно m ребер.
Структура данных
Матрица смежности и списки смежности являются основными структурами данных, которые используются для представления графов в компьютерных программах
Использование матрицы смежности предпочтительно только в случае неразреженных графов, с большим числом рёбер, так как она требует хранения по одному биту данных для каждого элемента. Если граф разрежён, то большая часть памяти напрасно будет тратиться на хранение нулей, зато в случае неразреженных графов матрица смежности достаточно компактно представляет граф в памяти, используя примерно  бит памяти, что может быть на порядок лучше списков смежности.
В алгоритмах, работающих со взвешенными графами (например, в алгоритме Флойда-Уоршелла), элементы матрицы смежности вместо чисел 0 и 1, указывающих на присутствие или отсутствие ребра, часто содержат веса самих ребер. При этом на место отсутствующих ребер ставят некоторое специальное граничное значение (англ. sentinel), зависящее от решаемой задачи, обычно 0 или .
Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке матрицы указывает связь между вершиной и ребром (их инцидентность).
В случае ориентированного графа каждой дуге <x,y> ставится в соответствие "-1" в строке вершины x и столбце дуги <x,y> и "1" в строке вершины y и столбце дуги <x,y>; если связи между вершиной и ребром нет, то в соответствующую ячейку ставится "0".
Пример
ГрафМатрица инцидентности

Особенности данного представления
Используется для любых графов, даже если есть петля.
В каждом столбце обязательно должны стоять две единицы (либо 1 и -1 в случае ориентированного графа).
Контрольные вопросы:
Виды множеств
Операции над множествами
Виды графов
Матрица смежности для графа
Матрица инцидентности для ориентированного графа
Литература:
Богомолов Н.В. Математика: Учебник для ссузов. М.: Дрофа, 2010.
2. Богомолов Н.В. Сборник задач по математике: Учебное пособие для ссузов. М.: Дрофа, 2012.
3. Богомолов Н.В. Практические занятия по математике: Учебное пособие для ссузов. М.: Дрофа, 2007.

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

  • docx file7.doc
    Тракич Н.В.
    Размер файла: 72 kB Загрузок: 2

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