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

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

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

[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 5:50