операции над графами. Занятие 29. Тема Операции над графами План лекции Полный граф Бинарные операции над графами
![]()
|
Занятие 29. Тема «Операции над графами» План лекции: Полный граф Бинарные операции над графами Унарные операции над графами Полный граф Полным графом G называется граф с п вершинами без петель, кратных и противоположных дуг (ориентация безразлична), у которого любые две вершины соединены ребром. Например ![]() Бинарные операции над графами Бинарные операции включают два графа. Бинарные операции над графами. Наиболее важными бинарными операциями являются: объединение, пересечение, кольцевая сумма и дополнение. Операции могут выполняться как графически, так и с помощью матриц смежности каждого графа. Рассмотрим все бинарные операции двумя способами. Объединение. Граф G=(X,А) называется объединением (или наложением) графов G1= (Х1, А1) и G2 = (Х2, А2), если множество его вершин является объединением Х1и Х2, а множество ребер - объединением А1 и А2: Другими словами, в один граф добавляются все вершины и ребра одного и второго графа (одинаковые остаются по одному). G= G1 ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() В матрице смежности объединенного графа работает операция дизъюнкция по таблице истинности. Матрицы смежности графов G1 и G2 имеют вид ![]() ![]() А1= А2= Объединение графов G1 ![]() ![]() Пересечение. Граф G=(X,А) называется пересечением графов G1=(Х1,А1) и G2=(Х2,А2), если множество его вершин является пересечением Х1и Х2, а множество ребер - пересечением А1и A2: G = G1 ![]() ![]() ![]() ![]() ![]() ![]() ![]() G G1 ![]() ![]() ![]() ![]() ![]() ![]() G2 Матрица смежности пересеченного графа G1 ![]() ![]() 3. Кольцевая сумма. Граф G=(X,А)=G1 ![]() ![]() ![]() ![]() ![]() G2 ![]() ![]() ![]() ![]() ![]() Матрица смежности кольцевого графа G1 ![]() ![]() 4. Разность. Граф G=(X,А)называется разностью графов G1=(Х1,А1) и G2=(Х2,А2), если множество его вершин является разностью Х1и Х2, а множество ребер - разностью А1и. A2: G= G1 ![]() ![]() ![]() ![]() ![]() ![]() ![]() G ![]() ![]() ![]() ![]() G1 ![]() ![]() ![]() ![]() ![]() G2 Матрица смежности разностного графа G1 ![]() ![]() 5. Дополнением графаG=(X,А1)является граф ![]() ![]() ![]() Матрица смежности полного графа, состоит из всех 1, кроме главной диагонали. Матрица смежности дополненного графа G1 ![]() G: ![]() ![]() ![]() Унарные операции над графами Унарные операции определены на одном графе. Рассмотрим их. Удаление вершины. Если xi - вершина графа G=(X,А), то G-i является графом, получившимся после удаления из графа Gвершимы i ивсех ребер, инцидентных этой вершине. Удаление из графа вершины влечет удаление всех ребер, входящих в эту вершину. Удаление вершины 2 показано на рисунке: ![]() ![]() Удаление ребра или удаление дуги. Если аi - ребро графа G = (X, А), то G-аiявляется графом, получающимся после удаления из Gребра аi. Заметим, что концевые вершины ребра аi, не удаляются. После удаления всех ребер граф оказывается без ребер. Удаление ребер (5,4) и (1,2) показано на рисунке: ![]() ![]() Замыкание или отождествление. Говорят, что пара вершин хiи хj в графе Gзамыкается (или отождествляется), если они замыкаются такой новой вершиной, что все дуги в графе G, инцидентные хiи хj, становятся инцидентными новой вершине. После замыкания, дуга или ребро, находящееся между вершинами, станет петлей. Например, результат замыкания вершин 2 и 3 показан на рисунке: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 2,3? 4 5 1 ![]() Стягивание. Под стягиванием подразумевают операцию удаления дуги или ребра и отождествление его концевых вершин. После стягивания, две вершины совмещаются в одну, а ребро или дуга, находящаяся между ними, удаляется. Граф, изображенный на следующем рисунке, получен стягиванием ребра (1,5): ![]() 2 ![]() ![]() Самостоятельная работа студентов Переписать лекцию в тетрадь и прислать фото Выполнить все бинарные операции (кроме дополнения) двумя способами для следующих графов: G1: ![]() ![]() Выполнить все унарные операции для следующего графа по следующим параметрам (удаление вершины 3, удаление дуги (46), замыкание вершин 1 и 3, стягивание дуги (46)). ![]() |