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

[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. Постройте граф группы симметрий октаэдра.

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

[Lapp]

Все таки 3 задание не получается, да???Просто, к сожалению, нет понятия как вообще можно изобразить этот граф.

Хм.. Забавно. Эта задача кажется выбивающейся из ряда других в задании. В сравнении с другими (типа раскрасок, например, которую даже я понял ) она кажется сложнее. Точнее, она требует дополнительных знаний - знаний по теории групп. Если теория групп у вас была в курсе (или есть), то ты, возможно, знаешь, что группа симметрий октаэдра состоит из 24 элементов, если говорить только о поворотах, и соответственно 48 элементов, если добавить зеркальные отображения. Эта группа абсолютно идентична группе симметрии куба - ведь октаэдр это не что иное как обрезанный куб (если мы соединим середины соседних граней куба, полученная фигура представит октаэдр). Не знаю, имеет ли смысл пояснять элементы этой группы.. Кратко: по 3 поворота вокруг 3 осей через центры граней (9), по 2 вокруг 4 осей через вершины (8), по 1 вокруг 6 осей через центры ребер (6), плюс тождественное преобразование.
Как видишь, тут все просто и прозрачно. Но как я уже говорил - я полный профан в графах (из грязи я лучше сразу в князи ). Так что боюсь, что я плохо представляю, что именно подразумевается под "графом группы". Впрочем, я могу предположить (ну почему-то мне так кажется!), что он должен являть собой сам октаэдр (поскольку группа эта годится и для куба, и для трехосной фигуры [типа системы координат], то не нужно думать, что я считаю, что группа симметрии всегда является самим исходным телом). Вершины графа будут представлять состояния, а ребра - преобразования. Исходя из этого, следует полагать, что некоторые (а скорее всего и все) ребра будут сдублированы (а может и не раз). Какие и сколько - надо подумать. Кроме того, помимо ребер самого октаэдра к ребрам графа следует добавить и диагонали - их три. И получится такая забавная фигурка из проволочек..

Не принимай особенно близко к сердцу всю эту галиматью. Просто мне захотелось пофантазировать.. ;) Если это совсем уж чушь - надеюсь, благородный Атос не даст ей завладеть твоим мозгом..