Проверка покрытия вершин Quadrati c -time - PullRequest
Новая
       2

Проверка покрытия вершин Quadrati c -time

0 голосов
/ 22 января 2020

Предположим, вам дан ненаправленный граф G с n вершинами и m ребрами, представленными n x n матрицей смежности A, и вам также дано подмножество вершин S (представлен массивом размером m). Как вы можете проверить, является ли S покрытием вершин G с квадратичной сложностью времени и пространства?

По определению покрытия вершин я знаю, что мы требуем, чтобы каждое ребро было инцидентным к вершине, содержащейся в S.

Я легко могу придумать алгоритм cubi c: перебрать матрицу смежности; каждый 1 представляет ребро (u, v). Проверьте, есть ли u или v в S. Если нет, ответ - нет. Если мы дойдем до конца матрицы смежности, ответ - да.

Но как я могу сделать это в O(n^2) времени? Я предполагаю, что единственное реальное «наблюдение», которое я сделал до сих пор, - это то, что мы можем пропустить промежуточные строки, перебирая матрицу смежности, если мы уже нашли вершину, соответствующую этой строке, в S. Однако это мне не очень помогло.

Может кто-нибудь помочь мне (или указать мне правильное направление)?

Спасибо

1 Ответ

1 голос
/ 22 января 2020

Создайте массив T, который является позициями всех элементов НЕ в S.

А затем: 

for i in T:
    for j in T:
        if A[i][j] == 1:
            return False
return True
...