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

[GaLL]

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

Напрямую же.

Допустим дан некий связной граф 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?).

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

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

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

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

[RawonaM]

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

Напрямую же.

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

[GaLL]

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

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

[GaLL]

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

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

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

[RawonaM]

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

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

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

[RawonaM]

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

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

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

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

[GaLL]

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

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

[RawonaM]

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

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

[RawonaM]

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

[RawonaM]

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

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

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

[GaLL]

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

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

[RawonaM]

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

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

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

[GaLL]

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

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

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

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

[RawonaM]

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

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

[GaLL]

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

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

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

[GaLL]

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

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

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

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

[RawonaM]

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

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

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

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

[GaLL]

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

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

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

[GaLL]

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

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

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

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

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

[RawonaM]

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

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

[GaLL]

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

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

[RawonaM]

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

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

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

[RawonaM]

Если она отличается от предыдущей на вес ребра e, значит, ответ "Да", иначе "Нет".

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

[GaLL]

Если она отличается от предыдущей на вес ребра e, значит, ответ "Да", иначе "Нет".

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

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