Zbiory niezależne

https://en.wikipedia.org/wiki/Independent_set_(graph_theory)

WPROWADZENIE

Zbiór niezależny (ang. independent set) grafu nieskierowanego G=(V,E) jest to podzbiór S zbioru wierzchołków V, taki że żadne dwa wierzchołki z S nie są połączone krawędzią z E. 'Maksymalny zbiór niezależny' (ang. maximal independent set) nie jest podzbiorem większego zbioru niezależnego. 'Największy zbiór niezależny' (ang. maximum independent set) jest zbiorem niezależnym o największej liczności w G. Problem znalezienia największego zbioru niezależnego jest NP-trudny.

Rozważmy graf nieskierowany, w którym wierzchołki grafu mają przyporządkowaną wagę (liczba dodatnia). W takim grafie rozważa się problem zbioru niezależnego o największej wadze, tzn. suma wag wierzchołków zbioru niezależnego ma być największa. Problem największego zbioru niezależnego jest szczególnym przypadkiem, w którym wagi wszystkich wierzchołków są równe jeden.

# Testowanie zbioru niezależnego.

import unittest

def find_independent_set(graph):
    pass

class TestIndependentSet(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_independent_set(self):
        iset = find_independent_set(self.G)
        for edge in self.edges:
            source, target, weight = edge
            self.assertFalse(source in iset and target in iset)

ALGORYTM Z POWROTAMI

Liczba potencjanych rozwiązań do sprawdzenia to 2^N, bo każdy wierzchołek może należeć lub nie do zbioru niezależnego.

# 0 --- 1 --- 2   graf nie jest dwudzielny, bo są trójkąty
# |   / |     |
# |  /  |     |   niezależne: 0, 4, 2 (najlepszy)
# | /   |     |
# 3 --- 4 --- 5

N = 6   # liczba wierzchołków

import sys
recursionlimit = sys.getrecursionlimit()
sys.setrecursionlimit(max(N*2, recursionlimit))

# Definicja prostego grafu spójnego.
graph = dict()
edges = [(0, 1, 1), (0, 3, 1), (1, 3, 1), (1, 4, 1), 
    (1, 2, 1), (2, 5, 1), (3, 4, 1), (4, 5, 1)]
for edge in edges:
    add_edge_undirected(graph, edge)

node_list = list(graph)
used = dict((node, 0) for node in graph)   # pokrycie wierzcholka
tmp_set = set()        # kandydat na największy zbiór niezależny
independent_set = set()   # największy zbiór niezależny

def add_iset(source):
    """Add a source to iset."""
    tmp_set.add(source)
    used[source] += 1
    for target in graph[source]:
        used[target] += 1

def remove_iset(source):
    """Remove a source from iset."""
    tmp_set.remove(source)
    used[source] -= 1
    for target in graph[source]:
        used[target] -= 1

def graph_iset(k):
    """Try to add a node k to an iset."""
    global independent_set, tmp_set, node_list, N
    node = node_list[k]
    if used[node] > 0:   # mogę wstawiać tylko że nie należy
        if k < N-1:
            graph_iset(k+1)
        else:
            if len(tmp_set) > len(independent_set):
                independent_set = set(tmp_set)
    else:   # used[node]==0
        # Najpierw sprawdzam możliwość, że należy do iset.
        add_iset(node)
        if k < N-1:
            graph_iset(k+1)
        else:
            if len(tmp_set) > len(independent_set):
                independent_set = set(tmp_set)
        remove_iset(node)
        # Teraz sprawdzam możliwość, że nie należy do iset.
        if k < N-1:
            graph_iset(k+1)
        else:
            if len(tmp_set) > len(independent_set):
                independent_set = set(tmp_set)

# Uruchomienie poszukiwania największego zbioru niezależnego.
graph_iset(0)