УНАРНЫЕ И БИНАРНЫЕ ОПЕРАЦИИ НАД ГРАФАМИ
Цель работы — исследование унарных, бинарных операций над графами и приобретение практических навыков решения задач с использованием основ теории графов. Основные понятия и определения Все унарные операции над графами можно объединить в две группы. Первую группу составляют операции, с помощью которых из исходного графа G1, можно построить граф G2 с меньшим числом элементов. В группу входят операции удаления ребра или вершины, отождествления вершин, стягивание ребра. Вторую группу составляют операции, позволяющие строить графы с большим числом элементов. В группу входят операции расщепления вершин, добавления ребра. Отождествление вершин. В графе G1 выделяются вершины и, v . Определяют окружение Q1 вершины u,и окружение Q2 вершины v , вычисляют их объединение Q = Q 1 Q 2 . Затем над графом G1 выполняются следующие преобразования: — из графа G1 удаляют вершины u , v ( H1 = G1 - u - v); — к графу Н1присоединяют новую вершину z ( H1 = H1 + z ); — вершину z соединяют ребром с каждой из вершин w1 Q (G2 = H1 + zwi, i = 1,2,3,…). Стягивание ребра. Данная операция является операцией отождествления смежных вершин и, v в графе G1. Наиболее важными бинарными операциями являются: объединение, пересечение, декартово произведение и кольцевая сумма. Объединение. Граф G называется объединением или наложением графов G1 и G2, если VG = V1 V2; UG = U1 U2 (рис. 1). Рис. 1. Объединение графов G1, G2 Объединение графов G1 и G2 называется дизъюнктным, если V1 V2 = . При дизъюнктном объединении никакие два из объединяемых графов не должны иметь общих вершин. Пересечение. Граф G называется пересечением графов G1, G2,если VG = V1 V2и UG = U1 U2 (риc.2). Операция "пересечения" записывается следующим образом: G = G1 G2. Рис.2. Пересечение графов G1, G2. Декартово произведение. Граф G называется декартовым произведением графов G1 и G2 если VG = V1 V2 —декартово произведение множеств вершин графов G1, G2, а множество ребер Uc задается следующим образом: вершины (zi, vk) и (zj, vl) смежны в графе G тогда и только тогда, когда zi = zj(i = j), a vk и vl смежны в G2 или vk = vl(k = l), смежны в графе G1 (см. рис.3). Рис. 3. Декартово произведение графов G1, G2 Кольцевая сумма графов представляет граф, который не имеет изолированных вершин и состоит из ребер, присутствующих либо в первом исходном графе, либо во втором. Кольцевая сумма определяется следующим соотношением: G = G1 G2 (рис.4). Рис.4. Кольцевая сумма графов G1, G2 Лабораторное задание 1. Выполните генерацию матриц M1, М2 смежности неориентированных помеченных графой G1, G2. Метки вершин выберите из подмножества натуральных чисел {1, 2, …, n}. Порядок графов, определяется преподавателем. Вычислите матрицу смежности дополнительного графа (дополнения) G1. Порядок графа п определяется преподавателем. 2. Вычислите матрицы смежности подграфов Н, Q графа G1( G1). Например: H = G1 - vi, i = 1, 2,..., n; Q = G1 - vi - vj, i = 1, 2,..., n, i j. 3. Выполните операцию отождествления вершин (стягивания ребра, расщепления вершины) в графе G1( G1), Номера выбираемых для выполнения операции двух вершин (вершины) согласуйте с преподавателем. 4. Выполните операцию объединения (пересечения, кольцевой суммы) графов G = G1 G2 (G = G1 G2, G = G1 G2). 5. Выполните операцию декартова произведения графов G = G1X G2, i = 1,2 Содержание отчета 1. Матричные и графические представления графов G1( G1),Н, Q,, G2, G3. 2. Протоколы и результаты выполнения операций отождествления вершин (стягивания ребра), расщепления вершины объединения, пересечения, кольцевой суммы, декартова произведения графов в матричной и графической формах. Контрольные вопросы 1. Задан неориентированный граф G. В графе удаляются вершина и два ребра. Существенна ли последовательность выполнения операций? 2. Как выглядит колода P( G) п — вершинного графа G, если все подграфы, входящие в колоду, выписать следующим образом: G1 = G - vi, i = 1, 2, ..., n? 3. К = {{1, 2}; {1, 2}} — полный двухвершинный граф, Q = ({{1,2,3,4}; {{1, 2}; {2, 3}; {3, 4}; {4, 1}} - двумерный куб. Верно ли, что граф R = К Q - трехмерный куб? 4. Графы H = H1 H2и Q являются подграфами полного n-вершинного графа. Выполняется ли для них соотношение H Q = (H1 H2) Q = H1 Q H2 Q?
Популярное: Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1056)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |