Правила форума
Здравствуйте! Вот и началась самая трудная и не очень для нас понятная тема в дискретной математике графы!!!! И как всегда из-за не имения логического мышления возникли многие вопросы.
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. Постройте граф группы симметрий октаэдра.
Большое вам спасибо!
 Графы, Задачи по графам |
