Сколько компонент связности в изображенных графах

Компонента связности графа

Компонента связности графа — некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.

Для ориентированных графов определено понятие сильной компоненты связности

Алгоритм

Для поиска компонент связности можно использовать поиск в ширину или поиск в глубину. При этом затраченное время будет линейным (относительно количества вершин и ребер).

См. также

• Связный граф
• Вполне несвязный граф
• Словарь терминов теории графов
• Компонента сильной связности в орграфе
• Теория перколяции

Ссылки

• Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).
• Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.

• Теория графов

Wikimedia Foundation . 2010 .

• Жадный алгоритм Радо — Эдмондса
• Связный граф

Полезное

Смотреть что такое «Компонента связности графа» в других словарях:

• Компонента сильной связности графа — Орграф называется сильно связным (strongly connected), если любые две его вершины сильно связаны. Две пары вершин s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Сильно связными… … Википедия
• Компонента — Компонент (от лат. componens, родительный падеж componentis составляющий) составная часть, элемент чего либо. В разных отраслях науки и техники может иметь дополнительное, более специфическое значение. В математике сложилось употребление в… … Википедия
• ГРАФА СВЯЗНОСТЬ — одна из топологических характеристик графа. Граф наз. связным, если для любых его вершин и н vсуществует цепь, соединяющая эти вершины. Числом вершинной связности графа G [обозначение ] наз. наименьшее число вершин, удаление к рых (вместе с… … Математическая энциклопедия
• ГРАФА АВТОМОРФИЗМ — изоморфное отображение графа на себя (см. Графов изоморфизм). Множество всех автоморфизмов данного графа образует группу относительно операции композиции автоморфизмов. Автоморфизмы графа Gпорождают группу подстановок вершин Г(G), наз. группой… … Математическая энциклопедия
• Компонента сильной связности в орграфе — Орграф называется сильно связным (англ. strongly connected), если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s.… … Википедия
• Связность графа — Связный граф граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует по крайней мере один путь. Содержание 1 Примеры применения 2 Связность для орграфов … Википедия
• Компонент — Компонента составная часть чего либо целого. В разных отраслях науки и техники может иметь дополнительное, более специфическое значение. В математике Компонента связности Компонента связности графа Компонента вектора или тензора, см.… … Википедия
• КС — Компонента связности графа Конституционный суд Контактная сеть Counter Strike Кубок Стэнли Корреспондентский счёт (к/с) Качугин, Солодовников (по другим данным Керосиновая смесь) Координационный совет Кран Самоходный (см. также Подъёмный кран#По… … Википедия
• Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия
• Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия

• Обратная связь: Техподдержка, Реклама на сайте

• �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,
WordPress, MODx.

• Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
• Искать во всех словарях
• Искать в переводах
• Искать в ИнтернетеИскать в этой же категории

Научный форум dxdy

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

Re: Число компонент связности
26.07.2018, 18:55

Заслуженный участник

Можете выписать определения компоненты связности и связного графа?
Re: Число компонент связности
26.07.2018, 19:27

Последний раз редактировалось gogoshik 26.07.2018, 20:14, всего редактировалось 5 раз(а).

Определение . Граф называется связным, если любые две его вершины можно соединить путем.

Определение . Компонента связности графа — некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.

Определение . Компонентой связности называется класс эквивалентности относительно связности.

Определение . Рассмотрим подграфы графа , порожденные множествами , т.е. для выполняется . Так как любые две вершины из связаны путем в , то этот путь будет связывать их и в . Следовательно, — связный граф. Нетрудно проверить, что множества образуют разбиение множества (возможен случай для некоторых , в этом случае — тривиальный) и для графа будет выполняться — дизъюнктное объединение графов . При этом подграфы называются компонентами связности графа .

Перечитал много раз и понял, что у данного графа будет одна компонента связности. Правильно?

Почему то сначала мне захотелось разбить граф на подмножества попарных вершин и соответствующих ребер. Получилось три ребра и три отдельные вершины. Я это принял за компоненты.

Поиск компонент связности

Понятие компоненты связности вытекает из понятия связности графа. Попросту говоря, компонента связности — часть графа (подграф), являющаяся связной. Формально, компонента связности — набор вершин графа, между любой парой которых существует путь.

Граф на иллюстрации содержит три компоненты связности, закрашенные разными цветами. Можно заметить, что даже одна вершина, изолированная от остального графа, составляет компоненту связности.

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

Алгоритм поиска компонент связности

Для поиска компонент связности используется обычный DFS практически без модификаций (можно использовать и BFS). При запуске обхода из одной вершины, он гарантированно посетит все вершины, до которых возможно добраться, то есть, всю компоненту связности, к которой принадлежит начальная вершина. Для нахождения всех компонент просто попытаемся запустить обход из каждой вершины по очереди, если мы ещё не обошли её компоненту ранее.

Реализация

Приведём два варианта реализации с разным способом хранения компонент связности.

Простейший вариант: просто заполнить массив \(comp\), где \(comp[i]\) — номер компоненты связности, к которой принадлежит вершина \(i\).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
#include  using namespace std; vectorint> graph[100000]; bool used[100000]; int comp[100000]; void dfs(int v, int c_num)  //c_num - номер текущей компоненты связности. used[v] = true; comp[v] = c_num; for (int u: graph[v])  if (!used[u])  dfs(u, c_num); > > > int main()  //Ввод графа. int c_num = 1; //Номер очередной компоненты. //Нумеровать можно как с 0, так и с 1, как вам удобнее. for (int i = 0; i  n; i++)  if (!used[i])  //если мы ещё не посетили эту вершину, обходя одну из предыдущих dfs(i, c_num); c_num++; > > for (int i = 0; i  n; i++)  cout  <"Vertex "  <i + 1  <" belongs to component "  <comp[i]  <endl; > > 
Другой вариант: явно хранить для каждой компоненты вектор из вершин, входящих в неё. Компоненты (векторы) хранить в векторе (из векторов).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
#include  using namespace std; vectorint> graph[100000]; bool used[100000]; vectorvectorint>> comps; void dfs(int v)  //информацию о компоненте в DFS больше передавать не нужно, //он просто будет добавлять вершины в последний вектор в comps. used[v] = true; comps.back().push_back(v); for (int u: graph[v])  if (!used[u])  dfs(u); > > > int main()  //Ввод графа. for (int i = 0; i  n; i++)  if (!used[i])  comps.push_back(vectorint>()); //добавляем в comps новый пустой вектор, //в который DFS будет записывать посещённые вершины. dfs(i); > > for (vectorint>& comp: comps)  cout  <"Component: "; for (int v: comp)  cout  <v + 1  <", "; > cout  <endl; > > 
brestprog
Сколько компонент связности в изображенных графах
 Примеры  решения задач из учебника  
Выделим компоненты связности ориентированного графа, изображенного на рис. 6. В данной задаче количество вершин n = 5.
 






Значит, для данного ориентированного графа матрица смежности будет иметь размерность 5×5 и будет выглядеть следующим образом
Найдем матрицу достижимости для данного ориентированного графа по формуле 1) из утверждения 3:
Таким образом, матрица сильной связности, полученная по формуле 2) утверждения 3, будет следующей:
Присваиваем p =1 и составляем множество вершин первой компоненты сильной связности D 1 : это те вершины, которым соответствуют единицы в первой строке матрицы S ( D ). Таким образом, первая компонента сильной связности состоит из одной вершины .
Вычеркиваем из матрицы S 1 ( D ) строку и столбец, соответствующие вершине v 1 , чтобы получить матрицу S 2 ( D ):
Присваиваем p =2. Множество вершин второй компоненты связности составят те вершины, которым соответствуют единицы в первой строке матрицы S 2( D ), то есть . Составляем матрицу смежности для компоненты сильной связности исходного графа D − в ее качестве возьмем подматрицу матрицы A ( D ), состоящую из элементов матрицы A , находящихся на пересечении строк и столбцов, соответствующих вершинам из V 2:
Вычеркиваем из матрицы S 2 ( D ) строки и столбцы, соответствующие вершинам из V 2 ,чтобы получить матрицу S 3 ( D ), которая состоит из одного элемента:






и присваиваем p =3. Таким образом, третья компонента сильной связности исходного графа, как и первая, состоит из одной вершины .
Таким образом, выделены 3 компоненты сильной связности ориентированного графа D :
 2.1. Компоненты сильной связности ориентированного графа 
 С помощью матрицы смежности найти компоненты сильной связности ориентированного графа D . 
C оставляем матрицу смежности A ( D ) размерности ( n − количество вершин) для данного ориентированного графа: она состоит из нулей и единиц, номера строк – индексы вершин , из которых исходят дуги, номера столбцов – индексы вершин, в которые дуги входят (если есть дуга, исходящая из вершины vi  и входящая в vj  , то элемент матрицы смежности, стоящий на пересечении i -той строки и j -того столбца равен 1, иначе – 0.).
Для того, чтобы выделить компоненты сильной связности, необходимо сначала найти матрицу достижимости T ( D ) ориентированного графа по первой формуле утверждения 3, затем находим матрицу сильной связности S ( D ) ориентированного графа (она должна быть симметрической) по второй формуле из того же утверждения.
 Алгоритм выделения компонент сильной связности  






1. Присваиваем p =1 ( p − количество компонент связности), .
2. Включаем в множество вершин Vp   компоненты сильной связности Dp  вершины, соответствующие единицам первой строки матрицы Sp  . В качестве матрицы A ( Dp  ) возьмем подматрицу матрицы A ( D ), состоящую из элементов матрицы A , находящихся на пересечении строк и столбцов, соответствующих вершинам из Vp  .
3. Вычеркиваем из Sp  строки и столбцы, соответствующие вершинам из Vp  . Если не остается ни одной строки (и столбца), то p - количество компонент сильной связности. В противном случае обозначим оставшуюся после вычеркивания срок и столбцов матрицу как Sp  +1  , присваиваем p = p +1 и переходим к п. 2.
 2.2. Расстояния в ориентированном графе 
С помощью алгоритма фронта волны найти расстояния в ориентированном графе D : диаметр, радиус и центры. 
Пусть ориентированный граф с n ³ 2 вершинами и v , w ( v ¹ w ) – заданные вершины из V .
 Алгоритм поиска минимального пути из в в ориентированном графе 






(алгоритм фронта волны).
1) Помечаем вершину индексом 0, затем помечаем вершины Î образу вершины индексом 1. Обозначаем их FW 1 ( v ). Полагаем k =1.
2) Если или k = n -1, и одновременно то вершина не достижима из . Работа алгоритма заканчивается.
В противном случае продолжаем:
3) Если , то переходим к шагу 4.
В противном случае мы нашли минимальный путь из в и его длина равна k . Последовательность вершин
есть этот минимальный путь. Работа завершается.






4) Помечаем индексом k +1 все непомеченные вершины, которые принадлежат образу множества вершин c индексом k . Множество вершин с индексом k +1 обозначаем . Присваиваем k := k +1 и переходим к 2).
· Множество называется фронтом волны k го уровня.
· Вершины могут быть выделены неоднозначно, что соответствует случаю, если несколько минимальных путей из в .
Чтобы найти расстояния в ориентированном графе, необходимо составить матрицу расстояний R ( D ) между его вершинами. Это квадратная матрица размерности , элементы главной диагонали которой равны нулю ( , i =1. n ).
Сначала составляем матрицу смежности. Затем переносим единицы из матрицы смежности в матрицу минимальных расстояний ( , если ). Далее построчно заполняем матрицу следующим образом.
Рассматриваем первую строку, в которой есть единицы. Пусть это строка − i -тая и на пересечении с j - тым столбцом стоит единица (то есть ). Это значит, что из вершины можно попасть в вершину за один шаг. Рассматриваем j -тую сроку (строку стоит вводить в рассмотрение, если она содержит хотя бы одну единицу). Пусть элемент . Тогда из вершины в вершину можно попасть за два шага. Таким образом, можно записать . Следует заметить, что если в рассматриваемых строках две или более единиц, то следует прорабатывать все возможные варианты попадания из одной вершины в другую, записывая в матрицу длину наикратчайшего из них.
 Примечание.  Самый длинный путь найти при помощи алгоритма фронта волны.






 Пример 
Найдем расстояния в ориентированном графе D , изображенном на рис. 7. В данной задаче количество вершин n = 7, следовательно, матрицы смежности и минимальных расстояний между вершинами ориентированного графа D будут иметь размерность 7×7.
 
Начинаем заполнять матрицу R ( D ) минимальных расстояний: сначала ставим нули по главной диагонали и rij  = aij  , если aij  =1, (т.е. переносим единицы из матрицы смежности). Рассматриваем первую строку. Здесь есть две единицы, то есть из первой вершины за один шаг можно попасть во вторую и шестую. Из второй вершины можно попасть за один шаг в третью (путь в первую вершину нас не интересует), следовательно, можно записать . Из шестой вершины можем добраться за один шаг в пятую и седьмую, а значит, , . Теперь ищем маршруты, исходящие из первой вершины, состоящие из 3 шагов: за 2 шага идем в третью вершину, оттуда за один шаг попадаем в четвертую, поэтому . В итоге получаем следующую матрицу:
Таким образом, диаметром исследуемого ориентированного графа будет .
Для каждой вершины заданного ориентированного графа найдем максимальное удаление (эксцентриситет) в графе G от вершины нее по формуле, которая была приведена выше : r ( vi  ) − максимальное из расстояний, стоящих в i -той строке. Таким образом,
 r ( v 1 )=3, r ( v 2 )=3, r ( v 3 )=5, r ( v 4 )=4, r ( v 5 )=2, r ( v 6 )=2, r ( v 7 )=3.
Значит, радиусом графа G будет






Соответственно, центрами графа G  будут вершины v 5 и v 6 , так как величины их эксцентриситетов совпадают с величиной радиуса .
Опишем теперь нахождение минимального пути из вершины v 3 в вершину v 6 по алгоритму фронта волны. Обозначим вершину v 3 как V 0 , а вершину v 6 - как W (см. рис. 8).
 
Множество вершин, принадлежащих образу V 0 , состоит из одного элемента - это вершина v 4 , которую, согласно алгоритму, обозначаем как V 1 : FW 1 ( v 3 )= < v 4 >. Поскольку искомая вершина не принадлежит фронту волны первого уровня , продолжаем работу алгоритма. Строим фронт волны второго уровня - это множество вершин, принадлежащих образу вершины V 1 : FW 2 ( v 3 )= < v 7 >, обозначаем v 7 ≡ V 2 . В образ вершины V 2 входят две вершины - v 5 и v 4 , но, так как v 4 уже была помечена как V 0 , то фронт волны третьего уровня состоит из одного элемента: FW 3 ( v 3 )= < v 5 >, v 5 ≡ V 3 . Из непомеченных вершин в образ вершины V 3 входят v 1 и v 2 , соответственно, FW 4 ( v 3 )= < v 1 , v 2 >, v 1 ≡ V 4 , v 2 ≡ V 4 . Теперь помечены все вершины, кроме v 6 , которая входит в образ вершины , то есть FW 5 ( v 3 )= < v 6 ≡ W >, работа алгоритма закончена. Минимальный путь (5 шагов) из вершины v 3 в вершину v 6 : v 3 v 4 v 7 v 5 v 1 v 6 .
 2.3. Минимальный путь в нагруженном ориентированном графе 
Найти минимальный путь в нагруженном ориентированном графе из вершины в вершину по методу Форда-Беллмана. 
Рассмотрим сначала общую задачу – нахождения минимального пути из вершины v  нач  в v  кон  .






Пусть D =( V , X ) – нагруженный ориентированный граф, V = < v 1 ,…, vn  >, n >1. Введем величины , где i =1,…, n , k =0,1,2,…, n – 1.
Для каждого фиксированного i и k величина равна длине минимального пути среди путей из v  нач  в vi  содержащих не более k дуг. Если путей нет, то .
Составляем матрицу длин дуг C ( D )=[ cij  ] порядка n :
 Утверждение . При i =2,…, n , k ³ 0 выполняется равенство
 Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном ориентированном графе  D  из  v   нач  в  v   кон  . ( v   нач  ≠  v   кон  ) 
записываем в виде матрицы, i - строка, k -столбец.
1) Составляем таблицу , i =1,…, n , k =0,…, n -1. Если , то пути из v  нач  в v  кон  нет. Конец алгоритма.






2) Если то это число выражает длину любого минимального пути из v  нач  в v  кон  . Найдем минимальное k 1 ³ 1, при котором . По определению получим, что k 1- минимальное число дуг в пути среди всех минимальных путей из v нач в v кон.
3) Затем определяем номера i 2 ,…, такие, что
то есть, восстанавливаем по составленной таблице и матрице стоимости искомый минимальный путь из v  нач  в v  кон  .
 Пример  
Найдем минимальный путь из вершины v 2 в v 6 в ориентированном нагруженном графе D , изображенном на рис. 9. В рассматриваемом графе количество вершин n = 7, следовательно, матрица длин дуг ориентированного графа D  будет иметь размерность 7×7.
Матрица длин дуг для рассматриваемого графа будет выглядеть следующим образом:
Согласно алгоритму, составляем таблицу стоимости минимальных путей из вершины v 2 в вершину vi  не более , чем за k шагов, k =0,… n -1 ( n =7, следовательно, k =0,…6). Как было определено выше, , и для всех остальных вершин vi   ≠ v 2 , то есть первый столбец таблицы состоит из элементов, равных , кроме элемента . Второй столбец таблицы повторяет вторую строку матрицы стоимости, поскольку представляет собой стоимость возможных путей из вершины v 2 за один шаг. Далее по формуле (3.1) находим по столбцам все оставшиеся элементы таблицы. Например, чтобы найти элемент , складываем элементы столбца и первого столбца матрицы стоимости и выбираем минимальное из получившихся чисел:






В конечном итоге получаем следующую таблицу:
Теперь необходимо по построенной таблице и по матрице C ( D ) восстановить минимальный путь из вершины v 2 в v 6 , который будет строиться с конца, то есть, начиная с вершины v 6. Для этого выбираем минимальное из чисел, стоящих в строке, соответствующей v 6 в таблице. Это число – 21 – длина минимального искомого пути. В первый раз такая длина была получена при количестве шагов, равном 4. В вершину v 6 мы можем попасть за один шаг из вершин v 1 и v 7 (длина соответствующих дуг 8 и 5 соответственно – данные из матрицы C ( D )). Выбираем минимальную по длине из этих дуг. Далее, в вершину v 7 можно попасть из v 4 и v 5 (длина соответствующих дуг 7 и 3 соответственно). Продолжая аналогичным образом, найдем искомый путь за 4 шага минимальной длины из вершины v 2 в v 6 : v 2 v 3 v 5 v 7 v 6 .
2.4. Эйлеровы циклы и цепи 
Найти Эйлерову цепь в неориентированном псевдографе . 
Исходя из утверждений 1 и 2, чтобы найти Эйлерову цепь, нужно соединить две вершины с нечетными степенями фиктивным ребром. Тогда задача сводится к нахождению Эйлерова цикла по приведенному ниже алгоритму. Из найденного цикла удаляется фиктивное ребро, тем самым находится искомая Эйлерова цепь.
 Алгоритм выделения эйлерова цикла в связном мультиграфе с четными степенями вершин 
1) Выделим из G цикл m 1 . (так как степени вершин четны, то висячие вершины отсутствуют). Положим l =1, G ¢ = G .






2) Удаляем из G ¢ ребра, принадлежащие выделенному циклу m 1 . Полученный псевдограф снова обозначаем как G ¢ . Если в G ¢ отсутствуют ребра, то переходим к шагу 4. Если ребра есть, то выделяем из G ¢ цикл m  l  +1 и переходим к шагу 3.
3) Присваиваем l := l +1 и переходим к шагу 2.
4) По построению выделенные циклы содержат все ребра по одному разу. Если l :=1, то искомый Эйлеров цикл найден (конец работы алгоритма). В противном случае находим циклы, содержащие хотя бы по одной общей вершине (в силу связности графа это всегда можно сделать). Склеиваем эти циклы. Повторяем эти операции, пока не останется один цикл, который является искомым.
 Пример  . 
Найдем Эйлерову цепь в неориентированном графе G , изображенном на рис. 10.
Прежде, чем приступать к нахождению Эйлеровой цепи, необходимо проверить степени вершин графа G − согласно утверждению 2, д ля существования Эйлеровой цепи, необходимо и достаточно, чтобы в графе G ровно 2 вершины нечетной степени.
В рассматриваемом графе нечетные степени имеют вершины v 3 и v 1 (степень этих вершин равна 3). Соединяя эти вершины фиктивным ребром так, как показано на рис. 11, получаем граф G ¢ :






 
Поскольку в конечном итоге будет получена цепь, то очевидно, что началом и концом этой цепи будут вершины с нечетными степенями. Поэтому, следуя описанному выше алгоритму, будем циклы m  i  так, чтобы хотя бы один из них начинался или кончался на вершинах v 3 или v 1 .
Пусть цикл m 1 составят ребра, проходящие через следующие вершины: v 3 v 4 v 7 v 6 v 1 v 2 v 3 . Согласно алгоритму, удаляем из G ¢ все ребра, задействованные в цикле m 1 . Теперь граф G ’ будет таким, как показано на рис. 12.
Составляем следующий цикл m 2 : v 4 v 5 v 6 v 2 v 5 v 7 v 4 . Граф G ¢ после удаления ребер, составляющих цикл m 2 , изображен на рис. 13.
 
 
Очевидно, что последний цикл m 3 будет состоять из v 3 v 5 v 1 | v 3 , где последнее ребро, соединяющее вершины v 1 и v 3 – фиктивно. После удаления ребер, составляющих цикл m 3 , в графе G ¢ не останется ни одного ребра.






Теперь по общим вершинам склеиваем полученные циклы. Поскольку m 1 и m 2 имеют общую вершину v 4 , то, объединяя их, получим следующий цикл: v 3 v 4 v 5 v 6 v 2 v 5 v 7 v 4 v 7 v 6 v 1 v 2 v 3 . Теперь склеим получившийся цикл с циклом m 3 : v 3 v 4 v 5 v 6 v 2 v 5 v 7 v 4 v 7 v 6 v 1 v 2 v 3 v 5 v 1 | v 3 . Удаляя фиктивное ребро, получаем искомую Эйлерову цепь: v 3 v 4 v 5 v 6 v 2 v 5 v 7 v 4 v 7 v 6 v 1 v 2 v 3 v 5 v 1 .
2.5. Минимальное остовное дерево 
 Найти минимальное остовное дерево в неориентированном нагруженном графе. 
 Алгоритм выделения минимального остовного дерева в неориентированном нагруженном графе  G  
1) Выберем в графе G ребро минимальной длины. Вместе с инцидентными ему двумя вершинами оно образует подграф G 2 графа G . Положим i:=2.
2) Если i = n ( G ), то задача решена и Gi  – искомое минимальное остовное дерево графа G . Иначе переходим к шагу 3).
3) Строим граф Gi  +1 . Для этого добавим к графу Gi  новое ребро минимальной длины из оставшихся , которое инцидентно какой-либо вершине графа Gi  и одновременно вершине, не содержащейся в Gi  . Вместе с этим ребром включаем в Gi  +1 и эту инцидентную ему вершину. Присваиваем i := i +1 и переходим к шагу 2).
 Пример  . 
Найдем минимальное остовное дерево в неориентированном нагруженном графе, изображенном на рис.14.
Обозначим ребро, соединяющее вершины vi  и vj  через xij  .
Для удобства использования приведенного выше алгоритма решения поставленной задачи, составим матрицу длин ребер. В рассматриваемом графе количество вершин n = 8, следовательно, матрица длин ребер графа G будет иметь размерность 8× 8 и выглядеть следующим образом:
Согласно приведенному выше алгоритму, выбираем ребро минимальной длины (выбираем среди элементов матрицы C ( G ), минимальное − это c 47 =1) и вместе с инцидентными ему двумя вершинами относим к графу G 2 . Таким образом, . Длина дерева G 2 будет равна l ( G 2 )= c 47 =1. Поскольку , продолжаем работу алгоритма. По четвертой и седьмой строкам ищем минимальное число (за исключением использованной единицы) − ребро минимальной длины, инцидентное либо вершине v 4 , либо v 7 . Выбираем ребро x 46 с длиной c 46 =3 и вместе с вершиной v 6 добавляем к графу G 2 , обозначая его теперь как G 3 : , при этом l ( G 3 )= c 47 + c 46 =1+3=4. Аналогично находим графы :
Поскольку i =8= n ( G ), работа алгоритма заканчивается.
Таким образом, искомое минимальное остовное дерево графа G − граф G 8 , изображенный на рис. 15, длина которого равна 22.
 
2.6. Задача о коммивояжёре 
Найти в нагруженном неориентированном графе гамильтонов цикл минимального веса. 
Эта задача имеет практическую интерпретацию, благодаря которой и получила своё название: коммивояжёр (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,3.. n и вернуться в первый город. Стоимости проезда между городами известны. В каком порядке следует объезжать города, чтобы замкнутый путь (тур) коммивояжера был наименее затратным?
Сформулируем задачу в терминах теории графов, введя следующие обозначения: пусть D =[ V , X ] – полный ориентированный граф и f : X ® - весовая функция, V = < v  1  , v  2  ,…, vn  > – множество вершин, X – множество дуг, C = < cij  >, i , j =1,2… n – весовая матрица данного ориентированного графа, то есть с  ij  = f ( v  i  , vj  ), причем для любого i справедливо cii  = ¥ . Требуется найти простой остовной ориентированный цикл (или «цикл коммивояжёра») минимального веса.
Следует заметить, что требование полноты ориентированного графа (наличие дороги из любого города в любой) можно опустить. Однако в этом случае гамильтонов цикл может и не существовать (по теореме, для его существования достаточна полнота орграфа). Следовательно, описываемый метод ветвей и границ приведёт к полному перебору всех вариантов незаконченных циклов прежде, чем станет очевиден факт отсутствия решения.
Очевидно, cij  следует трактовать как стоимость проезда из города i в город j . Допустим, что добрый мэр города j издал указ выплачивать каждому въехавшему в город коммивояжеру $5. Это означает, что любой тур подешевеет на $5, поскольку в любом туре нужно въехать в город j . Но поскольку все туры равномерно подешевели, то прежний минимальный тур будет и теперь стоить меньше всех. Добрый же поступок мэра можно представить как уменьшение всех чисел j -го столбца матрицы M на 5. Если бы мэр хотел спровадить коммивояжеров из j -го города и установил награду за выезд в размере $10, это можно было бы выразить вычитанием 10 из всех элементов j - й той строки. Это снова бы изменило стоимость каждого тура, но минимальный тур остался бы минимальным. Итак, доказана следующая лемма.
 Вычитая любую константу из всех элементов любой строки или столбца матрицы C , мы оставляем минимальный тур минимальным. 
В этой связи введем следующие термины. Пусть имеется некоторая числовая матрица. Привести строку этой матрицы означает выделить в строке минимальный элемент (его называют константой приведения) и вычесть его из всех элементов этой строки. Очевидно, в результате в этой строке на месте минимального элемента окажется нуль, а все остальные элементы будут неотрицательными. Аналогичный смысл имеют слова «привести столбец матрицы».
Привести матрицу по строкам означает, что все строки приводятся. Аналогичный смысл имеют слова «привести матрицу по столбцам». Приведение матрицы означает сначала приведение этой матрицы по строкам, а затем по столбцам.
Если с помощью приведённой матрицы удастся построить такую последовательность переходов по городам (по вершинам графа), которым соответствует последовательность нулевых элементов приведенной матрицы, то ясно, что для этой матрицы мы получим минимальный тур. Но он же будет минимальным и для исходной весовой матрицы С , только для того, чтобы получить правильную стоимость тура, нужно будет прибавить все константы приведения. Таким образом, сумма констант приведения играет роль оценки снизу для стоимости всех туров.
 Весом элемента матрицы  называют сумму констант приведения матрицы, которая получается из данной матрицы заменой обсуждаемого элемента на ¥ . Следовательно, слова «самый тяжёлый нуль в матрице» означают, что в матрице подсчитан вес каждого нулевого элемента, а затем фиксирован нуль с максимальным весом.
Продемонстрируем теперь метод ветвей и границ для решения задачи о коммивояжёре.
Пусть требуется найти легчайший простой остовной ориентированный цикл в полном взвешенном ориентированном графе на пяти вершинах, со следующей весовой матрицей C :


Похожие публикации:

Доказать что скользящая симметрия имеет единственную инвариантную прямую
Индикаторное устройство st1000 st2000 как снять показания
Как поменять цвет пнг картинки в фотошопе
Как посмотреть трафик интернета на компьютере windows 10