Здравствуйте! Вот и началась самая трудная и не очень для нас понятная тема в дискретной математике графы!!!! И как всегда из-за не имения логического мышления возникли многие вопросы.
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. Постройте граф группы симметрий октаэдра.

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

по мне так самая лёгкая и нагладная линейное программирование посложнее будет
За выходные постараюсь посмотреть. И совет: взять в читалке Кормана, Лейзермана и Ривеста "Алгоритмы: Построение и анализ". Будешь приятно поражена. Это библия прикладного матемтика!! В инете тоже можно найти, но без иллюстраций

Спасибо за книгу! Я уже скачала ее, но что-то нахажу пока что только некоторые мои задания, а какого-нибудь решения нет. Может надо еще более отчетливее поискать, не знаю! Но спасибо вам!

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

ИзвиниЁ но я что!то не очень врубилась что ты вообще имел в виду. Ты сказал:"ставим единички в соответствующие ячейки матрицы". А в какие? И как мы проходим по всем элементам? Этот граф представлен как обыкновенный граф? Просто мне в задаче не поняно как выглядят списки смежных вершин.

Вот у меня есть решение задачи о НОПе. Но проблема в том что моя постановка задачи содержит следующую фразу:Покажите как можно вычислить длину НОП, используя память размера 2min(m,n) + O(1). И я что!то не понимаю что мне делать с этим временем. Нигде не могу найти хотя разбор задачи с использованием времени.

способы задания графов
Для каждой вершине(V штук) проходим все элементы списка её смежных вершин. Каждое ребро(i--j) представлено двумя такими элементами - в списках смежности для вершин i и j. Поэтому сделаем не более (V+2E) операций. Когда видим в списке для вершины i вершину j, ставим единицу в ячейки [i,j] и [j,i] матрицы. Стоп. Это какая задача?

Спасибо! Это вот такая задача:
5. Задача о наибольшей общей подпоследовательности (НОП) состоит в том, чтобы найти общую подпоследовательность наибольшей длины для двух данных последовательностей  и . Покажите как можно вычислить длину НОП, используя память размера 2min(m,n) + O(1).

C НОП всё элементарно просто. Никаких ограничений на время нет, значит могжно использовать сколь угодно тупой алгоритм. Поэтому просто перебираем ВСЕ общие подпоследовательности. Память нужна для запоминания текущей подп-ти и уже найденной максимальной на данный момент подп-ти. А длина ни одной из них, естественно, не может превышать min(m,n). Ну и О(1) на сравниваемуе текущие элементы...

Долго думал на алгоритмом Краскала... Потом подключил научника... Черт, меня выгоняют из интернет-ласса... В общем, до пятницы...

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

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

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

Ключевая деталь: если считать 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. Можно воспользоваться тем фактом, что группа поворотов октаэдра изоморфна группе поворотов куба, подгруппы, входящие в неё, описаны на тех страницах, которые я сканил ещё в тему Дискретная математика . Надо только уточнить у препода, как именно строить этот граф? Вершины, наверное, будут соответствовать подгруппам, вот как строить рёбра... может быть, по общим элементам подгрупп...

Ой, большущее спасибо!!!! Ты мне очень очень помог!Остальные попробую сама решить, но если возникнут вопросы надеюсь можно будет опять обратиться!
И что-то не очень хорошо получилось, что еще, можно сказать, я побеспокоила твоего научного руководителя. Еще раз спасибо, мне и этому форуму очень повезло, что есть такой хороший человек, который помогает людям!!!!

Привет еще раз! Вот сегодня 3 часа сидела в библиотеке и так и не смогла решить не одного примера! Что за безобразие! Хотя честно говоря что!то получилосьб! Но у меня большая пребольшая просьба не мого бы ты мне помочь решить еще некоторые задачи! Я их никак не могу решить нигде не могу найти необходимой теории.
1. Назовем k-раскраской неориентированного графа (V,E) функцию c: V->{0,1,2, ... , k-1}, для которой c(u ) не равно c(v) для любых двух смежных вершин u и v (т.е. концы любого ребра должны иметь разные цвета). Пусть d - максимальная степень вершин неориентированного Покажите, что G имеет (d+1)-раскраску.
Еще раз 3) задание про группу симмтрии октаэдра. Я просто не понимаю даже как этот граф будет выглядеть, а наш препод тоже мне сказал: я даже об этом никогда не задумывался. К сожалению и я тоже.
8. Найдите хотя бы одно решение или установите несовместимость следующей системы неравенств:
{ х1 - х2 <= 4, х1 - х5 <= 5, х2 - х4 <= -6, х3 - х2 <= 1, х4 - х1 <= 3,
{х4 - х3 <= 5, х4 - х5 <= 10, х5 - х3 <= -4, х5 - х4 <= -8.
Я попыталась решить, но проблема в том что я не могу найти ни одного решения. У меня все сокрашается. И я не знаю что делать.

10. Пусть имеется сеть G = (V,E) и два потока f1 и f2 на ней. Рассмотрим их сумму (функцию V*V ->R ): (f1 + f2)(u,v) = f1 (u,v) +f2 (u,v). Каким требованиям определения потока она удовлетворяет обязательно, а каким может не удовлетворять?

Большое вам спасибо! Только, извините, я не хочу тебя торопить, но не мог бы ты хотя бы какие- нибудь мысли написать до понедельника. Просто в пон мне уже надо сдавать. Еще раз спасибо.

Он, что, дебил?! "Принеси то, не знаю что..."
Ну уж это элементарно просто вспомни определение. Подсказка: если у нас есть труба, и она может пропускать 100 литров варенья в час , то 200 литров(=100+100) в час лопнет, но не пропустит.

1. Да и это тоже совсем элементарно. Просто раскрашиваем вершины по одной, и так как вершина инцидентна не более чем с d, то мы всегда можем выбрать другую краску(их d+1).

Извини, но я как-то не очень врубилась. Что ты имеешь ввиду когда говоришь , что вершина онцидентна с д? с д чего? и почему мы так решили, что раскрасек будет именно д+1, а не например д-1?

setare, ну что ж тут непонятного?
Такое впечатление, что ты оглушена и ослеплена священным страхом перед Великой и Ужасной Теорией Графов! Забудь про то, что это высшая математика, привлеки обычный здравый смысл. Как я, например. Я в жизни ни разу даже учебник по графам не открывал - ну, не было у меня такого курса.. Сюда заглянул исключительно из любопытства. Давай разберемся.

Вот граф (его высочество), причем (это важно!) никакая его вершина не соединяется с более, чем d других вершин (видимо, уважаемый Атос называет словом "инцидентность" обычную смежность. Можно принять, если вспомнить английское incident, что можно перевести как "столкновение". Так, Атос?). Процесс окраски вершин будем проводить тупо - одну за другой, в произвольном порядке, это не важно. Когда красим - смотрим на смежные вершины. Некоторые из них могут быть уже закрашены, некоторые - нет. Смотрим на уже закрашенные смежные вершины. Сколько красок на них могло пойти? Могла и всего одна (если они друг с дружкой не смежные), но нам важно, что не больше, чем d, поскольку самих смежных вершин не больше, чем d. А если так, то у нас всегда есть в запасе по крайней мере одна краска - красок-то всего d+1, так? Таким образом, уверждение доказано. А почему d+1, а не d-1 или не 2d+3 - так это по условию! Тебя же просят доказать, что граф этот можно раскрасить в d+1 цветов. Если завтра тебе дадут такую же задачу про d-1, то будешь решать про d-1, а пока - живи и радуйся!



[m]lapp, молодец, чуть-чуть опередил с ответом! Респект. Хорошее обьяснение.
Atos[/m]

не более чем с d другими вершинами. По определению степени. "Надо знать формулировки!" (как постоянно твердит мне научник... ) предположили, что у нас есть d+1 красок и доказали, что их хватает для того, чтобы инцидентные вершины были разных цветов.

8.Добиваемся неотрицательности правых частей неравенств. Замена x5=x'5-8. Переписываем x'5-x4<=0; x'5-x3<=4; x4-x'5<=2; x1-x'5<=-3. Теперь осталось только одо неравенство x1-x'5<=-3 с отрицательной правой частью. Замена x1=x'1-3. Переписываем x'1-x'5<=0; x'1-x3<=0; x'1-x2<=7; x4-x'1<=0. Теперь все правые части неотрицательны, значит нулевой начальный план допустим. Решение (0-3,0,0,0,0-8)=(-3,0,0,0,-8).

Спасибо! Значит если мы сейчас нашли это решение следовательно мы уже не устанавливаем несовместность системы? Правильно?

Lapp спасибо за разъяснения!! Я врубилась!!!

2 Setare:
да, правильно, если хоть одно решение найдено, то система совместна, и доказывать ее несовместность было бы по меньшей мере странно
Молодец, Звездочка, так держать! Побольше уверенности. Не так страшен черт.. ;)

2 Atos:
Спасибо, приятно было разобраться в решении неравенства. Метод забавный и несложный, но в одну вещь я не врубаюсь. Смотри, ты пишешь:

Откуда тут берется x'1-x3<=0 ? В исходных неравенствах только 3 штуки включают в себя x1!
Это выражение лишнее (случайно попало), или я что-то недопонял?

Да уж и вправде я тоже заметила про это неравенство! Ну ладно, надеюсь оно ни на что на повлияет! Кстати,Lapp, откуда ты знаешь что означает мой ник? Или ты к другой обращался?

Конечно, к тебе! Тут никого и нету больше..
Он созвучен с английским словом star. Я дал себе труд поискать, и нашел, что это действительно так (по-персидски). Вообще, любопытно анализировать ники - в них люди пытаются выразить свою суть. Причем так, как они сами ее понимают, хотя способ может быть сильно непрямым.. Но это тема для другого форума - к математике она не имеет отношения.
Один вопрос, если уж не то пошло: кто изображен на твоем аватарчике?

Случайно. В спешке при copy+paste

Спасибо всем всем за помощь!!! Все таки 3 задание не получается, да???Просто, к сожалению, нет понятия как вообще можно изобразить этот граф. Ну да ладно.. Спасибо!!!
Lapp, на аватарчике никто особенный не изображен: просто маленькая девочка с кошечкой на рассвете!! И все!!!

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

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

Ну, честно говоря, это уж лучше чем ничего. Потому что наш препод мне сказал только то, что октаэдр подобен кубу и все. Остальное он сказал, я и сам не знаю как делать, но ты обязательно сделай. Вот так!Спасибо за объяснения, я может попробую как нибудь все это написать и посмотрим что получится. Мы все в группе с этим заданием сидим А Atos по-моему уже не придет на этих выходных, поэтому я воспользуюсь вашим объяснением!! Спасибо большое!!!!! А вы случайно в паскале не разбираетесь???? Просто я уже 3-4 недели бьюсь в разделе задачи, но никто мне вообще не отвечает. А там задачка серьезная!!!!

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

Объязательно!!!! Если конечно он скажет правильное решение!

Спасибо, спасибо большое за помощь!!!! Вы мне сделали самый лучший подарок на Новый год!!!! Препод мне засчитал все и поставил 5 за экзамен!!!!Спасибо!!!!!!!

"Come baaaaaack!!" (Copyright - game The 7th Guest)

Who must come back?

Намек понял