Zbuduj obwód z wykresu, który wyprowadza 1, jeśli wykres ma niezależny zestaw - algorytm, wykres, redukcja, np, schemat obwodu

Powiedzmy, że mam wykres,

i z tego wykresu chcę utworzyć obwód Kktórych wejścia mogą być ustawione tak, że K wyprowadza wartość true, wykres ma niezależny zestaw wielkości ≥2. Widziałem kilka dobrych rzeczy w Internecie / youtube na temat tego, jak to zrobić, ale zastanawiałem się, czy istnieje standardowy zestaw kroków, które należy wykonać, jak to zrobić.

Mój proces myślowy był w pewnym sensie: Niech obwód przyjmuje krawędzie jako dane wejściowe, a wyjście 1 (prawda), jeśli brakuje co najmniej jednej krawędzi (ponieważ ta krawędź jest niezależnym zbiorem).

Ale jeśli mam być szczery, mam problem z owinięciem się wokół tego.

Odpowiedzi:

Twoje podejście jest poprawne, ale istniejejeszcze łatwiejszy sposób: policz krawędzie na wykresie. Dla N węzłów, jeśli | E | <N * (N-1) / 2, masz co najmniej jeden niezależny zbiór wielkości> = 2. Wszystko, co musisz zrobić, to jeden brakujący brzeg, jak zauważyłeś.

Aby znaleźć Największa niezależny zestaw, istnieje sztuczka transformacjito jest względnie łatwe w koncepcji: Odwróć wykres: zmień wszystkie nie-krawędzie i krawędzie, na przykład, twój zaksięgowany wykres zawiera 4 z możliwych 6 krawędzi. Odwróć to, więc krawędzie twojego wykresu są tylko DB i DC.

Weź wynikowy wykres i znajdź największą kliszę (na tym jest dużo materiału) Ta największa klika jest największym niezależnym wykresem.