Связность в орграфе. Исследование маршрутов . Покрытия и независимость

Связность Вершинная связность  (G) - наименьшее количество вершин, удаление которых нарушает связность  (G)  1 Точка сочленения – вершина, удаление которой нарушает связность (4,5,8) Блок – связный граф без точек сочленения Реберная связность  (G) - наименьшее количество ребер, удаление которых нарушает связность  (G)  1 Мост - ребро, удаление которой нарушает связность (7,8) (5,6)  (G)  k - k –связный граф  (G)  k - реберно k –связный граф  (G)   (G)   (G) Теорема. 1 3 7 2 1 2 1 блоки: 4 5 6 4 3 5 9 8 Метод нахождения блоков 1) Найти все точки сочленения. 6 2 G1 3 4 … 2) При поиске в глубину, возвращаясь через точку сочленения, получаем блок. 4 5 5 G2 9 6 8 7 8 G3 G4 Связность в орграфе Вершины u и v сильно связаны, если существуют ориентированные цепи (u,v) и (v, u) Вершины u и v односторонне связаны, если существует только одна из цепей. Вершины u и v слабо связаны, если они связаны в графе, полученном отменой ориентации. Связный орграф Сильно связный орграф Сильная связная компонента – максимальный сильно связный подграф 4 3 Вершина v достижима из вершины и если существует ориентированная (u,v) цепь.  1, если a j достижима из ai Rij    0, если a j не достижима из ai - матрица достижимости (матрица связности) 1 2 3 1 SR   5 1, если ai достижима из a j Q  RT Qij   01  0, если ai не достижима из a j 01 1 - матрица контрдостижимости 01 01 2 Q  1 1 3 1 1 S  Q * R - матрица сильных компонент 4 1 2 3 4 1 1 1 1 01 2 1 1 1 01 3 1 1 4 0 0 5 0 0 1 5 4 2 5 1 2 3 4 5 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 5 1 1 1 1 1 1 2 3 4 5 6 7 1 2 3 R 4 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 6 7 1 2 3 Q 4 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 6 0 0 0 1 0 1 1 7 0 0 0 1 0 1 1 6 1 1 1 1 1 1 1 7 1 1 1 1 1 1 1 1 2 3 4 5 6 7 1 2 5 3 4 6 7 1 2 3 S 4 5 1 1 1 1 1 1 1 1 1 1 1 1 1 6 0 0 0 1 0 1 1 7 0 0 0 1 0 1 1 1 2 5 SП  3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 6 0 0 0 0 1 1 1 7 0 0 0 0 1 1 1 База графа – минимальное множество вершин, из которого достижима любая вершина графа 1 5 2 3 6 7 4 Исследование маршрутов k Теорема. Элемент (i, j ) матрицы AG - число (i, j ) маршрутов длины k 4 3 5 1 2 A 1 2 3 4 5 1 2 3 4 5 1 0 0 1 0 0 1 0 1 0 1 0 2 1 0 0 0 0 3 0 1 0 1 0 5 0 0 0 1 0 5 0 0 0 0 1 1 1 0 0 0 1 A  A A 3 1 0 0 1 1 4 0 0 0 1 0 1 2 3 4 5 2 2 0 0 1 0 0 4 0 0 0 0 1 маршруты длины 1 3 A2  2 0 1 0 1 0 3 0 0 1 1 0 4 0 0 0 0 1 5 0 0 0 1 0 маршруты длины 3 (2,4)  (2,3)(3,4)  (2,1)(1,3)(3,4) маршруты длины 2 [bij ]  E  A  A2  A3  ...  An 1, если bij  0 Rij   0, если bij  0 - Матрица достижимости (связности) Покрытия и независимость Вершина графа покрывает инцидентные ей ребра Ребро графа покрывает инцидентные ему вершины Число вершинного покрытия - минимальное число вершин, покрывающих все ребра  0 (G) Число реберного покрытия - минимальное число ребер, покрывающих все вершины 1(G) Независимое множество вершин – множество взаимно несмежных вершин Вершинное число независимости – наибольшее число вершин в независимом множестве 0 (G) Независимое множество ребер – множество взаимно несмежных ребер (паросочетание) Реберное число независимости – наибольшее число ребер в независимом множестве 1(G) Совершенное паросочетание – является реберным покрытием Теорема. Для любого связного графа справедливо: 0 (G)  0 (G)  1(G)  1(G)  n 2 7 1(G)  4 0 (G)  4 1,2,5,7 3 6  (G)  3 1(G)  3 3,4,6 4 1 5 (1,2), (1,3), (4,5), (5,6) (1,3), (2,4), (6,7) Клика – полный подграф Максимальная клика – не содержится в другой клике Наибольшая клика – содержит наибольшее число вершин – кликовое число (плотность графа)  (G) 2 G 2 1 Максимальные клики: 1 5 G 4 {2,3,5} {1,5} {1,4} 3 5 4 3 Независимые множества вершин: {1,4} {1,5} {2,3,5} 2 1 4 3 6 5 8 7 (1,2), (3,4), (5,6), (7,8) - совершенное паросочетание Если в Gn ,n n1  n2, то любое паросочетание, 1 2 покрывающее V1 или V2 , является совершенным. Теорема. В двудольном графе: 1   0  4 Следствие. Для произвольной бинарной матрицы максимальная мощность множества единиц из которого никакие две не лежат на одной линии равно минимальному числу линий, которым можно покрыть все единицы 1  1 A  0 0 1 0 0  0 1 0 0 0 1 0 0  1 1 1 1  1 i  4 1 j  5 1 2 1 2 3 3 4 4 5 Максимальное множество единиц из которого никакие две не лежат на одной линии - максимальное паросочетание Минимальное число линий, покрывающих единицы – минимальное вершинное покрытие Алгоритм нахождения наибольшего паросочетания в двудольном графе 1) Строим произвольное паросочетание М 1 1 {1} V1 {3,5} V2 - свободны от М 3 4 2) Находим чередующуюся цепочку, начинающуюся в свободной вершине V1 и заканчивающаяся в свободной вершине V2 {(1,4), (4,4), (4,2), (2,3), (3,3)} 4 5 3) Меняем ребра цепочки – получаем паросочетание M1. 2 2 3 4) Паросочетание М является наибольшим тогда и только тогда когда не существует чередующейся цепочки относительно этого паросочетания. Построение чередующейся цепочки - метод поиска в глубину с ограничениями Задача о назначениях поиск в реберно-взвешенном графе совершенного паросочетания с минимальным весом (оптимального паросочетания) Свойства оптимального паросочетания nm 1. Если веса всех ребер, инцидентных одной и той же вершине уменьшить или увеличить на одно и то же число, то оптимальное паросочетание останется оптимальным 2) Если паросочетание построено на вершинах V1  V1 и V2  V2, то оно не изменится при следующем преобразовании весов ребер: W  V1 V1 \ V1 V2 V2 \ V2 d d d d не изменяем 3) Если веса всех ребер неотрицательны и некоторое совершенное паросочетание состоит из ребер нулевого веса, то оно - оптимальное Алгоритм поиска оптимального паросочетания 0 0 W  -2 2  1 4 4 1  1) Изменяем веса ребер так, чтобы у каждой 7 2 7  вершины было хотя бы одно инцидентное ребро  6 4 6 нулевого веса (свойство1).  5 0 0 -4 0 0 W  0  1 0 4 1 3 2 7  0 2 4  1 0 0 2) Формируем паросочетание М с 1 нулевым весом 2 2 3) Проверяем М на совершенство. Если оно совершенное, то работа 3 3 алгоритма завершена. 4 4 2V  M 4V2  M 1 1 0 4 4 1  4) Ищем чередующуюся цепь с нулевым весом. 0 7 2 7  {(2,1), (1,1), (1,2), (2,3), (3,1)}  W  2 6 4 6 5) Если цепь найдена, изменяем   паросочетание, переходим на шаг 3 1 5 0 0  Если цепь не найдена переходим на шаг 6 p=1+0+6+0=7 1 1 6) Изменяем веса ребер по утверждению 2, переходим на шаг 4. 1 {(2,1), (1,1), (1,4)} 0 0 3 0 V1  {2,1,3} V2  {1,2} 0 3 1 6 2 5) Цепь найдена, изменяем   W 0 0 1 3 паросочетание, переходим на шаг 3 3   2 2 0 0 3) Паросочетание совершенное. 4 1 2 3 4 Теорема. Наименьшее число вершин, разделяющих несмежные вершины u и v равно наибольшему числу вершинно-непересекающихся простых (u,v) цепей. (основная теорема о связности графа) Q - множество вершинно-непересекающихся цепей S - число вершин, разделяющих вершины u и v max Q  min S Теорема Уитни. Граф k-связен тогда и только тогда когда любая пара его несмежных вершин соединена по крайней мере k непересекающимися цепями. Теорема Менгера. Наибольшее число реберно-непересекающихся цепей, соединяющих несмежные вершины графа равно наименьшему числу ребер, разделяющих эти вершины.