Глава 2.Ненаправленные графы, часть 1. Простые графы (графы) Способы задания графа Основные способы задания графов графический

• Название: Простые графы (графы) Способы задания графа Основные способы задания графов графический
• Анкор: Глава 2.Ненаправленные графы, часть 1.doc
• Дата: 04.09.2018
• Размер: 1.28 Mb.
• Имя файла: Глава 2.Ненаправленные графы, часть 1.doc
• Тип: Глава; #24055
• страница: 4 из 14

2.2.3. Унарные операции над графами

Для графа G=(V,E) частью графа называется такой граф H=(V^’,E^’), у которого V^’(H)V(G) и E^’(H)E(G). Другими словами, этот граф, порожденный ребрами графа G. Частью графа является путь, цикл и т.п. Вместо термина «часть графа» часто используют термин «подграф (в слабом смысле)».

Подграф ( в сильном смысле)- для графа G=(V,E) такой граф H=(W,U), у которого множество вершин WV, множество ребер UE, причем если {x,y}E и x,yW, то обязательно {x,y}U.

Если G₁G и G₁ содержит все вершины графа G, тогда G₁ называют каркасным подграфом. Каркасных подграфов может быть несколько.

Дополнением графа G=(V,E) называется граф G’=(V,E’), у которого:

• 
  вершины исходного графа G,
  
• 
  ребра E’ являются ребрами, дополняющими граф G до полного графа K_n.
  

Пример

G

G’

Рис.2.2.5. Граф G и его дополнение G’

Определение

Операцией декомпозиции графа G(V,E) называется представление его в виде последовательности графов G₁,…, G_S таких, что:

• 
  число вершин одинаково у всех графов G₁,…, G_S;
  
• 
  число ребер E(G) графа G=(V,E) равно объединению ребер графов G₁,…, G_S:
  

E(G)= E(G_i).

Замечания

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

Определение

Операция построения реберного графа L(G)=(U,F) графа G=(V,E) состоит в следующем:

• 
  каждой вершине uU реберного графа L(G) сопоставлено ребро e_iE(G) графа G;
  
• 
  в

  Пример

  ершины в L(G) смежны тогда и только тогда, когда соответствующие ребра смежны в графе G.
  

е₁

е₆


е₂


е₄

е₅

е₃


Вершины L(G): U₁={1,2}, U₂={1,3}, U₃={1,4},

U₄={2,3}, U₅={2,4}, U₆={3,4}



Ребра L(G) (определяются в соответствии со вторым условием):


1 ребро L(G)

ребра {1,2}и{1,3} смежны в G:

U₁ соединена ребром с U₂

2 ребро L(G)

ребра {1,2}и{1,4} смежны в G:

U₁ соединена ребром с U₃

3 ребро L(G)

ребра {1,2}и{2,4} смежны в G:

U₁ соединена ребром с U₅

4 ребро L(G)

ребра {1,2}и{2,3} смежны в G:

U₁ соединена ребром с U₄

5 ребро L(G)

ребра {1,2}и{1,3} смежны в G:

вариант был

6 ребро L(G)

ребра {1,3}и{1,4} смежны в G:

U₂ соединена ребром с U₃

7 ребро L(G)

ребра {1,3}и{2,3} смежны в G:

U₂ соединена ребром с U₄

8 ребро L(G)

ребра {1,3}и{3,4} смежны в G:

U₂ соединена ребром с U₆

9 ребро L(G)

ребра {1,4}и{1,2} смежны в G:

вариант был

10 ребро L(G)

ребра {1,4}и{1,3} смежны в G:

вариант был


11 ребро L(G)

ребра {1,4}и{2,4} смежны в G:

U₃ соединена ребром с U₅

12 ребро L(G)

ребра {1,4}и{3,4} смежны в G:

U₃ соединена ребром с U₆

13 ребро L(G)

ребра {2,3}и{1,3} смежны в G:

вариант был

14 ребро L(G)

ребра {2,3}и{1,2} смежны в G:

вариант был

15 ребро L(G)

ребра {2,3}и{2,4} смежны в G:

U₄ соединена ребром с U₅

16 ребро L(G)

ребра {2,3}и{3,4} смежны в G:

U₄ соединена ребром с U₆

17 ребро L(G)

ребра {3,4}и{1,3} смежны в G:

вариант был

18 ребро L(G)

ребра {3,4}и{2,3} смежны в G:

вариант был

19 ребро L(G)

ребра {3,4}и{1,4} смежны в G:

вариант был

20 ребро L(G)

ребра {3,4}и{2,4} смежны в G:

U₅ соединена ребром с U₆

Определения

Срединный граф M(G) получается из графа G выполнением следующих операций:

• 
  новая вершина вставляется в каждое ребро графа G;
  
• 
  пары новых вершин соединяются ребрами в том случае, когда эти пары лежат на смежных ребрах графа.
  

Тотальный граф T(G) графа G строится следующим образом:

• 
  вершины T(G) являются объединением множества вершин и ребер графа G;
  
• 
  две вершины графа T(G) соединены ребром тогда и только тогда, когда соответствующие элементы графа G смежны или индидентны.
  

k-ой степенью G^kграфа G=(V,E) является граф с тем же множеством вершин V(G) и ребром между двумя вершинами тогда и только тогда, когда между ними имеется путь длиной самое большее k.