Печать страницы - Теория графов

Название: Теория графов
Отправлено: RawonaM от июня 7, 2011, 19:36

Что-то тут было, но стерлось.

Название: Теория графов
Отправлено: RawonaM от июня 7, 2011, 19:40

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

П.С. В туториале тема мало затрагивается, связи с предыдущим сообщением нет.

Название: Теория графов
Отправлено: Квас от июня 7, 2011, 20:33

Цитата: RawonaM от июня 7, 2011, 19:40
А теперь теоретический вопрос о планарных графах: можно ли сказать, что непростой граф (т.е. содержащий либо петли либо двойные ребра) планарный iff если сделать из него простой путем убирания всех петлей и двойных ребер — планарный?

Очевидно, да. Если простой планарный граф уложить на плоскость, добавить крохотные петельки и ненамного раздвинуть, разодрав их, рёбра, то пересечений рёбер не будет.

Речь, естественно, о конечных графах.

Название: Теория графов
Отправлено: RawonaM от июня 7, 2011, 20:37

Цитата: Квас от июня 7, 2011, 20:33
Если простой планарный граф уложить на плоскость, добавить крохотные петельки и ненамного раздвинуть, разодрав их, рёбра, то пересечений рёбер не будет.

Результат этой вашей жестокой операции можно описать как дополняющий к дополняющему этого графа? :)

Собственно, мне это тоже вроде очевидно, но ведь нужно доказать перед использованием, наверное.

Название: Теория графов
Отправлено: Квас от июня 7, 2011, 20:40

Цитата: RawonaM от июня 7, 2011, 20:37
Цитата: Квас от июня 7, 2011, 20:33Если простой планарный граф уложить на плоскость, добавить крохотные петельки и ненамного раздвинуть, разодрав их, рёбра, то пересечений рёбер не будет.
Результат этой вашей жестокой операции можно описать как дополняющий к дополняющему этого графа? :)

Дополняющий к дополняющему определён однозначно, а петелек можно добавлять разное число.

Цитата: RawonaM от июня 7, 2011, 20:37
Собственно, мне это тоже вроде очевидно, но ведь нужно доказать.

Это самое утверждение о планарности? Топология, однако. А каким инструментарием мы владеем? Надо теорему Понтрягина вспоминать. :-\

Название: Теория графов
Отправлено: RawonaM от июня 7, 2011, 20:44

Цитата: Квас от июня 7, 2011, 20:40
Дополняющий к дополняющему определён однозначно, а петелек можно добавлять разное число.

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

Название: Теория графов
Отправлено: RawonaM от июня 7, 2011, 20:47

Цитата: Квас от июня 7, 2011, 20:40
Цитата: RawonaM от июня 7, 2011, 20:37Собственно, мне это тоже вроде очевидно, но ведь нужно доказать.
Это самое утверждение о планарности? Топология, однако. А каким инструментарием мы владеем? Надо теорему Понтрягина вспоминать. :-\

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

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

Название: Теория графов
Отправлено: RawonaM от июня 10, 2011, 14:06

Тут у меня понову проблема, но я не знаю чем мне можно помочь.

У меня такой вопрос:
Покрасили граф G (x(G) = k) k красками.
1) Покажите, что на каждый цвет есть такая вершина, что ее соседи используют ровно k-1 цветов.
Достаточно легко доказывается обычными рассуждениями в духе теории графов.
2) Какое утверждение в книге, доказывает 1).

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

Утверждения есть такие (самые вообще не втемные отбрасываю):
1) х(Kn)=n
2) x(G)=2 iff G двухсторонний граф с хотя бы одним ребром
3) x(G)<=d(G)+1 (d(G) — максимальная степень вершины из G)
4) x(G)<=d(G) кроме двух частных случаев.
5) d-вырожденный граф можно покрасить d+1 цветами
6) если G можно покрасить k цветами, то в G есть независимое подмножество размером $[tex]\lceil |V(G)|/k \rceil[/tex]$ .

Айдии?

Название: Теория графов
Отправлено: Квас от июня 10, 2011, 14:39

Voulez-vous bien expliquer ces notations ? ;)

Название: Теория графов
Отправлено: RawonaM от июня 10, 2011, 14:58

Цитата: Квас от июня 10, 2011, 14:39
Voulez-vous bien expliquer ces notations ? ;)

Pardon :)
x(G)= $[tex]\chi(G)[/tex]$ (ленюсь переключаться :)), т.е. хроматический индекс, т.е. минимум цветов, которыми можно покрасить.
V(G)=количество вершин.
K_n= полный граф к количеством вершин n.
Какие еще не ясны?

Название: Теория графов
Отправлено: Квас от июня 10, 2011, 14:59

Цитата: RawonaM от июня 10, 2011, 14:06
Покрасили граф G, x(G), k красками.

А это что так много через запятую? x(G) = k?

Название: Теория графов
Отправлено: RawonaM от июня 10, 2011, 15:01

Цитата: Квас от июня 10, 2011, 14:59
Цитата: RawonaM от июня 10, 2011, 14:06Покрасили граф G, x(G), k красками.
А это что так много через запятую? x(G) = k?

Да, именно так. Че-то я поспешил :)

Название: Теория графов
Отправлено: Квас от июня 10, 2011, 20:54

Цитата: RawonaM от июня 10, 2011, 14:06
Айдии?

Да что-то не очень ясно.

Цитата: RawonaM от июня 10, 2011, 14:06
1) х(Kn)=n
2) x(G)=2 iff G двухсторонний граф с хотя бы одним ребром
3) x(G)<=d(G)+1 (d(G) — максимальная степень вершины из G)
4) x(G)<=d(G) кроме двух частных случаев.
5) d-вырожденный граф можно покрасить d+1 цветами
6) если G можно покрасить k цветами, то в G есть независимое подмножество размером $[tex]\lceil |V(G)|/k \rceil[/tex]$ .

1) и 2) не подходят, потому что относятся к специальным графам. Односторонних оценок, даваемых 3) и 4), насколько понимаю, ни для чего не хватит. 5) ⇔ 3), насколько понимаю. 6) — :???

Думаю...

Название: Теория графов
Отправлено: RawonaM от июня 11, 2011, 19:54

Цитата: RawonaM от июня 10, 2011, 14:06
У меня такой вопрос:
Покрасили граф G (x(G) = k) k красками.
1) Покажите, что на каждый цвет есть такая вершина, что ее соседи используют ровно k-1 цветов.

Третий пункт там такой: 3) Покажите, что в G есть по меньшей мере k вершин со степенью k-1.

Я почуял неладное, и вот нашел контрпример: круг на четырех вершинах. x(G)=2, но нет в нем 2 вершины со степенью 1. Верно говорю? Написал на форум курса.

Название: Теория графов
Отправлено: Квас от июня 11, 2011, 20:05

Цитата: RawonaM от июня 11, 2011, 19:54
Я почуял неладное, и вот нашел контрпример: круг на четырех вершинах. x(G)=2, но нет в нем 2 вершины со степенью 1. Верно говорю?

Ну конечно. И вообще противоречит свойству 2).

Название: Теория графов
Отправлено: RawonaM от июня 11, 2011, 20:08

Цитата: Квас от июня 11, 2011, 20:05
Цитата: RawonaM от июня 11, 2011, 19:54Я почуял неладное, и вот нашел контрпример: круг на четырех вершинах. x(G)=2, но нет в нем 2 вершины со степенью 1. Верно говорю?
Ну конечно. И вообще противоречит свойству 2).

Почему противоречит?

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

Название: Теория графов
Отправлено: Квас от июня 11, 2011, 20:12

Цитата: RawonaM от июня 11, 2011, 20:08
Почему противоречит?

Можно привести сколько угодно примеров двудольных графов, у которых нет вершин степени 1.

Название: Теория графов
Отправлено: RawonaM от июня 12, 2011, 10:52

Ошибку признали, сказали разошлют фикс по всем инстанциям.

Оказывается я ~~идиот~~ прочитал неправильно пункт 2), там нужно показать, какое утверждение из книги доказывается пунктом 1), а не наоборот.

Думаю, что из:

Цитата: RawonaM от июня 10, 2011, 14:06
Покрасили граф G (x(G) = k) k красками.
1) Покажите, что на каждый цвет есть такая вершина, что ее соседи используют ровно k-1 цветов.

следует:

Цитата: RawonaM от июня 10, 2011, 15:01
3) x(G)<=d(G)+1 (d(G) — максимальная степень вершины из G)

Название: Теория графов
Отправлено: Квас от июня 12, 2011, 21:42

Цитата: RawonaM от июня 12, 2011, 10:52
Думаю, что из:
Цитата: RawonaM от июня 10, 2011, 14:06Покрасили граф G (x(G) = k) k красками.
1) Покажите, что на каждый цвет есть такая вершина, что ее соседи используют ровно k-1 цветов.
следует:
Цитата: RawonaM от июня 10, 2011, 15:013) x(G)<=d(G)+1 (d(G) — максимальная степень вершины из G)

Согласен. Вроде бы и 5) так же легко выводится.

Название: Теория графов
Отправлено: RawonaM от июня 12, 2011, 21:58

Цитата: Квас от июня 12, 2011, 21:42
Согласен. Вроде бы и 5) так же легко выводится.

Может быть. Но утверждение 2 сильнее вроде.

Название: Теория графов
Отправлено: RawonaM от октября 8, 2011, 16:57

Дан простой граф G с вершинами V, правильно раскрашенными в цвета из множества А.
G' - дополняющий к G, правильно раскрашен цветами из B.

Для каждого v из V, подберем пару (a,b), так что а цвет v в G, а В цвет v в G'. Доказать, что нет двух вершин, для которых выходит та же пара (т.е. отображение инъективно).

Что скажете? У меня ничего не вышло :)

Название: Теория графов
Отправлено: RawonaM от октября 10, 2011, 21:11

Из моего сегодняшнего экзамена:

Даны два дерева на вершинах V G₁=(V,E₁), G₁=(V,E₁).

Для каждой вершины v определим d1(v) - степень вершины на первом дереве, d2(v) степень вершины на втором дереве.

Доказать, что существует такой v, для которого d1(v)+d2(v)≤3.

Название: Теория графов
Отправлено: RawonaM от октября 10, 2011, 21:24

Получается так: если предположить, что нет такой вершины, то сумма степеней всех вершин обоих графов >=4n (n количество вершин).

С другой стороны сумма степеней всех вершин дерева равна 2n-2, значит двух деревьев 4n-4.

Следовательно есть хоть одна такая вершина. Эх, такую фигню спорол. :(
А я просто написал >=3n и у меня вышла фигня.

Название: Теория графов
Отправлено: RawonaM от ноября 23, 2011, 15:16

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

Смотрю (wiki/en) Strong_orientation (http://en.wikipedia.org/wiki/Strong_orientation)

ЦитироватьIn graph theory, a strong orientation of an undirected graph is an assignment of a direction to each edge that makes it into a strongly connected graph. Robbins' theorem, named after Herbert Robbins (1939), states that the graphs that have strong orientations are exactly the 2-edge-connected graphs. That is, it is possible to choose a direction for each edge of an undirected graph G, turning into a directed graph that has a path from every vertex to every other vertex, if and only if G is connected and has no bridge.

Смотрю (wiki/en) K-edge-connected_graph (http://en.wikipedia.org/wiki/K-edge-connected_graph)

ЦитироватьIn graph theory, a graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.

Let G = (E,V) be an arbitrary graph. If G' = (E \ X,V) is connected for all X ⊆ E where |X| < k, then G is k-edge-connected. Trivially, a graph that is k-edge-connected is also (k−1)-edge-connected.

Смотрю в первую цитату снова: 2-edge-connected graph = is connected and has no bridge.

Вроде логично. Берем граф из трех вершин соединенных в треугольник, ставим стрелки по кругу. Получился сильно ориентированный граф? Вроде как да. Но ведь он 1-edge-connected!

Чего я недопонял?

Название: Теория графов
Отправлено: RawonaM от ноября 23, 2011, 15:18

А нет, подождите, он is connected and has no bridge. Значит таки 2-edge-connected?
Не понял я этого термина пока что.

Название: Теория графов
Отправлено: GaLL от ноября 23, 2011, 15:43

Цитата: RawonaM от ноября 23, 2011, 15:16
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 от ноября 23, 2011, 15:48

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

Название: Теория графов
Отправлено: GaLL от ноября 23, 2011, 15:52

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

Название: Теория графов
Отправлено: RawonaM от ноября 23, 2011, 15:55

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

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

Название: Теория графов
Отправлено: RawonaM от ноября 24, 2011, 17:55

Цитата: GaLL от ноября 23, 2011, 15:43
Кажется, я решил эту задачу, но доказательство получилось не очень красивое.

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

Название: Теория графов
Отправлено: RawonaM от ноября 24, 2011, 18:07

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

Название: Теория графов
Отправлено: Bhudh от ноября 24, 2011, 20:37

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

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

Название: Теория графов
Отправлено: RawonaM от ноября 25, 2011, 10:56

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

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

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

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

Название: Теория графов
Отправлено: GaLL от ноября 25, 2011, 12:32

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

Название: Теория графов
Отправлено: GaLL от ноября 25, 2011, 13:46

Моё решение:

Spoiler ⇓⇓⇓

Название: Теория графов
Отправлено: RawonaM от ноября 25, 2011, 14:05

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

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

Название: Теория графов
Отправлено: GaLL от ноября 25, 2011, 14:07

Цитата: RawonaM от ноября 25, 2011, 14:05
Ага, понятно.

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

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

Название: Теория графов
Отправлено: RawonaM от ноября 25, 2011, 14:15

Цитата: GaLL от ноября 25, 2011, 14:07
Читал, но к нему легко подобрать контрпример, см. выше.

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

Название: Теория графов
Отправлено: RawonaM от ноября 25, 2011, 14:18

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

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

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

Название: Теория графов
Отправлено: GaLL от ноября 25, 2011, 14:28

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

Название: Теория графов
Отправлено: RawonaM от ноября 25, 2011, 14:35

Цитата: GaLL от ноября 25, 2011, 14:28
Вы имеете в виду алгоритм проверки графа на возможность сделать из него сильно связный ориентированный? Я думал, вопрос в задаче - каков критерий того, что это можно сделать.

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

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

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

Название: Теория графов
Отправлено: GaLL от ноября 25, 2011, 14:56

Цитата: RawonaM от ноября 25, 2011, 14:35
А как одним DFS-ом проверить на мосты?

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

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

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

Название: Теория графов
Отправлено: RawonaM от ноября 25, 2011, 15:16

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

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

Название: Теория графов
Отправлено: RawonaM от ноября 25, 2011, 15:17

Цитата: GaLL от ноября 25, 2011, 14:56
Частенько простые алгоритмы основываются на довольно длинных доказательствах. Вы видели доказательство верности алгоритма Флойда (длины кратчайших путей между всеми парами вершин графа)?

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

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

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

Название: Теория графов
Отправлено: GaLL от ноября 25, 2011, 16:20

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

Любой алгоритм требует доказательства. Здесь доказательство примерно такое такое же, как для критерия.
Я там ошибся немного, надо не 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 от ноября 25, 2011, 18:06

Цитата: GaLL от ноября 25, 2011, 16:20
Цитата: RawonaM от ноября 25, 2011, 15:16Что-то я не понял, как это происходит. Еще и это доказывать надо будет!
Любой алгоритм требует доказательства. Здесь доказательство примерно такое такое же, как для критерия.

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

В книге A first look at graph theory (http://books.google.com/books?id=vLRNRebXuKYC&pg=PA254&lpg=PA254&dq=Clark,+John;+Holton,+Derek+Allan+%281991%29,+%227.4+Traffic+Flow%22,+A+first+look+at+graph+theory&source=bl&ots=36Xwwfa98l&sig=yrJKe2B4x4SX6NZcP8ru1EVzJ10&hl=fr&ei=zrnPTqTXHMWA-wazkJQT&sa=X&oi=book_result&ct=result&resnum=1&ved=0CCYQ6AEwAA#v=onepage&q&f=false) доказательство двусвязности заняло больше страницы мелкого текста.

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

Название: Теория графов
Отправлено: RawonaM от декабря 9, 2011, 21:55

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

Допустим дан некий связной граф 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 от декабря 15, 2011, 15:50

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

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

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

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

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

Название: Теория графов
Отправлено: RawonaM от декабря 15, 2011, 16:46

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

Название: Теория графов
Отправлено: GaLL от декабря 16, 2011, 06:31

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

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

Название: Теория графов
Отправлено: GaLL от декабря 16, 2011, 06:33

Цитата: RawonaM от декабря 9, 2011, 21:55
Тут в книге задача, не пойму каким образом она относится к теме.

Напрямую же. :)

Цитировать
Допустим дан некий связной граф 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 от декабря 16, 2011, 07:53

Цитата: GaLL от декабря 16, 2011, 06:31
Цитата: RawonaM от декабря 15, 2011, 15:50Нужно предложить алгоритм определения, является ли определенная грань e=(v,w) частью какого-то минимального остовного дерева некоего связанного графа с ве́сами (weights?).
Находим величину минимального остова данного графа. Потом стягиваем v и w, и у получившегося графа находим величину мин. остова. Если она отличается от предыдущей на вес ребра e, значит, ответ "Да", иначе "Нет".

Что-то мне тут не понятно. Что такое минимальный остов?

Там еще вопрос затесался, который имхо сложнее, посмотрите если не трудно:

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

Название: Теория графов
Отправлено: RawonaM от декабря 16, 2011, 07:54

Цитата: GaLL от декабря 16, 2011, 06:33
Цитата: RawonaM от декабря 9, 2011, 21:55Тут в книге задача, не пойму каким образом она относится к теме.
Напрямую же. :)

Я имею в виду к теме жадных алгоритмов :)

Название: Теория графов
Отправлено: GaLL от декабря 16, 2011, 07:56

Цитата: RawonaM от декабря 16, 2011, 07:53
Что-то мне тут не понятно. Что такое минимальный остов?

То же, что и минимальное остовное дерево. Жаргонизм.

Название: Теория графов
Отправлено: GaLL от декабря 16, 2011, 07:58

Цитата: RawonaM от декабря 16, 2011, 07:53
Там еще вопрос затесался, который имхо сложнее, посмотрите если не трудно:
Цитата: RawonaM от декабря 15, 2011, 15:50
Гораздо непонятнее второй вопрос: какой можно предложить алгоритм определения того, является ли определенная грань e=(v,w) частью всех минимальных остовных деревьев?

Ну это легко. Тогда и только тогда, когда после удаления данного ребра величина мин. остовного дерева становится больше.

Название: Теория графов
Отправлено: RawonaM от декабря 16, 2011, 07:59

Цитата: GaLL от декабря 16, 2011, 07:56
Цитата: RawonaM от декабря 16, 2011, 07:53Что-то мне тут не понятно. Что такое минимальный остов?
То же, что и минимальное остовное дерево. Жаргонизм.

Я еще не уверен, что понял как работает ваш алгоритм, но он в любом случае как минимум О(m lg n), т.к. нужно найти остов, что занимает именно столько. Мой алгоритм (точнее модификация уже где-то подсмотренного алгоритма) работает в О(m+n).

Название: Теория графов
Отправлено: RawonaM от декабря 16, 2011, 08:03

Цитата: GaLL от декабря 16, 2011, 07:58
Цитата: RawonaM от декабря 16, 2011, 07:53Там еще вопрос затесался, который имхо сложнее, посмотрите если не трудно:
Цитата: RawonaM от декабря 15, 2011, 15:50Гораздо непонятнее второй вопрос: какой можно предложить алгоритм определения того, является ли определенная грань e=(v,w) частью всех минимальных остовных деревьев?
Ну это легко. Тогда и только тогда, когда после удаления данного ребра величина мин. остовного дерева становится больше.

А и правда! :scl: Спасибо!

Название: Теория графов
Отправлено: GaLL от декабря 16, 2011, 08:04

Цитата: RawonaM от декабря 16, 2011, 07:59
Я еще не уверен, что понял как работает ваш алгоритм, но он в любом случае как минимум О(m lg n), т.к. нужно найти остов, что занимает именно столько. Мой алгоритм (точнее модификация уже где-то подсмотренного алгоритма) работает в О(m+n).

Алгоритм Прима на фибоначчиевой куче работает за O(m + n*log(n)).

Название: Теория графов
Отправлено: RawonaM от декабря 16, 2011, 08:28

Цитата: GaLL от декабря 16, 2011, 08:04
Алгоритм Прима на фибоначчиевой куче работает за O(m + n*log(n)).

Нас такому не учили :( У нас в книге все алгоритмы O(m lg n).

Название: Теория графов
Отправлено: RawonaM от декабря 16, 2011, 20:46

Нужно найти самый легкий цикл на ориентированном графе с весом на гранях. Как это сделать оптимально?
Ничего кроме как запустить для каждой вершины алгоритм Дейкстры я не придумал.

Название: Теория графов
Отправлено: RawonaM от декабря 16, 2011, 22:39

Цитата: GaLL от декабря 16, 2011, 06:31
Цитата: RawonaM от декабря 15, 2011, 15:50Нужно предложить алгоритм определения, является ли определенная грань e=(v,w) частью какого-то минимального остовного дерева некоего связанного графа с ве́сами (weights?).
Находим величину минимального остова данного графа. Потом стягиваем v и w, и у получившегося графа находим величину мин. остова. Если она отличается от предыдущей на вес ребра e, значит, ответ "Да", иначе "Нет".

А как это работает? Что-то я не догоняю. А если вес 0? Тогда ничего отличаться не будет.

Название: Теория графов
Отправлено: GaLL от декабря 18, 2011, 17:34

Цитата: RawonaM от декабря 16, 2011, 20:46
Нужно найти самый легкий цикл на ориентированном графе с весом на гранях. Как это сделать оптимально?
Ничего кроме как запустить для каждой вершины алгоритм Дейкстры я не придумал.

Не знаю, как сделать быстрее, чем за O(V*E).

Название: Теория графов
Отправлено: RawonaM от декабря 18, 2011, 17:39

Цитата: GaLL от декабря 18, 2011, 17:34
Цитата: RawonaM от декабря 16, 2011, 20:46Нужно найти самый легкий цикл на ориентированном графе с весом на гранях. Как это сделать оптимально?
Ничего кроме как запустить для каждой вершины алгоритм Дейкстры я не придумал.
Не знаю, как сделать быстрее, чем за O(V*E).

А как за O(V*E)?

Название: Теория графов
Отправлено: GaLL от декабря 18, 2011, 17:41

Цитата: RawonaM от декабря 16, 2011, 22:39
Цитата: GaLL от декабря 16, 2011, 06:31
Цитата: RawonaM от декабря 15, 2011, 15:50Нужно предложить алгоритм определения, является ли определенная грань e=(v,w) частью какого-то минимального остовного дерева некоего связанного графа с ве́сами (weights?).
Находим величину минимального остова данного графа. Потом стягиваем v и w, и у получившегося графа находим величину мин. остова. Если она отличается от предыдущей на вес ребра e, значит, ответ "Да", иначе "Нет".
А как это работает? Что-то я не догоняю. А если вес 0? Тогда ничего отличаться не будет.

Совсем необязательно, может и отличаться. Например, если веса остальных рёбер отрицательные, ребро vw при этом не мост. Тогда величина мин. остова со стянутыми v и w будет больше.
Стягивание вершин - т. е. они объединяются в одну, а ребро между ними исчезает.

Название: Теория графов
Отправлено: RawonaM от декабря 18, 2011, 17:48

Цитата: GaLL от декабря 18, 2011, 17:41
Совсем необязательно, может и отличаться. Например, если веса остальных рёбер отрицательные, ребро vw при этом не мост. Тогда величина мин. остова со стянутыми v и w будет больше.

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

Название: Теория графов
Отправлено: GaLL от декабря 18, 2011, 17:54

Цитата: RawonaM от декабря 18, 2011, 17:48
Цитата: GaLL от декабря 18, 2011, 17:41
Совсем необязательно, может и отличаться. Например, если веса остальных рёбер отрицательные, ребро vw при этом не мост. Тогда величина мин. остова со стянутыми v и w будет больше.
Ну да, может отличаться. Но таким образом это условие уже не годно, ведь не будет отличаться, а может отличаться.

Почему негодно? Приведите контрпример.

Название: Теория графов
Отправлено: GaLL от декабря 18, 2011, 17:57

Цитата: RawonaM от декабря 18, 2011, 17:39
Цитата: GaLL от декабря 18, 2011, 17:34
Цитата: RawonaM от декабря 16, 2011, 20:46Нужно найти самый легкий цикл на ориентированном графе с весом на гранях. Как это сделать оптимально?
Ничего кроме как запустить для каждой вершины алгоритм Дейкстры я не придумал.
Не знаю, как сделать быстрее, чем за O(V*E).
А как за O(V*E)?

Для относительно плотных графов - V раз алгоритм Дейкстры (каждый из них - за O(E + V*log(V))).

Название: Теория графов
Отправлено: RawonaM от декабря 18, 2011, 18:00

Цитата: GaLL от декабря 18, 2011, 17:54
Цитата: RawonaM от декабря 18, 2011, 17:48
Цитата: GaLL от декабря 18, 2011, 17:41Совсем необязательно, может и отличаться. Например, если веса остальных рёбер отрицательные, ребро vw при этом не мост. Тогда величина мин. остова со стянутыми v и w будет больше.
Ну да, может отличаться. Но таким образом это условие уже не годно, ведь не будет отличаться, а может отличаться.
Почему негодно? Приведите контрпример.

Если граф со всеми гранями неотрицательным весом, на определенной грани 0. Убираем ее, добавляем ее, вес минимального остова не должен меняться. Или может не меняться при определенном раскладе.
Например возьмем квадрат, все грани по нулю. Или все грани по любому n. Убираем одну грань, вес минимального остова не меняется, хотя был минимальный остов с ней.

Название: Теория графов
Отправлено: GaLL от декабря 18, 2011, 18:01

Цитата: RawonaM от декабря 16, 2011, 08:28
Цитата: GaLL от декабря 16, 2011, 08:04
Алгоритм Прима на фибоначчиевой куче работает за O(m + n*log(n)).
Нас такому не учили :( У нас в книге все алгоритмы O(m lg n).

О фибоначчиевых кучах можно прочитать, например, в книге "Алгоритмы: построение и анализ" Кормена, Лейзерсона, Ривеста. На практике эта структура данных начинает давать выигрыш только при ~миллионе элементов, так как она довольно сложно устроена.

Название: Теория графов
Отправлено: GaLL от декабря 18, 2011, 18:05

Цитата: RawonaM от декабря 18, 2011, 18:00
Цитата: GaLL от декабря 18, 2011, 17:54
Цитата: RawonaM от декабря 18, 2011, 17:48
Цитата: GaLL от декабря 18, 2011, 17:41Совсем необязательно, может и отличаться. Например, если веса остальных рёбер отрицательные, ребро vw при этом не мост. Тогда величина мин. остова со стянутыми v и w будет больше.
Ну да, может отличаться. Но таким образом это условие уже не годно, ведь не будет отличаться, а может отличаться.
Почему негодно? Приведите контрпример.
Если граф со всеми гранями неотрицательным весом, на определенной грани 0. Убираем ее, добавляем ее, вес минимального остова не должен меняться. Или может не меняться при определенном раскладе.
Например возьмем квадрат, все грани по нулю. Или все грани по любому n. Убираем одну грань, вес минимального остова не меняется, хотя был минимальный остов с ней.

Не просто убираем, а объединяем две вершины в одну. Соответственно, если ребро соединяло v и w с некоей вершиной t, то теперь оно будет соединять объединённую вершину с t. после стягивания можно избавиться от мульграфности, отбросив каждое ребро, для которого существует соединяющее те же вершины, но меньшее или равное по весу.

Название: Теория графов
Отправлено: RawonaM от декабря 18, 2011, 18:21

Цитата: GaLL от декабря 18, 2011, 18:05
Не просто убираем, а объединяем две вершины в одну. Соответственно, если ребро соединяло v и w с некоей вершиной t, то теперь оно будет соединять объединённую вершину с t. после стягивания можно избавиться от мульграфности, отбросив каждое ребро, для которого существует соединяющее те же вершины, но меньшее или равное по весу.

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

Название: Теория графов
Отправлено: GaLL от декабря 18, 2011, 18:23

Цитата: RawonaM от декабря 18, 2011, 18:21
Хорошо, значит контрпример такой: берем квадрат со всеми гранями с весом ноль.
Взяли одну, стянули, получился треугольник, но вес остова не изменился.

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

Название: Теория графов
Отправлено: RawonaM от декабря 18, 2011, 18:24

Цитата: GaLL от декабря 18, 2011, 18:23
Цитата: RawonaM от декабря 18, 2011, 18:21Хорошо, значит контрпример такой: берем квадрат со всеми гранями с весом ноль.
Взяли одну, стянули, получился треугольник, но вес остова не изменился.
Отсюда следует, что ребро, которое стягивали, содержится в одном из минимальных остовов исходного графа.

Это потому, что вес ноль?
Что-то я уже запутался совсем :)

Название: Теория графов
Отправлено: RawonaM от декабря 18, 2011, 18:25

Цитата: GaLL от декабря 16, 2011, 06:31
Если она отличается от предыдущей на вес ребра e, значит, ответ "Да", иначе "Нет".

Получается, что если вес ребра = 0, то ответ да и нет имеет одинаковый результат.

Название: Теория графов
Отправлено: GaLL от декабря 18, 2011, 18:28

Цитата: RawonaM от декабря 18, 2011, 18:25
Цитата: GaLL от декабря 16, 2011, 06:31
Если она отличается от предыдущей на вес ребра e, значит, ответ "Да", иначе "Нет".
Получается, что если вес ребра = 0, то ответ да и нет имеет одинаковый результат.

Если вес ребра - ноль, то это ещё не говорит о том, что вес мин. остова не изменится при стягивании.

Название: Теория графов
Отправлено: GaLL от декабря 18, 2011, 18:31

Цитата: RawonaM от декабря 18, 2011, 18:24
Цитата: GaLL от декабря 18, 2011, 18:23
Цитата: RawonaM от декабря 18, 2011, 18:21Хорошо, значит контрпример такой: берем квадрат со всеми гранями с весом ноль.
Взяли одну, стянули, получился треугольник, но вес остова не изменился.
Отсюда следует, что ребро, которое стягивали, содержится в одном из минимальных остовов исходного графа.
Это потому, что вес ноль?
Что-то я уже запутался совсем :)

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

Название: Теория графов
Отправлено: GaLL от декабря 18, 2011, 18:36

Цитата: RawonaM от декабря 16, 2011, 08:03
Цитата: GaLL от декабря 16, 2011, 07:58
Цитата: RawonaM от декабря 16, 2011, 07:53Там еще вопрос затесался, который имхо сложнее, посмотрите если не трудно:
Цитата: RawonaM от декабря 15, 2011, 15:50Гораздо непонятнее второй вопрос: какой можно предложить алгоритм определения того, является ли определенная грань e=(v,w) частью всех минимальных остовных деревьев?
Ну это легко. Тогда и только тогда, когда после удаления данного ребра величина мин. остовного дерева становится больше.
А и правда! :scl: Спасибо!

Кстати, если одно из мин. остовных деревьев уже известно, то задача решается за O(E). А проверить все рёбра данного остовного дерева на это свойство можно за O(V²).

Название: Теория графов
Отправлено: RawonaM от декабря 19, 2011, 08:01

Цитата: GaLL от декабря 18, 2011, 18:31
Вес остова изменился на ноль, т. е. на вес убранного ребра.

Как вы отличаете "изменился на 0" и "не изменился"? Или измениться может на другое количество?

Название: Теория графов
Отправлено: GaLL от декабря 20, 2011, 09:18

Цитата: RawonaM от декабря 19, 2011, 08:01
Цитата: GaLL от декабря 18, 2011, 18:31
Вес остова изменился на ноль, т. е. на вес убранного ребра.
Как вы отличаете "изменился на 0" и "не изменился"? Или измениться может на другое количество?

Я о Вашем примере: цикл с четырьмя вершинами и рёбрами с весом 0. Вес его мин. остова = 0. Если стянуть две смежные вершины, вес мин. остова опять будет 0. Разница равна весу стянутого ребра => есть мин. остовное дерево данного графа, содержащее это ребро.

Название: Теория графов
Отправлено: RawonaM от января 10, 2012, 10:50

Похожий вопрос. Дан граф с весами на гранях, вершины s и t (s≠t) и грань е. Нужно найти эффективные алгоритмы, отвечающие на вопросы:
1) Принадлежит ли е к каждому минимальному пути между s и t.
2) Принадлежит ли е к какому-нибудь простому минимальному пути между s и t.

Ввиду опыта с минимальными остовами я так сделал:
1) Находим вес минимального пути, убираем е и опять находим вес минимального пути. Если вес изменился, то е принадлежит ко всем минимальным путям.
2) Если есть отрицательные циклы, то нет минимального маршрута.
Иначе находим вес минимального маршрута.
Затем уменьшаем вес е на любое число а и снова находим вес минимального маршрута. Если вес минимального маршрута уменьшился на а, то е принадлежит какому-нибудь простому маршруту.

Верно?

Название: Теория графов
Отправлено: RawonaM от января 12, 2012, 11:15

Цитата: RawonaM от января 10, 2012, 10:50
Затем уменьшаем вес е на любое число а и снова находим вес минимального маршрута. Если вес минимального маршрута уменьшился на а, то е принадлежит какому-нибудь простому маршруту.

Нет, что-то это бред какой-то.

Название: Теория графов
Отправлено: RawonaM от января 12, 2012, 11:33

Цитата: RawonaM от января 12, 2012, 11:15
Цитата: RawonaM от января 10, 2012, 10:50Затем уменьшаем вес е на любое число а и снова находим вес минимального маршрута. Если вес минимального маршрута уменьшился на а, то е принадлежит какому-нибудь простому маршруту.
Нет, что-то это бред какой-то.

Нет, это не бред. Вроде как все правильно.

Название: Теория графов
Отправлено: GaLL от января 23, 2012, 20:40

Цитата: RawonaM от января 10, 2012, 10:50
Похожий вопрос. Дан граф с весами на гранях, вершины s и t (s≠t) и грань е. Нужно найти эффективные алгоритмы, отвечающие на вопросы:
1) Принадлежит ли е к каждому минимальному пути между s и t.
2) Принадлежит ли е к какому-нибудь простому минимальному пути между s и t.

Если известны длины кратчайших путей от s до всех остальных вершин, то и на первый, и на второй вопрос можно ответить за O(E) не только для какого-то конкретного e, но и для всех рёбер сразу. Для этого можно воспользоваться вспомогательным графом, построенным следующим образом:
Пусть исходный граф - G, а d - длина кратчайшего пути от s до i, а H - пустой граф с тем же числом вершин и без весов у рёбер. Перебираем все рёбра из G, пусть текущее соединяет вершины a и b (из a в b), и его длина - q. Если d = d[a] + q, то добавляем в граф H ребро из a в b.
Далее всё сводится к исследованию графа H. Понятно, что любой путь из a в b в графе H будет соответствовать кратчайшему пути из a в b в графе G.

Название: Теория графов
Отправлено: GaLL от января 23, 2012, 22:32

Цитата: RawonaM от декабря 16, 2011, 20:46
Нужно найти самый легкий цикл на ориентированном графе с весом на гранях. Как это сделать оптимально?
Ничего кроме как запустить для каждой вершины алгоритм Дейкстры я не придумал.

Оказывается, до сих пор не придумано ничего лучше, чем решать эту задачу через поиск длин кратчайших путей между всеми парами вершин:
http://arxiv.org/abs/1104.2882

Цитировать
Minimum cycle and APSP. Recently, in FOCS'10 Vassilevska W. and Williams [24] showed that the minimum
weight cycle problem is equivalent to many other graph and matrix problems for which no truly subcubic (O(n^{3− ε})-
time for constant ε > 0) algorithms are known. They showed that if there is a truly subcubic algorithm for the
minimum weight cycle problem, then many other problems such as the all-pairs-shortest-paths (APSP) problem also
have truly subcubic algorithms. Hence, the minimum weight cycle problem has a pivotal role in understanding the
complexity of many fundamental polynomial problems in a similar spirit to the role of 3SAT for NP-hard problems.

Название: Теория графов
Отправлено: RawonaM от апреля 21, 2012, 11:11

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

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

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

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

Название: Теория графов
Отправлено: RawonaM от апреля 22, 2012, 08:47

Дан граф ориентированный или неориентированный с вершинами С, П и гранью Е, известно что есть путь между С и П.
Нужно дать эффективный алгоритм, который определяет, есть ли простой путь от С к П через грань Е.
Я пока ничего не придумал.

Название: Теория графов
Отправлено: RawonaM от апреля 22, 2012, 08:52

Вообще в целом, чтобы найти несколько путей нужно строить транспортную сеть, лучше ничего нет?

Название: Теория графов
Отправлено: RawonaM от апреля 22, 2012, 18:06

http://www.ics.uci.edu/~eppstein/161/960208.html

Цитировать
Dijkstra and negative lengths
Dijkstra's algorithm does not work with negative edge weights. For instance, consider the following graph (assume the edges are all directed from left to right):

2
A-----B
\ /
3 \ / -2
C

If we start with A, Dijkstra's algorithm will choose the edge (A,x) minimizing d(A,A)+length(edge), namely (A,B). It then sets d(A,B)=2 and chooses another edge (y,C) minimizing d(A,y)+d(y,C); the only choice is (A,C) and it sets d(A,C)=3. But it never finds the shortest path from A to B, via C, with total length 1.

Нет ли ошибки в этом примере? Если я правильно понимаю алгоритм Дейкстры, то этот пример посчитается как надо.
Правда я не уверен, что я понимаю алгоритм... :(

Название: Теория графов
Отправлено: RawonaM от апреля 22, 2012, 18:16

Нет, все-таки контрпример правильный. Длина пути к В не будет правильной. Но меня смущает

Цитировать
It then sets d(A,B)=2 and chooses another edge (y,C) minimizing d(A,y)+d(y,C); the only choice is (A,C) and it sets d(A,C)=3.

тут мне кажется ошибка. Следущую вершину после В он должен взять С вроде как.

Лингвофорум

Общий раздел => Наука и техника => Математика => Тема начата: RawonaM от июня 7, 2011, 19:36