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

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

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!
Это выражение лишнее (случайно попало), или я что-то недопонял?