Zbiory dominujące

https://en.wikipedia.org/wiki/Dominating_set

WPROWADZENIE

Zbiór dominujący (ang. dominating set) grafu nieskierowanego G=(V,E) jest to podzbiór S zbioru wierzchołków V taki, że każdy wierzchołek z V, który nie należy do S, ma co najmniej jednego sąsiada w S.

Problem znalezienia najmniejszego zbioru dominującego, jako problem decyzyjny, jest NP-zupełny. Dla danego grafu G i liczby k pytamy, czy najmniejszy zbiór dominujący ma liczność mniejszą lub równą k.

# 5---3---4---1  najmniejsze zbiory dominujące: {3,4}, {4,6}
#   \ |   |
#     6---2

# Testowanie zbioru dominującego.

import unittest

def find_dominating_set(graph):
    pass

class TestDominatingSet(unittest.TestCase):

    def setUp(self):
        self.G = dict()
        self.edges = []   # wstawiamy 3-krotki, graf ważony
        # Wstawiamy wierzchołki i krawędzie do G.

    def test_dominating_set(self):
        dset = find_dominating_set(self.G)
        neighbors = set(dset)
        for source in dset:
            neighbors.update(self.G[source])
        self.assertEqual(len(neighbors), len(self.G))