Графы, Задачи по графам Опции

[setare]

Здравствуйте! Вот и началась самая трудная и не очень для нас понятная тема в дискретной математике графы!!!! И как всегда из-за не имения логического мышления возникли многие вопросы.
6. Мультиграф G = (V,E) представлен в виде списков смежных вершин. Как за время O(V+E) преобразовать его в обычный неориентированный граф G’=(V,E’), заменив кратные ребра на обычные и удалив ребра-циклы?
7. Пусть веса ребер графа G = (V,E) - целые числа в интервале от 1 до  V . Какой скорости работы алгоритма Крускала можно добиться в этом случае? А если весами являются целые числа от 1 до некоторой константы W?
9.Транзитивным замыканием ориентированного графа G = (V,E) называется граф G* = (V,E*), где E* = {(i,j): в графе G существует путь из i в j}. Допустим, что транзитивное замыкание ориентированного ациклического графа может быть построено за время f(модулиV,E), где f - монотонно возрастающая (по каждому аргументу) функция. Докажите, что тогда транзитивное замыкание G* = (V,E*) произвольного ориентированного графа G = (V,E) может быть построено за время f(модулиV,E) + O(V+E*).

3. Постройте граф группы симметрий октаэдра.

Большое вам спасибо!

[Atos]

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

Фух... разобрался наконец вчера полностью с алгоритмом Краскала - благодаря консультации с научником и случайно оказавшимся под рукой чужим конспектам по алгоритмам теории графов (я в своё время на эту часть лекций не смог ходить и готовился к сдаче именно по Корману и иже с ним).

Ключевая деталь: если считать E приблизительно равным V^2, то O(logE)=O(2logV)=O(logV) !!

Так вот: создаётся впечатление, что "массачусетская троица" в описании алгоритмов иногда имела это в виду, а иногда выпускала из вида, что и создало путаницу.
На это указывают следующие противоречивые утверждения в книге:
"время сортировки алгоритма Краскала O(ElogE)"
"Е проходов цикла алгоритма Краскала по O(logE) - то есть O(ElogE)"
"общее время работы O(ElogE)"
"основное время уходит на сортировку"
"общее время работы алгоритма Прима O(ElogV), то есть такая же, как и у алгоритма Краскала"

А теперь конкретно к задаче:
ответ отрицательный, время работы O(ElogV) нельзя уменьшить, какие бы ни были веса рёбер! Просто по тому простому соображению, что время O(ElogV) требуется на работу с независимымы множествами вершин, и от весов абсолютно никак не зависит: после того, как мы отсортировали, на вообще наплевать на конкретные значения весов рёбер, - мы работаем уже только лишь с упорядочением их(эту здравую мысль подсказал научник). А вот если считать, что авторы книги попутались, и в какой-то момент у них вышло, что для сортировки O(ElogE), а для цикла O(ElogV), причём O(ElogV) и O(ElogE)- это разные вещи (вот тогда-то и получается, что основное время уходит на сортировку), то действительно, задача была бы корректной. И тогда в первом случае для сортировки получаем О(min(V,E))~=O(E), во втором О(min(W,E)). Общее время, соответственно, O(ElogV) (что в данном контексте меньше, чем O(ElogE) ) и O(min(W,ElogV)).

Зря, видимо, я теорию графов самой лёгкой назвал ;)

9. Тоже долго думал, но в голову пришёл лишь идиотский способ , основанный на древнем анекдоте:
"-- Задача: вскипятить чайник. Ваши действия?
-- Налить в чайник воды, зажечь газ. поставить чайник на плиту.
-- Исходные условия изменились: в чайнике уже есть вода. Ваши действия?
-- Зажечь газ, поставить чайник на плиту...
-- Неправильно! Так поступил бы физик. Математик выльет воду и скажет, что задача свелась к предыдущей! "

Если знаем, как строить замыкание ациклического графа, то из произвольного графа будем удалять по одной циклической дуге, пока не получим ациклический граф (короче говоря, построим остовное дерево). Причём удалённые дуги запоминаются, и все вершины, входящие в циклы, тоже запоминаются. Теперь строим это самое замыкание за время f(V,E) , причём все добавляемые дуги тоже запоминаем. После этого проверяем для каждого добавленной дуги принадлежность её начальной и конечной вершины к одному циклу, и если это так, то добавляем к графу обратную её дугу(так как, очевидно, в одном цикле из каждой вершины в каждую существует путь), наконец, добавляем все ранее удалённые дуги вместе с обратными к ним. Последние действия, также очевидно, займут не более O(V+E*).
Правда в этих рассуждениях есть очень большой скользкий момент - а кто сказал, что остовное дерево можно построить не более чем f(V,E) операций? но, может быть, прокатит...


3. Можно воспользоваться тем фактом, что группа поворотов октаэдра изоморфна группе поворотов куба, подгруппы, входящие в неё, описаны на тех страницах, которые я сканил ещё в тему Дискретная математика . Надо только уточнить у препода, как именно строить этот граф? Вершины, наверное, будут соответствовать подгруппам, вот как строить рёбра... может быть, по общим элементам подгрупп...