Дан неориентированный взвешенный граф. Для любого введенного n-числа вершин и m-числа дуг (m>n) сформировать граф со случайными связями между вершинами и случайными весами дуг. Определить набор методов, позволяющих:
- определить, является ли граф связным (т.е. из любой вершины достижима любая гругая вершина)
- определить, существуют ли в графе циклы (из одной (любой) вершины вернуться в нее же, проходя по дугам не более одного раза)
- определить, существуют ли в графе Эйлеровы циклы (возможность вернуться в вершину, пройдя по всем вершинам и по всем дугам только 1 раз)
- определить, существуют ли в графе Эйлеровы пути (возможность пройти по всем вершинам графа произвольное количество раз при обязательном условии прохождения по всем дугам точно 1 раз).
Обратить внимание на скорость вычислений. Предложить варианты распараллеливания.
Опубликован 20.05.2015 в 22:26