МАПКС-03-ОперацииНадГрафами. Мдк. 01. 02 Математический аппарат для построения компьютерных сетей
 Скачать 1.12 Mb.
|
|
(МАПКС-03) – 1 МДК.01.02 – Математический аппарат для построения компьютерных сетей 3. Операции над графами Актуализация опорных знаний ............................................................... Основные операции над графами .......................................................... Бинарные операции .......................................................................... Унарные операции ............................................................................ Контрольные вопросы ............................................................................. Литература ОИ03. И. А. Палий. Дискретная математика : учебное пособие для среднего профессионального образования. – Москва : Издательство Юрайт, 2019. — 352 с. — (Профессиональное образование. — ISBN 978-5-534- 06292-2. — Текст : электронный // ЭБС Юрайт сайт. — URL: https://biblio- online.ru/bcode/441865 . – С. 209-215. Алексеев В.Е., Захарова Д.В. Теория графов. Электронное учебно- методическое пособие. – Нижний Новгород Нижегородский госуниверситет, 2012. – 57 с. – С. 7-8. Актуализация опорных знаний Основной объект теории графов — граф и его обобщения. Граф – это множество точек, называемых вершинами, и множество линий, называемых ребрами, которые соединяют пары вершин (или вершину саму с собой. Ребро и любая из его двух вершин называются инцидентными. Под степенью вершины подразумевается количество инцидентных ей рѐбер. Изолированная вершина графа имеет степень 0, а висячая – степень 1. Графом G(V, E) называется совокупность двух множеств — непустого множества V (множества вершин) и множества E двухэлементных подмножеств множества V (E — множество рѐбер). Связи между элементами изображаются на графе линиями. Если линия направленная, то она называется дугой. Если нетто это ребро. Граф, в котором направление линий не выделяется (все линии являются ребрами, называется неориентированным граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным. Основные операции над графами Поскольку граф может быть определен как совокупность двух множеств, то многие операции над графами могут быть описаны в терминах теории множеств. (МАПКС-03) – 2 Раздел 1: Основы теории графов Два множества Аи В равны (А=В), если они состоят из одних и тех же элементов. Например, если А, B={3,1,4,2} то А=В. Объединением (суммой) множеств Аи В называется множество А ∪ В, элементы которого принадлежат хотя бы одному из этих множеств. Например, если А, B={3,4,5,6}, то А ∪ B = {1,2,3,4,5,6} Пересечением (произведением множеств Аи В называется множество А ∩ В, элементы которого принадлежат как множеству Атаки множеству В. Например, если А, B={3,4,5,2}, то А ∩ В = {2,4} Разностью множеств Аи В называется множество АВ, элементы которого принадлежат множесву А, ноне принадлежат множеству В. Например, если А, B={3,4,5}, то АВ = {1,2}. Рассмотрим семь операций над графами, три из которых являются бинарными, включающими два графа, а остальные четыре – унарные, те. определены на одном графе. Бинарные операции Объединение графов 𝐺 1 и 𝐺 2 , обозначаемое как 𝐺 1 ∪ 𝐺 2 , представляет такой граф 𝐺 3 = (𝑋 1 ∪ 𝑋 2 , 𝐴 1 ∪ 𝐴 2 ), что множество его вершин является объединением Хи Ха множество ребер – объединением A 1 и Рис. 1. Исходные графы 𝐺 1 и Предложить студентам построить матрицы смежности исходных графов Матрицы смежности исходных графов имеют вид Объединение Граф G 3 , полученный операцией объединения графов G 1 и G 2 , показан на рис. 2. (МАПКС-03) – 3 3. Операции над графами При объединении графов матрица смежности результирующего графа получается операцией поэлементного логического сложения матриц смежности исходных графов G 1 и Рис. 2 Пересечение Пересечение графов G 1 и G 2 , обозначаемое как 𝐺 1 ∩ 𝐺 2 , представляет собой граф 𝐺 4 = (𝑋 1 ∩ 𝑋 2 , 𝐴 1 ∩ 𝐴 2 ). Таким образом, множество вершин графа G 4 состоит из вершин, присутствующих одновременно в G 1 и Операция пересечения графов 𝐺 1 ∩ 𝐺 2 показана на риса При пересечении графов результирующая матрица смежности получается операцией поэлементного логического умножения матриц смежности исходных графов G 1 и Рис. 3. Результат операции пересечения графов Кольцевая сумма Кольцевая сумма двух графов G 1 и G 2 , обозначаемая как 𝐺 1 ⨁𝐺 2 , представляет собой граф G 5 , порожденный на множестве ребер в результате кольцевой суммы граф G 5 не имеет изолированных вершин и состоит только из ребер, присутствующих либо в G 1 , либо в G 2 , ноне в обоих одновременно. Кольцевая сумма графов G 1 и G 2 показана на риса результирующая матрица смежности получается операцией поэлементного логического сложения по модулю 2 (обозначается mod 2) матриц смежности исходных графов G 1 и G 2 (МАПКС-03) – 4 Раздел 1: Основы теории графов Рис. 4. Результат кольцевой суммы графов Легко убедиться в том, что три рассмотренные операции коммутативны те и многоместны, те итак далее. Унарные операции Рассмотрим унарные операции на графе, который показан на рис. 5. ( 𝒙 𝟏 𝒙 𝟐 𝒙 𝟑 𝒙 𝟒 𝒙 𝟓 𝒙 𝟏 0 1 0 0 0 𝒙 𝟐 0 0 1 0 1 𝒙 𝟑 0 0 0 1 1 𝒙 𝟒 0 0 1 0 0 𝒙 𝟓 1 0 0 1 0 Рис. 5. Исходный граф для рассмотрения унарных операций Удаление вершины. Если х i -вершина графа G = (X, A), то х i -порожденный подграф графа G на множестве вершин х i , тех является графом, получившимся после удаления из графа G вершины хи всех ребер, инцидентных этой вершине. Удаление вершины х показано на риса Рис. 6. Результат удаления вершины Результирующая матрица смежности графа после выполнения операции удаления вершины х i получается путем удаления соответствующего- го столбца и j -ой строки из исходной матрицы и "сжимания" матрицы по вертикали и горизонтали (МАПКС-03) – 5 3. Операции над графами начиная с (i+1) - го столбца и (j+1) -ой строки . В дальнейшем элементы графа могут быть переобозначены. Удаление ребра или удаление дуги. Если a i - дуга графа G = (X, A), то G-a i – подграф графа G, получающийся после удаления из G дуги a i . Заметим, что концевые вершины дуги a не удаляются. Удаление из графа множества вершин или дуг определяется как последовательное удаление определенных вершин или дуг. Удаление дуги показано на рис. 7. Результирующая матрица смежности графа после выполнения операции удаления дуги a i получается путем удаления соответствующих элементов из исходной матрицы. ( 𝒙 𝟏 𝒙 𝟐 𝒙 𝟑 𝒙 𝟒 𝒙 𝟓 𝒙 𝟏 1 𝒙 𝟐 − 1 𝒙 𝟑 1 1 𝒙 𝟒 − 𝒙 𝟓 1 Рис. Удаление дуги Замыкание или отождествление. Говорят, что пара вершин хи в графе G замыкается (или отождествляется, если они заменяются такой новой вершиной, что все дуги в графе G, инцидентные хи, становятся инцидентными новой вершине. Например, результат замыкания вершины хи х показан на рис. 8 для графа G. ( 𝒙 𝟏−𝟐 𝒙 𝟑 𝒙 𝟒 𝒙 𝟓 𝒙 𝟏−𝟐 1 1 0 1 𝒙 𝟑 0 0 1 1 𝒙 𝟒 0 1 0 0 𝒙 𝟓 1 0 1 0 Рис. 8. Результат замыкания вершин хи х 2 Матрица смежности графа после выполнения операции замыкания вершин хи получается путем поэлементного логического сложения i - го иго столбцов и i -ой и j - строк в исходной матрице и "сжимания" матрицы по вертикали и горизонтали. Стягивание. Под стягиванием подразумевают операцию удаления дуги или ребра и отождествление его концевых вершин. На рис. 9 изображен результат стягивания дуги a 1 , а на рис. 10 – стягивания дуги (МАПКС-03) – 6 Раздел 1: Основы теории графов 1 0 1 𝒙 𝟑 0 0 1 1 𝒙 𝟒 0 1 0 0 𝒙 𝟓 1 0 1 0 Рис. 9. Результат стягивания дуги a 1 ( 𝒙 𝟏−𝟐 𝒙 𝟑−𝟒 𝒙 𝟓 𝒙 𝟏−𝟐 0 1 1 𝒙 𝟑−𝟒 0 0 1 𝒙 𝟓 1 1 0 ) Рис. 10. Результат стягивания дуги Контрольные вопросы 1. Выполнить операцию пересечения для графов, показанных на рисунке. Рис. 11. К контрольному вопросу 1 Варианты ответов a. а ; b. б ; c. в ; d. нет верного рисунка 2. Выполнить операцию пересечения 𝐺 1 ∩ 𝐺 2 для графов, представленных матрицами смежности (МАПКС-03) – 7 3. Операции над графами 𝐺 1 = ( 𝒙 𝟏 𝒙 𝟐 𝒙 𝟑 𝒙 𝟒 𝒙 𝟓 𝒙 𝟏 0 0 0 0 1 𝒙 𝟐 1 0 0 1 0 𝒙 𝟑 0 0 0 0 0 𝒙 𝟒 0 0 1 0 0 𝒙 𝟓 0 1 0 1 0 ) ; 𝐺 2 = ( 𝒙 𝟏 𝒙 𝟐 𝒙 𝟑 𝒙 𝟒 𝒙 𝟓 𝒙 𝟏 0 0 0 0 1 𝒙 𝟐 1 0 1 0 1 𝒙 𝟑 0 0 0 0 0 𝒙 𝟒 0 1 1 0 1 𝒙 𝟓 0 0 0 0 0 Варианты ответов a. граф представлена. граф представлен б c. граф представлен в 2. Для графа 𝐺 1 , представленного на рис. 11, выполнить операцию отождествления вершин хи х. Есть ли ошибки на рисунке (если есть – укажите, какие. a. неверно ; b. верно ( 𝒙 𝟏−𝟐 𝒙 𝟑 𝒙 𝟒 𝒙 𝟓 𝒙 𝟏−𝟐 1 0 1 1 𝒙 𝟑 0 0 0 1 𝒙 𝟒 0 1 0 0 𝒙 𝟓 1 0 1 0 ) (МАПКС-03) – 8 Раздел 1: Основы теории графов (МАПКС-03) – 9 3. Операции над графами |