Dado un grafo no dirigido con vértices V y aristas E , la tarea es imprimir todos los conjuntos independientes y también encontrar los conjuntos independientes máximos .
Conjunto independiente es un conjunto de vértices tales que dos vértices cualesquiera del conjunto no tienen una arista directa entre ellos.
El conjunto independiente máximo es un conjunto independiente que tiene el mayor número de vértices.
Nota: Puede haber más de un conjunto independiente y máximo independiente para un gráfico dado.
Ejemplos:
Entrada:
V = 3, E = 0
Gráfico:
Gráfico para el ejemplo 1
Salida:
{ }{ 1 }{ 1 2 }{ 1 2 3 }{ 1 3 }{ 2 }{ 2 3 }{ 3 }
{ 1 2 3 }
Explicación:
La primera línea representa todos los conjuntos independientes posibles para el gráfico dado . La segunda línea tiene los conjuntos independientes máximos posibles para el gráfico dado.
Entrada:
V = 4, E = 4
Gráfico:
Gráfico para el ejemplo 2
Salida:
{ }{ 1 }{ 1 3 }{ 2 }{ 2 4 }{ 3 }{ 4 }
{ 1 3 }{ 2 4 }
Enfoque:
La idea es utilizar Backtracking para resolver el problema. En cada paso, debemos verificar si el Node actual tiene algún borde directo con alguno de los Nodes que ya están presentes en nuestro conjunto independiente. Si no, podemos agregarlo a nuestro conjunto independiente y repetir recursivamente el mismo proceso para todos los Nodes.
Ilustración:
Árbol de recursión para el primer ejemplo:
Árbol de retroceso para todos los conjuntos posibles
En el árbol de retroceso anterior, elegiremos solo aquellos conjuntos que se producen después de agregar un Node seguro para mantener el conjunto como un conjunto independiente.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ Program to print the
// independent sets and
// maximal independent sets
// of the given graph
#include <bits/stdc++.h>
using namespace std;
// To store all the independent
// sets of the graph
set<set<int> > independentSets;
// To store all maximal independent
// sets in the graph
set<set<int> > maximalIndependentSets;
map<pair<int, int>, int> edges;
vector<int> vertices;
// Function to print all independent sets
void printAllIndependentSets()
{
for (auto iter : independentSets) {
cout << "{ ";
for (auto iter2 : iter) {
cout << iter2 << " ";
}
cout << "}";
}
cout << endl;
}
// Function to extract all
// maximal independent sets
void printMaximalIndependentSets()
{
int maxCount = 0;
int localCount = 0;
for (auto iter : independentSets) {
localCount = 0;
for (auto iter2 : iter) {
localCount++;
}
if (localCount > maxCount)
maxCount = localCount;
}
for (auto iter : independentSets) {
localCount = 0;
set<int> tempMaximalSet;
for (auto iter2 : iter) {
localCount++;
tempMaximalSet.insert(iter2);
}
if (localCount == maxCount)
maximalIndependentSets
.insert(tempMaximalSet);
}
for (auto iter : maximalIndependentSets) {
cout << "{ ";
for (auto iter2 : iter) {
cout << iter2 << " ";
}
cout << "}";
}
cout << endl;
}
// Function to check if a
// node is safe node.
bool isSafeForIndependentSet(
int vertex,
set<int> tempSolutionSet)
{
for (auto iter : tempSolutionSet) {
if (edges[make_pair(iter, vertex)]) {
return false;
}
}
return true;
}
// Recursive function to find
// all independent sets
void findAllIndependentSets(
int currV,
int setSize,
set<int> tempSolutionSet)
{
for (int i = currV; i <= setSize; i++) {
if (isSafeForIndependentSet(
vertices[i - 1],
tempSolutionSet)) {
tempSolutionSet
.insert(vertices[i - 1]);
findAllIndependentSets(
i + 1,
setSize,
tempSolutionSet);
tempSolutionSet
.erase(vertices[i - 1]);
}
}
independentSets
.insert(tempSolutionSet);
}
// Driver Program
int main()
{
int V = 3, E = 0;
for (int i = 1; i <= V; i++)
vertices.push_back(i);
vector<pair<int, int> > inputEdges;
pair<int, int> edge;
int x, y;
for (int i = 0; i < E; i++) {
cout<<i<<endl;
edge.first = inputEdges[i].first;
edge.second = inputEdges[i].second;
edges[edge] = 1;
int t = edge.first;
edge.first = edge.second;
edge.second = t;
edges[edge] = 1;
}
set<int> tempSolutionSet;
findAllIndependentSets(1,
V,
tempSolutionSet);
printAllIndependentSets();
printMaximalIndependentSets();
return 0;
}
Python3
# Python3 Program to print the
# independent sets and
# maximal independent sets
# of the given graph
# To store all the independent
# sets of the graph
independentSets=set()
# To store all maximal independent
# sets in the graph
maximalIndependentSets=set()
edges=dict()
vertices=[]
# Function to print all independent sets
def printAllIndependentSets():
for itr in independentSets:
print("{",end=" ")
for itr2 in itr:
print(itr2,end= " ")
print("}",end='')
print()
# Function to extract all
# maximal independent sets
def printMaximalIndependentSets():
maxCount = 0;localCount = 0
for itr in independentSets:
localCount = 0
for itr2 in itr:
localCount+=1
if (localCount > maxCount):
maxCount = localCount
for itr in independentSets:
localCount = 0
tempMaximalSet=set()
for itr2 in itr:
localCount+=1
tempMaximalSet.add(itr2)
if (localCount == maxCount):
maximalIndependentSets.add(frozenset(tempMaximalSet))
for itr in maximalIndependentSets :
print("{",end=" ")
for itr2 in itr:
print(itr2,end=" ")
print("}",end="")
print()
# Function to check if a
# node is safe node.
def isSafeForIndependentSet(vertex, tempSolutionSet):
for itr in tempSolutionSet:
if (itr, vertex) in edges:
return False
return True
# Recursive function to find
# all independent sets
def findAllIndependentSets(currV, setSize, tempSolutionSet):
for i in range(currV,setSize+1):
if (isSafeForIndependentSet(vertices[i - 1], tempSolutionSet)) :
tempSolutionSet.add(vertices[i - 1])
findAllIndependentSets(i + 1, setSize, tempSolutionSet)
tempSolutionSet.remove(vertices[i - 1])
independentSets.add(frozenset(tempSolutionSet))
# Driver Program
if __name__ == '__main__':
V = 3; E = 0
for i in range(1,V+1):
vertices.append(i)
inputEdges=[]
for i in range(E):
edges[inputEdges[i]]=True
edges[(inputEdges[i][1],inputEdges[i][0])]=True
tempSolutionSet=set()
findAllIndependentSets(1, V, tempSolutionSet)
printAllIndependentSets()
printMaximalIndependentSets()
{ }{ 1 }{ 1 2 }{ 1 2 3 }{ 1 3 }{ 2 }{ 2 3 }{ 3 }
{ 1 2 3 }
Complejidad del tiempo: O(2 ^ N)
Espacio auxiliar: O(2 ^ N)