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

Операции над графами G(V , E )  GV  a, E  1) Добавление к графу G(V, E) вершины a G(V , E )  GV  a, b, E  a, b 2) Добавление к графу G(V, E) ребра (a, b) 3) Удаление из графа G(V, E) вершины a вместе с инцидентными ей ребрами G(V , E )  GV \ a, E \ b, c  | b  a  c  a 4) Удаление из графа G(V, E) ребра (a, b) G(V , E )  GV , E \ a, b G : V (G)  V (G)  с E (G)  E (G) /(a, b)  a, c , c, b 5) Подразделение ребра (a, b) графа G(V, E) 6) Дополнение графа G(V, E) (a, b)  E (G )  (a, b)  E (G) 2 4 1 G : V (G)  V (G ) 7) Объединение графов G1(V1,E1) и G2(V2,E2) G  G1  G2 : V (G)  V1  V2 E (G)  E1  E2 8) Пересечение графов G1(V1,E1) и G2(V2,E2) G  G1  G2 : V (G)  V1  V2 G K4 G 6 E (G)  E1  E2 1 2 1 2 3 G1 3 4 2 1 G2 4 3 7 5 G1  G2 1 2 G1  G2 4 8 9 9) Кольцевая сумма графов G1(V1,E1) и G2(V2,E2) G  G1  G2 : E (G)  E1  E2  E1 \ E2   E2 \ E1  V (G)  V1  V2 10) Соединение графов G1(V1,E1) и G2(V2,E2) E (G)  E1  E2  a, b | a V1, b V2 , a  b G  G1  G2 : V (G)  V1  V2 11) Произведение графов G1(V1,E1) и G2(V2,E2) G  G1  G2 : V (G)  V1  V2  a, b | a V1, b V2 a1, b1, a2 , b2   E(G)  b1  b2 & a1, a2   E(G1)  a1  a2 & b1, b2   E(G2 ) 14) Композиция графов G1(V1,E1) и G2(V2,E2) 1 3 1 E  E  V 2 E  E  V 2 G(V , E) : V   V G(V , E) : V   V 12) Подграф графа G(V, E) 13) Часть графа G(V, E) G  G1G2  : V (G)  V1  V2 a1, b1, a2 , b2  E(G)  a1, a2  E(G1)  (a1  a2 & (b1, b2 )  E(G2 )) 2 4 2 2 G1 4 1 2 1 2 1 2 3 G1 3 4 3 4 2 4 3 G2 4 1 G2 G1  G2 G1  G2 Клика – максимальный полный подграф (1,4) (1,1) (2,4) (2,1) (3,4) (1,2) (2,2) (3,1) (3,2) G1  G2 Некоторые типы графов  (On )  (On )  0 1) On – вполне несвязный граф порядка n 2) K n – полный граф порядка n n(n  1) m 2 K4 3) Pn – простая цепь длины n-1 4) Сn  ( K n )  ( K n )  n  1 K5 P4 – простой цикл (n>2) 5) G - двудольный граф С5 V (G)  V1  V2 V1  V2   V1 - подмножество несмежных вершин V2 - подмножество несмежных вершин K 2,3 K3,3 6) K1, n  S n 1 – звезда S6 7) Wn 1 – колесо W6 лес - неорграф без циклов Дерево – связный ациклический граф укладка компонента связности леса- дерево. корень Остов графа G(V, E) – часть G(V , E) : V  V  G - лес, образующий дерево на любой компоненте связности графа G (стягивающее дерево, каркас, остовное дерево) 2 2 7 1 3 7 1 3 8 6 8 6 9 5 4 9 5 4 Ребра остовного дерева - ветви 2 Удаленные ребра графа - хорды 7 1 3 Цикломатическое число графа  (G)  m  n  c  (G)  11  9  2  4 8 6 5 4 9 Метод поиска в глубину 1) Начинаем с фиксированной вершины a0. 2) Рассматриваем вершину, смежную выбранной, если их нет, то возвращаемся к предыдущей вершине. 3) Поиск заканчивается при возврате в a0 и отсутствии смежных ей еще не рассмотренных вершин 1 V3  {1, 2,3, 4,5, 6} 2 1 2 3 4 5 6 V2  {1, 2,3, 4,5, 6} 2 2 1 2 3 4 1 1 V1  {1, 2,3, 4,5, 6} 3 6 3 4 5 6 2 3 1 6 3 6 6 5 4 5 6 4 2 5 Метод поиска в ширину 6 3 1) Начинаем с фиксированной вершины a0. 4 2) Рассматриваем все вершины, смежные выбранной. V  V1  V2  V3 V1 - подмножество просмотренных и обработанных вершин V2 - подмножество просмотренных, необработанных вершин V3 - подмножество не помеченных вершин 5 Алгоритм поиска остова минимального веса Алгоритм Краскала e1 - ребро минимального веса 1) Строим граф T1(V , e1) i) Из графа Ti (V , i  n  c) строим Ti 1 Ei 1  Ei  ei 1 ei 1- ребро минимального веса, не принадлежащее Ti и не образующее циклов с его ребрами 2  1 5 3 3 1 4  1 2 3 2  3 4 4 3 6 1 2  2  1 5 1 2 6 Алгоритм Прима Дерево строится добавлением ребер минимального веса, одна вершина которых принадлежит дереву, другая нет 2  Массив меток вершин 1) 1,2,3,4,5,6 2) 1,5 1,2,3,4,1,6 3) 2,6 1,2,3,4,1,2 4) 1,6 1,1,3,4,1,1 5) 2,4 1,1,3,1,1,1 6) 3,6 1,1,1,1,1,1 Возникающие задачи: 1) Число остовных деревьев = = алгебраическому дополнению матрицы 3 K  D  A - матричная формула Кирхгофа 1 2 3 0, i  j , Матрица степеней вершин: Dij   6 deg ai , i  j 2) Перечислить все остовные деревья. 4 2  1 5 1 Проблема: проверка, образует ли ребро цикл? 3 3  (G)  9  6  1  4