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

[GaLL]

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

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

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

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

[GaLL]

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

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

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

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

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

[RawonaM]

Вес остова изменился на ноль, т. е. на вес убранного ребра.

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

[GaLL]

Вес остова изменился на ноль, т. е. на вес убранного ребра.

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

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

[RawonaM]

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

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

Верно?

[RawonaM]

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

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

[RawonaM]

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

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

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

[GaLL]

Похожий вопрос. Дан граф с весами на гранях, вершины 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]

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

Оказывается, до сих пор не придумано ничего лучше, чем решать эту задачу через поиск длин кратчайших путей между всеми парами вершин:
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]

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

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

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

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

[RawonaM]

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

[RawonaM]

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

[RawonaM]

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]

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

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.

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