Граф - квадрат ориентированного графа
Да, это будет вопрос домашней работы (я учусь не в университете), но я не прошу решения. Вместо этого я надеюсь уточнить сам вопрос.
В CLRS 3-е издание, стр. 593, акциз 22.1-5,
Квадрат ориентированного графа G = (V, E) - это граф G^2 = (V, E^2) такой, что (u,v) ∈ E^2 тогда и только тогда, когда G содержит путь с не более чем двумя края между вами и v. Опишите эффективные алгоритмы для вычисления G2 из G как для представления списка смежности, так и для представления матрицы смежности G. Проанализируйте время выполнения ваших алгоритмов.
Однако во 2-м издании CLRS (я больше не могу найти ссылку на книгу), стр. 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?
2 ответа
Да, это именно то, что это значит. E^2 должен содержать (u,v) тогда и только тогда E содержит (u,v) или есть w в Vтакой, что E содержит как (u,w) а также (w,v),
Другими словами, E^2 в соответствии с новым определением является союз E а также E^2 согласно старому определению.
Что касается вашего последнего вопроса: не имеет значения, какие еще пути между u а также v существуют (если они есть). Итак, если есть два пути между u а также vодин с двумя ребрами и один с тремя ребрами, затем (u,v) должен быть в E^2 (согласно обоим определениям).
Квадрат графа G, G^2 определен теми вершинами V', для которых d(u,v)<=2, а ребра G' группы G ^ 2 - это все те ребра G, которые имеют обе конечные вершины из V'