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

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

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

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