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

[GaLL]

In graph theory, a graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.

Треугольник (K₃) - двусвязный (2-edge-connected) граф.
Кажется, я решил эту задачу, но доказательство получилось не очень красивое.

[RawonaM]

Думаю я понял, что значит "k-edge-connected". Это значит, что каждая вершина связана как минимум k-egd-aми со всеми другими вершинами, то есть если убрать к-1 ребер от этой вершины (т.е. оставить только одну), то граф все еще будет связаным.

[GaLL]

Какое бы разбиение вершин графа на два множества мы ни взяли, будут хотя бы k рёбер, каждое из которых соединяет пару вершин из разных множеств.

[RawonaM]

Какое бы разбиение вершин графа на два множества мы ни взяли, будут хотя бы k рёбер, каждое из которых соединяет пару вершин из разных множеств.

Ага, так понятнее, спасибо. Действительно, это получается как бы "k мостов" между двумя компонентами.

[RawonaM]

Кажется, я решил эту задачу, но доказательство получилось не очень красивое.

И как вы доказали?
Роббинс в 1939 г доказал через разложение уха. (wiki/en) Ear_decomposition
Ничего проще я не могу придумать.

[RawonaM]

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

[Bhudh]

Роббинс в 1939 г доказал через разложение уха.

Таким переводом надо рассказ Кинга называть...

[RawonaM]

Пожалуйста, проследите за логикой, есть ли ошибки:

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

Дан базовый граф G. Запускаем DFS ((wiki/en) Depth-first_search) с любой вершины, допустим с V1.
Если DFS выдал больше, чем одно дерево, ответ отрицательный.
Если одно, то мы получили пути от V1 ко всем листьям дерева.
Убираем с графа G все ребра, которые присутствуют на дереве DFS.
Снова запускаем DFS с вершины V1. Если в результате на одном дереве присуствуют все листья с предыдущего DFS дерева, то мы нашли по два независимых путя* от любой вершины к другой, если нет, то этого невозможно сделать и ответ отрицательный.

*Э-э, не уверен насчет этой формы слова. Может пути?

[GaLL]

Возьмём граф с вершинами a, b, c, d, e и рёбрами ab, bd, de, ae, bc, cd. Из него легко сделать сильно связный ориентированный, т. к. в нём есть гамильтонов цикл. DFS находит дерево в виде пути abde и ребра cd (конечно, возможны другие деревья DFS'а, это получается, если рассматривать вершины в алфавитном порядке, получится именно такое). Исходный граф минус дерево DFSа - это рёбра ae, bc. c - лист дерева DFSа, но пути до него по оставшимся рёбрам нет.

[GaLL]

Моё решение:

Допустим сначала, что исходный граф несвязный. Тогда, очевидно, сделать его сильно связным, установив направление рёбрам, нельзя.
Допустим теперь, что он связный и с мостом ab. Тогда невозможно выполнить данные условия, поскольку либо не будет пути из a в b, либо из b в a.
Рассмотрим теперь связный граф без мостов, т. е. двусвязный граф. Возьмём какое-нибудь дерево DFS'а и назначим его рёбрам направление в ту сторону, в какую совершался обход этим самым DFS'ом. Остальным рёбрам назначим направление также в соответствии с DFS'ом: если ребро ab было в первый раз найдено, когда DFS находился в вершине a, но направление ребра будет a->b. Ребро не принадлежит дереву DFS'а (далее дерево DFS'а буду обозначать D) тогда и только тогда, когда b - уже пройденная вершина. Важным свойством таких рёбер является то, что b обязательно лежит где-то на пути от корня D до вершины a (это следует из того, что именно вершины, образующие путь от корня до текущей вершины, находятся в данный момент в стэке DFS'а; когда у вершины просмотрены все рёбра, выходящие из неё, она извлекается из стэка; следовательно, тот факт, что ребро ab в первый раз обнаружено именно из вершины a, говорит о том, что вершина b просмотрена ещё не полностью, т. е. лежит в стэке). Назовём такие рёбра обратными. Итак в графе все рёбра получили ориентацию, и каждое ребро либо принадлежит D, либо является обратным.
Теперь рассмотрим произвольное ребро дерева DFS'а ab (a->b). Обозначим множество вершин поддерева дерева DFS'а с корнем в b как B (т. е. множество вершин, достижимых из b по рёбрам D, включая и саму вершину b). Множество остальных вершин графа обозначим как A. Если взять разбиение вершин на эти два множества, то, поскольку граф двусвязный, обязательно должно быть хотя бы два различных ребра, у каждого из которых пара вершин принадлежит разным множествам. Для A и B одним таким ребром будет ab, другое назовём cd, где c принадлежит A, d принадлежит B (причём возможно, что a=c или b=d). Понятно, что cd - обратное ребро. Значит, его направление  - из d в c, поскольку вершина c была пройдена раньше. Более того, по вышеприведённому свойству обратных рёбер по рёбрам из D есть путь из c в d. Этот путь обязательно должен проходить через ребро ab, ведь это единственное ребро из D, соединяющее множества A и B. Следовательно, существует путь из c в a. Итак,
1) существует путь из b в d (ведь d принадлежит множеству B);
2) ребро cd с направлением d->c;
3) путь из c в a.
Стало быть, есть путь по ориентированным рёбрам из b в a. Поскольку ab - произвольное ребро D, значит, можно попасть из любой вершины графа в любую другую.
Итак, критерий (в данном случае - достаточное и необходимое условие) того, что из неориентированного графа можно сделать сильно связный, задав каждому ребру направление -  его двусвязность.

[RawonaM]

Ага, понятно.

Мне нужно было алгоритм придумать, который определяет, можно сориентировать граф или нет. Я решил, что с двусвязностью алгоритм получается слишком неэффективный. Вы мой алгоритм не читали или ничего не понятно?

[GaLL]

Ага, понятно.

Мне нужно было алгоритм придумать. Я решил, что с двусвязностью алгоритм получается слишком неэффективный. Вы мой алгоритм не читали или ничего не понятно?

Читал, но к нему легко подобрать контрпример, см. выше.

[RawonaM]

Читал, но к нему легко подобрать контрпример, см. выше.

Действительно. Щас подумаю как надо исправить.

[RawonaM]

Значит нужно изменить так:

Дан базовый граф G. Запускаем DFS с любой вершины, допустим с V1.
Если DFS выдал больше, чем одно дерево, ответ отрицательный.
Если одно, то даем всем ребрам, которые присутствуют на дереве DFS, ориентацию от листьев к корню, а остальным (добавив их на дерево DFS) наоборот.
Снова запускаем DFS с вершины V1. Если в результате на одном дереве присуствуют все вершины, то мы нашли по два независимых путя* от любой вершины к другой, если нет, то этого невозможно сделать и ответ отрицательный.

Теперь должно работать

[GaLL]

Вы имеете в виду алгоритм проверки графа на возможность сделать из него сильно связный ориентированный? Я думал, вопрос в задаче - каков критерий того, что это можно сделать.
Если же рассматривать вопрос об алгоритме проверки, то, как показано выше, достаточно проверить граф на двусвязность, т. е. связность и отсутствие мостов. Это можно сделать за один DFS. Ваш алгоритм, конечно, тоже работает за O(E), но проверка на мосты с помощью одного DFS'а может быть сделана путём добавления меток только вершинам, а не рёбрам, что требует лишь O(V) дополнительной памяти.

[RawonaM]

Вы имеете в виду алгоритм проверки графа на возможность сделать из него сильно связный ориентированный? Я думал, вопрос в задаче - каков критерий того, что это можно сделать.

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

Если же рассматривать вопрос об алгоритме проверки, то, как показано выше, достаточно проверить граф на двусвязность, т. е. связность и отсутствие мостов. Это можно сделать за один DFS. Ваш алгоритм, конечно, тоже работает за O(E), но проверка на мосты с помощью одного DFS'а может быть сделана путём добавления меток только вершинам, а не рёбрам, что требует лишь O(V) дополнительной памяти.

А как одним DFS-ом проверить на мосты?
Ну и потом, чтобы идти этим путем нужно сначала доказывать, что действительно такое условие, а это несколько нудное доказательство

[GaLL]

А как одним DFS-ом проверить на мосты?

1) В процессе ДФСа каждой вершине присваиваем номер в каком порядке их этот ДФС обходит. Корень - №1, первая попавшаяся вершина, связанная ребром с корнем - №2 и т. д.
2) Кроме того, каждой вершине даём ещё одну метку L - минимальный номер вершины, достигнутой ДФСом из этой вершины (в том числе при обработке обратного ребра; при этом важно не обработать ребро дерева ДФСа как обратное; для этого достаточно в качестве параметра рекурсивной функции ДФСа использовать не только текущую вершину, но и предыдущую).
3) Если в процессе ДФСа мы идём по ребру из вершины a в вершину b по ребру ab (не обратному, т. е. в вершину b при этом попадаем в первый раз), и оказывается, что L[a] < L, то ab - мост.

Ну и потом, чтобы идти этим путем нужно сначала доказывать, что действительно такое условие, а это несколько нудное доказательство

Да оно, в общем-то, простое, это я его старался сделать подробнее. Частенько простые алгоритмы основываются на довольно длинных доказательствах. Вы видели доказательство верности алгоритма Флойда (длины кратчайших путей между всеми парами вершин графа)?
К тому же, чтобы убедиться в том, что Ваш алгоритм говорит "нет" тогда и только тогда, когда граф не может быть преобразован в сильно связный, нужно всё равно проделать подобное доказательство.

[RawonaM]

А как одним DFS-ом проверить на мосты?

1) В процессе ДФСа каждой вершине присваиваем номер в каком порядке их этот ДФС обходит. Корень - №1, первая попавшаяся вершина, связанная ребром с корнем - №2 и т. д.
2) Кроме того, каждой вершине даём ещё одну метку L - минимальный номер вершины, достигнутой ДФСом из этой вершины (в том числе при обработке обратного ребра; при этом важно не обработать ребро дерева ДФСа как обратное; для этого достаточно в качестве параметра рекурсивной функции ДФСа использовать не только текущую вершину, но и предыдущую).
3) Если в процессе ДФСа мы идём по ребру из вершины a в вершину b по ребру ab (не обратному, т. е. в вершину b при этом попадаем в первый раз), и оказывается, что L[a] < L, то ab - мост.

Что-то я не понял, как это происходит. Еще и это доказывать надо будет!

[RawonaM]

Частенько простые алгоритмы основываются на довольно длинных доказательствах. Вы видели доказательство верности алгоритма Флойда (длины кратчайших путей между всеми парами вершин графа)?

Неа, не видел.

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

Думаете? Я сначала тоже так думал, потом я вроде как доказал это намного короче.
Вроде как частично я изложил это выше. Щас попробую изложить более внятно.

[GaLL]

Что-то я не понял, как это происходит. Еще и это доказывать надо будет!

Любой алгоритм требует доказательства. Здесь доказательство примерно такое такое же, как для критерия.
Я там ошибся немного, надо не L[a] < L, а num[a] < L, где num - номер вершины, присваеваемый ДФСом. Рекурсию можно сделать, например, так:

// вначале все num и count равны нулю
void DFS(int a, int prev) // a - текущая вершина ДФСа, prev - предыдущая; у корня, то есть при стартовом запуске этой функции, prev равен, например, -1
{
   num[a] = L[a] = ++count;
   for ( b принимает значения всех вершин, соединённых с a ребром )
   {
      if (b == prev)
         continue;
      if (!num)
      {
         // DFS ещё не был в вершине b
         DFS(b, a);
         // теперь значение L установлено и больше меняться не будет
         if (num[a] < L)
            printf("bridge: %d %d\n", a, b);
         if (L[a] > L)   L[a] = L;
      }
      else // обратное ребро
      {
         if (L[a] > num)   L[a] = num;
      }
   }
}

[RawonaM]

Что-то я не понял, как это происходит. Еще и это доказывать надо будет!

Любой алгоритм требует доказательства. Здесь доказательство примерно такое такое же, как для критерия.

В таком случае придется доказывать и критерий и это Я пытаюсь сэкономить на писанине и доказательствах.

В книге A first look at graph theory доказательство двусвязности заняло больше страницы мелкого текста.

Меня не покидает ощущение, что эта задача решается гораздо проще. Может я ошибаюсь.

[RawonaM]

Тут в книге задача, не пойму каким образом она относится к теме.

Допустим дан некий связной граф G. Определим граф H так: вершины будут составлять все остовные деревья графа G, а две вершины T и T' соединены iff они отличаются только одной гранью (т.е. в T' есть одна грань, которой нет в T, и следовательно наоборот). Верно ли, что для любого связного G граф H будет связным?

Мне как-то сразу интуитивно довольно очевидно, что это верно.

Положим, что существует связной граф G, для которого H не связной. Возьмем из H две вершины, T и T', из разных компонент связности. T и T' отличаются n гранями. Без ограничения общности возьмем из T' грань, которой нет в T и добавим ее в T. Теперь в T есть цикл. Удалим из этого цикла ту грань, которой нет в T'. Теперь T и T' отличаются n-1 гранями. Проделываем эту процедуру n раз и получаем, что T и T' находятся в одной компоненте, вопреки тому, что мы их выбирали из разных компонент связности.

Значит такого графа G не существует. Верно?

[RawonaM]

Нужно предложить алгоритм определения, является ли определенная грань e=(v,w) частью какого-то минимального остовного дерева некоего связанного графа с ве́сами (weights?).

Думаю, что такой граф не существует iff существует путь от v к w, в котором все грани легче е. Для этого убираем все грани тяжелее е и прогоняем BFS или DFS. Если есть путь, то нет минимального дерева с е, если нет пути, то есть такое дерево.

Гораздо непонятнее второй вопрос: какой можно предложить алгоритм определения того, является ли определенная грань e=(v,w) частью всех минимальных остовных деревьев?

По-моему условие такое: грань е является частью всех МОД iff все пути от w к v состоят из граней с весом большим, чем у е (то есть грань е является самой легкой во всех циклах, в которых она состоит) или грань е является мостом.

А вот как это найти, я уже пару дней (с перерывами) пытаюсь понять.
Убирание всех граней тяжелее или легче тут не помогает, нужно придумывать что-то более утонченное.

[RawonaM]

Классная жава-штуковина для рисования графов:
http://www.cut-the-knot.org/Curriculum/Combinatorics/MinimumSpanningTree.shtml

[GaLL]

Нужно предложить алгоритм определения, является ли определенная грань e=(v,w) частью какого-то минимального остовного дерева некоего связанного графа с ве́сами (weights?).

Находим величину минимального остова данного графа. Потом стягиваем v и w, и у получившегося графа находим величину мин. остова. Если она отличается от предыдущей на вес ребра e, значит, ответ "Да", иначе "Нет".