Да, это будет домашнее задание (я занимаюсь самообучением, а не для университета), но я не прошу решения. Вместо этого я надеюсь прояснить сам вопрос.
В 3-е издание CLRS, стр. 593, акциз 22.1 -5,
Квадратом ориентированного графа G = (V, E) называется граф G2 = (V, E2) такой, что (u,v) ∈ E2 тогда и только тогда, когда G содержит путь с не более чем двумя ребрами между u и v. Опишите эффективные алгоритмы вычисления G2 из G как для представлений G в виде списка смежности, так и в виде матрицы смежности. Проанализируйте время выполнения ваших алгоритмов.
Однако во 2-м издании CLRS (больше не могу найти ссылку на книгу), стр. 530, то же упражнение, но с немного другим описанием:
Квадратом ориентированного графа G = (V, E) называется граф G2 = (V, E2) такой, что (u,w) ∈ E2 тогда и только тогда, когда для некоторого v ∈ V оба (u,v) ∈ E и (v,w) ∈ E. То есть G2 содержит ребро между u и w всякий раз, когда G содержит путь с ровно двумя ребрами между u и w. Опишите эффективные алгоритмы вычисления G2 из G как для представлений G в виде списка смежности, так и в виде матрицы смежности. Проанализируйте время выполнения ваших алгоритмов.
Старое упражнение с «ровно двумя ребрами» я могу понять и решить. Например, для списка смежности я просто делаю v->neighbour->neighbour.neighbour, а затем добавляю (v, Neighbour.neighbour) к новому E2.
Но для нового упражнения с «максимум двумя ребрами» я запутался.
Что означает «тогда и только тогда, когда G содержит путь с не более чем двумя ребрами между u и v»?
Поскольку одно ребро может удовлетворять условию «не более двух ребер», если u и v имеют только один путь, который содержит только одно ребро, следует ли добавить (u, v) к E2?
Что, если у u и v есть путь с 2 ребрами, но есть и другой путь с 3 ребрами, могу ли я добавить (u, v) к E2?
