Поиск по яндексу ничего не дал.

Здравствуйте, C-D.

Задача поставлена так, что никто толком ответить не сможет.

Во-первых, графы бывают разные — ориентированные, взвешенные, мультиграфы, с крашенными ребрами и вершинами.
Во-вторых, существует уйма способов представления графов — матрицами смежности и инцидентности, списками ребер и т. д.

Кроме того, еще можно понять сложность поиска циклов, — но петель? Что сложного в поиске петель?

Здравствуйте, Аноним, Вы писали:

А>Во-первых, графы бывают разные — ориентированные, взвешенные, мультиграфы, с крашенными ребрами и вершинами.
А>Во-вторых, существует уйма способов представления графов — матрицами смежности и инцидентности, списками ребер и т. д.

Простите, а не подскажите где про это можно прочитать. А то случайно наткнулся на Ваш ответ и стало интересно.

Здравствуйте, Аноним, Вы писали:

А>Во-первых, графы бывают разные — ориентированные, взвешенные, мультиграфы, с крашенными ребрами и вершинами.
Граф ориентированный.
А>Во-вторых, существует уйма способов представления графов — матрицами смежности и инцидентности, списками ребер и т. д.
Матрица смежности, список ребер.
А>Кроме того, еще можно понять сложность поиска циклов, — но петель? Что сложного в поиске петель?
Не знаю как правильно называется. Путей вида : A>B>C>A

Здравствуйте, C-D, Вы писали:

C-D>Не знаю как правильно называется. Путей вида : A>B>C>A

Правильно называется циклов. А вот эффективного алгориьтма их поиска не существует

Здравствуйте, C-D, Вы писали:

C-D>Не знаю как правильно называется. Путей вида : A>B>C>A
Я как то решал подобную задачу путём n-кратного умножения матрици смежности саму на себя (где n количество вершин в графе)

Здравствуйте, DOOM, Вы писали:


DOO>Правильно называется циклов. А вот эффективного алгориьтма их поиска не существует
Мне любой подойдет.
2Anatoliy Elsukov
Подробней можно?

Здравствуйте, <Аноним>, Вы писали:

При возведении матриц смежности в степень (k) получаем матрицу достижимости за k шагов. Появление единиц на главной диагонали свидетельствует о наличии циклов. Длинна максимального цикла равна количеству вершин в графе.