Рубрики

Проблема покрытия вершин | Набор 1 (введение и приблизительный алгоритм)

Покрытие вершин неориентированного графа — это подмножество его вершин, так что для каждого ребра (u, v) графа либо «u», либо «v» находится в покрытии вершин. Хотя имя и есть Vertex Cover, набор покрывает все ребра данного графа. Для неориентированного графа задача покрытия вершин состоит в том, чтобы найти покрытие вершин минимального размера .

Ниже приведены некоторые примеры.

Проблема покрытия вершин является известной проблемой NP Complete , т. Е. Для нее нет решения за полиномиальное время, если P = NP. Тем не менее, существуют приблизительные алгоритмы полиномиального времени для решения проблемы. Ниже приведен простой примерный алгоритм, адаптированный из книги CLRS .

Примерный алгоритм для покрытия вершин:

1) Initialize the result as {}
2) Consider a set of all edges in given graph.  Let the set be E.
3) Do following while E is not empty
...a) Pick an arbitrary edge (u, v) from set E and add 'u' and 'v' to result
...b) Remove all edges from E which are either incident on u or v.
4) Return result 

На диаграмме ниже показано выполнение приведенного выше приближенного алгоритма:

Насколько хорошо работает вышеуказанный алгоритм?
Можно доказать, что приведенный выше приближенный алгоритм никогда не находит покрытие вершин, размер которого более чем в два раза больше минимально возможного покрытия вершин (см. Это для доказательства)

Реализация:
Ниже приведены реализации приведенного выше приближенного алгоритма на C ++ и Java.

C ++

// Программа для печати Vertex Cover заданного неориентированного графа
#include<iostream>
#include <list>

using namespace std;

  
// Этот класс представляет неориентированный граф, используя список смежности

class Graph

{

    int V;    // Количество вершин

    list<int> *adj;  // Указатель на массив, содержащий списки смежности

public:

    Graph(int V);  // Конструктор

    void addEdge(int v, int w); // функция для добавления ребра на график

    void printVertexCover();  // печатает обложку вершины

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

  

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w); // Добавить w в список v.

    adj[w].push_back(v); // Поскольку граф не является ненаправленным

}

  
// Функция для печати обложки вершины

void Graph::printVertexCover()

{

    // Инициализируем все вершины как не посещенные.

    bool visited[V];

    for (int i=0; i<V; i++)

        visited[i] = false;

  

    list<int>::iterator i;

  

    // Рассмотрим все ребра по одному

    for (int u=0; u<V; u++)

    {

        // Край выбирается только тогда, когда посещены [u] и посещены [v]

        // ложны

        if (visited[u] == false)

        {

            // Пройдите через все смежные области и выберите первое

            // еще не посещенная вершина (мы в основном выбираем ребро

            // (u, v) от остальных ребер.

            for (i= adj[u].begin(); i != adj[u].end(); ++i)

            {

                int v = *i;

                if (visited[v] == false)

                {

                     // Добавить вершины (u, v) к результирующему набору.

                     // Делаем посещенные вершины u и v так, чтобы

                     // все ребра от / к ним будут игнорироваться

                     visited[v] = true;

                     visited[u]  = true;

                     break;

                }

            }

        }

    }

  

    // Распечатать обложку вершины

    for (int i=0; i<V; i++)

        if (visited[i])

          cout << i << " ";

}

  
// Программа драйвера для тестирования методов класса графа

int main()

{

    // Создать график, приведенный на диаграмме выше

    Graph g(7);

    g.addEdge(0, 1);

    g.addEdge(0, 2);

    g.addEdge(1, 3);

    g.addEdge(3, 4);

    g.addEdge(4, 5);

    g.addEdge(5, 6);

  

    g.printVertexCover();

  

    return 0;

}

Джава

// Java-программа для печати покрытия вершин заданного неориентированного графа

import java.io.*;

import java.util.*;

import java.util.LinkedList;

  
// Этот класс представляет неориентированный граф, используя список смежности

class Graph

{

    private int V;   // Количество вершин

  

    // Массив списков для представления списка смежности

    private LinkedList<Integer> adj[];

  

    // Конструктор

    Graph(int v)

    {

        V = v;

        adj = new LinkedList[v];

        for (int i=0; i<v; ++i)

            adj[i] = new LinkedList();

    }

  

    // Функция для добавления ребра в график

    void addEdge(int v, int w)

    {

        adj[v].add(w);  // Добавить w в список v.

        adj[w].add(v);  // График не ориентирован

    }

  

    // Функция для печати обложки вершины

    void printVertexCover()

    {

        // Инициализируем все вершины как не посещенные.

        boolean visited[] = new boolean[V];

        for (int i=0; i<V; i++)

            visited[i] = false;

  

        Iterator<Integer> i;

  

        // Рассмотрим все ребра по одному

        for (int u=0; u<V; u++)

        {

            // Край выбирается только при посещении [u]

            // и посещенный [v] ложный

            if (visited[u] == false)

            {

                // Пройдите через все смежные области и выберите

                // первая еще не посещенная вершина (мы в основном

                // выбираем ребро (u, v) из оставшихся ребер.

                i = adj[u].iterator();

                while (i.hasNext())

                {

                    int v = i.next();

                    if (visited[v] == false)

                    {

                         // Добавить вершины (u, v) к результату

                         // устанавливать. Делаем вершины u и v посещенными

                         // чтобы все ребра от / до них были

                         // быть проигнорированным

                         visited[v] = true;

                         visited[u]  = true;

                         break;

                    }

                }

            }

        }

  

        // Распечатать обложку вершины

        for (int j=0; j<V; j++)

            if (visited[j])

              System.out.print(j+" ");

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

        // Создать график, приведенный на диаграмме выше

        Graph g = new Graph(7);

        g.addEdge(0, 1);

        g.addEdge(0, 2);

        g.addEdge(1, 3);

        g.addEdge(3, 4);

        g.addEdge(4, 5);

        g.addEdge(5, 6);

  

        g.printVertexCover();

    }

}
// Этот код предоставлен Aakash Hasija


Выход:

0 1 3 4 5 6

Сложность времени вышеупомянутого алгоритма O (V + E).

Точные алгоритмы:
Хотя задача является NP-полной, она может быть решена за полиномиальное время для следующих типов графиков.
1) Двухсторонний график
2) Граф дерева

Проблема проверки того, существует ли покрытие вершин размером, меньшим или равным данному числу k, также может быть решена за полиномиальное время, если k ограничено O (LogV) (см. Это )

Мы скоро будем обсуждать точные алгоритмы для покрытия вершин.

Эта статья предоставлена Shubham . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Проблема покрытия вершин | Набор 1 (введение и приблизительный алгоритм)

0.00 (0%) 0 votes