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