Odłącz wszystkie wierzchołki na wykresie - Algorytm

Question

Szukam algorytmu, który znajdzie minimalny podzbiór wierzchołków w taki sposób, że po usunięciu tego podzestawu (i krawędzi łączących te wierzchołki) z wykresu wszystkie pozostałe wierzchołki staną się niepołączone (tzn. Wykres nie będzie mieć dowolne krawędzie).

• Czy istnieje taki algorytm?
• Jeśli nie: Czy możesz polecić heurystyki do wyznaczenia wierzchołków?

Posiadam podstawową wiedzę z zakresu teorii grafów, więc przepraszamy za wszelkie nieprawidłowości.

Answer 1

IIUC, jest to klasyczny problem o nazwie Minimum Vertex Cover, który jest, niestety, NP Complete.

Na szczęście model most intuitive and greedy possible algorithm jest tak dobry, jak się da w tym przypadku.

Answer 2

Algorytm zachłanności jest 2-przybliżeniem dla pokrywy wierzchołków, która pod w teorii, pod Unique Games Conjecture, jest tak dobra, jak to tylko możliwe. W praktyce rozwiązanie formuły zakrycia wierzchołków jako programu typu integer zapewne przyniesie znacznie lepsze wyniki. Program jest

min sum_{v in V} x(v) 
s.t. 
forall {u, v} in E, x(u) + x(v) >= 1 
forall v in V, x(v) in {0, 1}. 

Answer 3

Spróbuj w ten sposób:

• zdefiniować zmienną policzyć liczbę wierzchołków, począwszy od 0;
• Utwórz maks. Stertę wierzchołków posortowanych według długości sąsiedniej listy każdego wierzchołka;
• Usuń wszystkie krawędzie z pierwszego wierzchołka sterty (ten z największą liczbą krawędzi) i usuń go ze sterty, dodając 1 do liczby;

• Zmień kolejność sterty teraz, gdy liczba krawędzi wierzchołków się zmieniła, powtarzając poprzedni krok, dopóki długość sąsiedniej listy z pierwszego wierzchołka nie będzie równa 0;

  Heap Q 
  int count = 0 
  
  while(1){ 
  
      Q = Create_Heap(G) 
      Vertex first = Q.pop 
      if(first.adjacents.size() == 0) { 
       break 
      } 
  
      for(Vertex v : first.adjacent){ 
       RemoveEdge(first, v) 
       RemoveEdge(v, first) /* depends on the implementation */ 
      } 
  
      count = count + 1 
  
  } 
  
  return count