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

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

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

не более чем с 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).