"Операции над графами"

Лекционный материал рекомендуется к изучению по разделу дискретной математики "Теория графов". В лекции рассматриваются следующие понятия: 1. Объединение графов. 2. Удаление ребра или дуги. 3. Замыкание или отождествление. 4. Стягивание.
Скачать материал
Просмотр
содержимого документа

Занятие 5.

Тема: Операции над графами.

 

Цель занятия: познакомить обучающихся с основными операциями над графами.

План:

  1. Объединение графов.
  2. Удаление ребра или дуги.
  3. Замыкание или отождествление.
  4. Стягивание.

Литература:

1.Арасланов, Ш.В. Теория графов. Лекции и практические занятия: учеб.пособие. — Казань: Изд-во Казанск.гос.архитект.- строит.ун-та, 2013. – 87 с.

2.Новиков, Ф.А. Дискретная математика: Учебник для вузов. 2-е изд. Стандарт третьего поколения. — СПб.:Питер, 2013. - 432 с.:ил.

 

Операции над графами

 

Рассмотрим семь операций над графами, три из которых являются бинарными, включающими два графа, а остальные четыре – унарные, т. е. определены на одном графе.

Объединение графов G1 и G2, обозначаемое как , представляет такой граф , что множество его вершин является объединением Х1 и Х2 , а множество ребер – объединением A1 и A2 .

Граф G3, полученный операцией объединения графов G1 и G2, показан на рис. 1,д, а его матрица смежности – на рис. 1,е.

Матрица смежности результирующего графа получается операцией поэлементного логического сложения матриц смежности исходных графов G1 и G2.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 1.

Пересечение графов G1 и G2, обозначаемое как , представляет собой граф .

Таким образом, множество вершин графа G4 состоит из вершин, присутствующих одновременно в G1 и G2.

Операция пересечения графов показана на рис. 2,в, а результирующая матрица смежности получается операцией поэлементного логического умножения матриц смежности исходных графов G1 и G2 . показана на рис. 2.г.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис.2. Операция пересечения и кольцевой суммы: а граф G1; б граф G2 ; в граф;  г – матрица смежности графа ; д – граф ;  е – матрица смежности графа

Кольцевая сумма двух графов G1 и G2, обозначаемая как ,представляет собой граф G5 , порожденный на множестве ребер .

Другими словами, граф G5 не имеет изолированных вершин и состоит только из ребер, присутствующих либо в G1, либо в G2 , но не в обоих одновременно.

Кольцевая сумма графов G1 и G2 показана на рис. 2,д, а результирующая матрица смежности получается операцией поэлементного логического сложения по mod 2 матриц смежности исходных графов G1 и G2 . показана на рис. 2.е.

Легко убедиться в том, что три рассмотренные операции коммутативны


 


т. е.

и многоместны, т. е.

 

и так далее.

Рассмотрим унарные операции на графе.

Удаление вершины. Если хi -вершина графа G = (X, A), то G–хi -порожденный подграф графа G на множестве вершин X–хi , т. е. G–х i является графом, получившимся после удаления из графа G вершины хi и всех ребер, инцидентных этой вершине.

Удаление вершины х3 показано на рис. 3,б (для исходного графа, изображенного на рис. 3,а).

Матрица смежности исходного графа представлена на таблице 1а. Результирующая матрица смежности графа после выполнения операции удаления вершины хi получается путем удаления соответствующего i - го столбца и i -ой строки из исходной матрицы и "сжимания" матрицы по вертикали и горизонтали начиная с (i+1) - го столбца и (i+1) -ой строки (таблица 1б).

В дальнейшем элементы графа могут быть переобозначены.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 3.

 

Удаление ребра или удаление дуги. Если ai - дуга графа G = (X, A), то G-ai – подграф графа G, получающийся после удаления из G дуги ai . Заметим, что концевые вершины дуги ai не удаляются. Удаление из графа множества вершин или дуг определяется как последовательное удаление определенных вершин или дуг. Удаление дуг a4 и a7 показано на рис. 3,в. Результирующая матрица смежности графа после выполнения операции удаления дуги ai получается путем удаления соответствующих элементов из исходной матрицы ( таблица 1в).


 


 

 

Таблица 1a.

 

 

X1 X2 X3 X4 X5

X1

1

 

 

X2

1

 

1

X3

 

1

1

X4

1

 

 

X5

1

1

 

Таблица 1г.

 

 

 


 

 

Таблица 1б.

 

X1 X2 X4 X5

X1

 

1

X2

 

1

X4

 

 

X5

1

1

Таблица 1д.

 


 

 

 

Таблица 1в.

 

 

X1 X2 X3 X4 X5

X1

1

 

 

X2

 

 

1

X3

 

1

1

X4

 

 

 

X5

1

1

 

Таблица 1е.

 

 

 

 


 

X1-2 X3 X4 X5

X1-2 X3 X4 X5

X1-2 X3-4 X5

X1-2  1    1

 

1   X1-2

1

1   X1-2

 

11

X3

 

1  1   X3

 

1  1   X3

 

1

X4

1

 

X4

1

X5

1

1

X5

1

1

X5

1

1

 

 

 

Замыкание или отождествление. Говорят, что пара вершин хi  и xj  в графе G

замыкается (или отождествляется), если они заменяются такой новой вершиной, что все

дуги в графе G, инцидентные хi

и xj , становятся инцидентными новой вершине.

Например, результат замыкания вершины х1 и х2 показан на рис. 3,г для графа G (

рис. 3,а).

 

 

 

 

 

 

 

Матрица смежности графа после выполнения операции замыкания вершин хi  и xj

получается путем поэлементного логического сложения i - го и j - го столбцов и i -ой и j -

строк в исходной матрице и "сжимания" матрицы по вертикали и горизонтали (таблица

1г).

 

 

 

 

 

 

 

Стягивание. Под стягиванием подразумевают операцию удаления дуги или ребра

и отождествление его концевых вершин.

 

 

 

 

Граф,  изображенный  на  рис.  3,д  получен  стягиванием  дуги  a1,  а  на  рис.  3,е 

стягиванием дуг a1 , a6 и a7 .

 

 

 

 

 

 

Соответствующие результирующие матрицы смежности показаны в таблицах 1д и

1е.

 

 

 

 

 

 

 

Вопросы и задания

 

 

 

 

 

 

 

  1. Выполнить операцию пересечения G1 G2 для графов, показанных на рисунке 1.

 


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


 

  1. а
  2. б
  3. в
  4. нет верного рисунка

 

 

 

 

 

 

 

  1. Выполнить операцию пересечения G1 ∩ G2 для графов, представленных матрицами смежности в таблице 1

 

 

Матрица смежности G1  Матрица смежности G2

 

X1   X2   X3   X4   X5

 

X1   X2   X3   X4   X5

X1

0

0

0

0

1

X1

0

0

0

0

1

X2

1

0

0

1

0

X2

1

0

1

0

1

X3

0

0

0

0

0

X3

0

0

0

0

0

X4

0

0

1

0

0

X4

0

1

1

0

1

X5

0

1

0

1

0

X5

0

0

0

0

0

 

 

 

 

a

 

 

 

 

 

б

 

 

 

 

 

в

 

 

 

X1 X2 X3 X4 X5

 

X1 X2 X3 X4 X5

 

X1 X2 X3 X4 X5

X1  0  0   0      0   1  X1  0   0   0      0    0  X1   0   0  0   0  1

X2

1

0

0

0

0

X2

0

0

1

1

1

X2

1

0

1

1

1

X3

0

0

0

0

0

X3

0

0

0

0

0

X3

0

0

0

0

0

X4

0

0

1

0

0

X4

0

1

0

0

1

X4

0

1

1

0

1

X5

0

0

0

0

0

X5

0

1

0

1

0

X5

0

1

0

1

0

 

  1. граф представлен а
  2. граф представлен б
  3. граф представлен в

 

  1. Для графа G1, показанном на рисунке 1, выполнить операцию отождествления двух вершин (х34). Верно ли результат представлен на рис. 2а?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  1. неверно
  2. верно
  1. Для графа G1, показанном на рисунке 1, выполнить операцию отождествления двух вершин (х12). Верно ли результат представлен матрицей смежности ниже?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

X(1,2) X3 X4 X5

 

X(1,2) 1

1

1

X3

 

 

 

X4

 

1

 

X5

1

1

 

 

  1. неверно
  2. верно

 

  1. Для графа G1, показанном на рисунке a, выполнить операцию стягивания двух вершин (х12). Верно ли результат представлен графом на рисунке б?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  1. верно
  2. неверно

 

  1. В графе G6 , показанном на рис. 1 удалить вершину х2. Результат представлен в матричном виде ниже

 

 

 

 

 

 

 

 

 

 

 

а

 

б

 

в

 

X2 X3

X1 X2

X1 X3

X2 0

1

X1 0

1

X1 0

1

X2 1

0

X2 1

0

X3 1

0

  1. верно а
  2. верно в
  3. верно б

  1. В графе G6 , показанном на рис. 1 удалить вершину х3. Результат представлен в матричном виде ниже

 


 

 

 

 

 

 

 

 

а

X2 X3

X2 0 1

X2 1 0

 

  1. верно а
  2. верно в
  3. верно б


 

 

 

 

 

 

 

 

  • в

X1 X2

X1 X3

X1 0

1

X1 0

1

X2 1

0

X3 1

0

 


  1. В графе G6 , показанном на рис. 1 удалить дугу (х13). Результат представлен ниже

 

  • матричном виде

 

 

 

 

 

 

 

 

 

 

а

 

 

б

 

 

в

X1 X2 X3

X1 X2 X3

X1 X2 X3

X1

1  1

 

X1

 

1

X1

1

X2 1

1

X2 1

 

1

X2 1

1

X3 1

 

 

X3 1

1

 

X3 1

1

  1. верно в
  2. верно а
  3. верно б

 

  1. В графе G6 , показанном на рис. 1 удалить дугу (х12). Результат представлен ниже

 

  • матричном виде

 

 

 

 

 

 

 

 

 

 

а

 

 

б

 

 

в

X1 X2 X3

X1 X2 X3

X1 X2 X3

X1

1  1

 

X1

 

1

X1

1

X2 1

1

X2 1

 

1

X2 1

1

X3 1

 

 

X3 1

1

 

X3 1

1

  1. верно б
  2. верно в
  3. верно а

Домашнее задание: стр. 30-35,стр. 122. Подготовить ответы на контрольные вопросы.

Информация о публикации
Загружено: 17 января
Просмотров: 3198
Скачиваний: 18
Карасева Виолетта Сергеевна
Математика, СУЗ, Уроки