Как найти все эквивалентные вершины в графе?

Question

Эквивалентные вершины - это те, которые имеют те же «входящие» и «исходящие» вершины.

Может кто-нибудь помочь мне, как подойти к алгоритму?

Я думал, что-то вроде этого: для поиска два вершин в то же время, и если я нахожу равные входящие и выходящие вершины, чтобы напечатать их .. и так далее, так что это будет фактической брутфорсом, но как для этого, например, с рекурсией? Какое лучшее решение?

Answer 1

Вот рекурсивное решение, которое я придумал.

Представьте, что мы удаляем все вершины, кроме двух (не имеет значения, какие два).

В вашем примере, предположим, что мы удалили все вершины, за исключением и б. Обратите внимание на то, что и б эквивалентны тогда и только тогда, когда существует ребро от к б, и есть ребро из б к . Это наш базовый футляр.

Представьте, что мы добавляем недостающие вершины один за другим (порядок не имеет значения). Мы должны рассмотреть два случая. i) Нам нужно проверить, стал ли какой-либо набор вершин эквивалентным при добавлении вершины. ii) Нам нужно проверить, эквивалентен ли какой-либо набор вершин, которые были эквивалентными.

Случай 1.

В вашем примере, предположим, что мы добавили гр, (напомним, что мы начали с вершинами и б). Мы точно знаем, что a и b не являются эквивалентными. Зачем?Так, имеет исходящую вершину, что б отсутствует, и что исходящая вершина не с, потому что с не был на графиком ранее. Поэтому нам нужно только проверить, есть ли какая-либо вершина, эквивалентная c. Мы можем сделать это эффективно просто, проверив входящие вершины исходящих вершин c и исходящие вершины входящих вершин c. Затем мы выясним, что a и c эквивалентны.

Примечание: Я использую = символ для обозначения equility вершин в оставшейся части поста.

Чтобы быть более общим, когда мы добавляем новую вершину, (скажем г) на графике, мы знаем, за то, что не существует пара вершин, (скажем х и у), что х! = у перед добавлением г и х = у после добавления г. Это происходит потому, что:

Предположим, что х имеет исходящий или входящий вершину ш что у не без потери общности. Мы знаем, что w! = Z, потому что мы не добавили z. Затем, после добавления z, y все еще пропускает вершину w. Поэтому x! = Y после добавления вершины z. Поэтому нам нужно только проверить, есть ли какие-либо вершины, эквивалентные z.

Случай 2

Этот случай гораздо проще. В вашем примере, предположим, что мы, наконец, добавить д, (напомним, что мы добавили вершины , б и с ранее). Мы вычислили, что a и c были эквивалентными, и нам нужно проверить, все ли они эквивалентны после добавления d. Обратите внимание, что все, что нам нужно сделать, это проверить, являются ли оба a и c имеют d в качестве исходящей или входящей вершины. И сравните их.

---

Итак, в заключение мы начинаем с двух произвольных вершин и проверяем, являются ли они эквивалентными. Затем мы добавляем каждую вершину по одному, и мы проверяем случай 1 и случай 2, как я описал выше.

Итак, предположим, что у вас есть рекурсивная функция EQ (n), которая возвращает все эквивалентные вершины. Затем, учитывая график с n вершинами, которые вы вызываете EQ (n-1), то есть с отсутствующей одной вершиной (скажем z). И вы проверяете случай 1 и случай 2, чтобы увидеть, как z влияет на общее решение. И в вашем базовом случае у вас есть n = 2, как я уже упоминал в начале.

Таким образом, время работы алгоритма задается как это повторение T (2) = O (1) и Т (п) = Т (п - 1) + О (п). Поэтому время работы O (n^2).

Answer 2

Один из подходов состоит в том, чтобы добавить списки в каждую вершину, одну для входящих вершин, List ingoingVertices и одну для исходящих вершин, List outgoingVertices. Затем пересечь края для каждой вершины, добавляя посещенную вершину к List outgoingVertices в пределах первой вершины, и каждый раз, когда вы берете край из первой вершины, добавьте первую вершину к List ingoingEdges посещенной вершины. Затем просто перебирайте вершины, проверяя, совпадают ли списки между двумя вершинами, чтобы найти их эквивалентность.

Рекурсивно посещая каждую вершину, а затем выполнение этой вершины будет примерно такой же, как итерация по каждой вершине. Одновременно будет работать Brute, позволяющий сравнивать только две вершины, но для выполнения кода потребуется больше времени и времени.