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

[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]

самая трудная и не очень для нас понятная тема в дискретной математике графы!

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

[setare]

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

[Atos]

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

[setare]

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

[setare]

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

[Atos]

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

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

Вот у меня есть решение задачи о НОПе.

Стоп. Это какая задача?

[setare]

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

[Atos]

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

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

[setare]

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

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

[setare]

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

Сообщение отредактировано: setare - 9.12.2005 22:07

[setare]

Привет еще раз! Вот сегодня 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). Каким требованиям определения потока она удовлетворяет обязательно, а каким может не удовлетворять?

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

[Atos]

а наш препод тоже мне сказал: я даже об этом никогда не задумывался

Он, что, дебил?! "Принеси то, не знаю что..."

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).

[setare]

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

[Lapp]

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

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



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

Сообщение отредактировано: Atos - 14.12.2005 9:50

[Atos]

вершина онцидентна с д? с д чего?

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

и почему мы так решили, что раскрасек будет именно д+1, а не например д-1?

предположили, что у нас есть 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).

[setare]

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

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

[Lapp]

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

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

Переписываем x'1-x'5<=0; x'1-x3<=0; x'1-x2<=7; x4-x'1<=0. Теперь все правые части неотрицательны

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

[setare]

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