Dado un grafo no dirigido definido por el número de vértices V y las aristas E[ ] , la tarea es encontrar el conjunto máximo de vértices independientes en un grafo no dirigido.
Conjunto independiente: Un conjunto independiente en un gráfico es un conjunto de vértices que no están conectados directamente entre sí.
Nota: Es un hecho que hay al menos una forma de atravesar desde cualquier vértice en el gráfico a otro, es decir, el gráfico tiene un componente conectado .
Ejemplos:
Entrada: V = 3, E = { (1, 2), (2, 3) }
Salida: {1, 3}
Explicación:
Como no hay aristas entre 1 y 3, y no podemos sumar 2 a esto ya que es un vecino de 1, este es el Conjunto Máximo Independiente.Entrada: V = 8,
E = { (1, 2), (1, 3), (2, 4), (5, 6), (6, 7), (4, 8) }
Salida: {2, 3, 5, 7, 8}
Enfoque:
Este problema es un problema NP-Difícil , que solo se puede resolver en tiempo exponencial (a partir de ahora).
Siga los pasos a continuación para resolver el problema:
- Itere a través de los vértices del gráfico y use el retroceso para verificar si un vértice se puede incluir en el conjunto independiente máximo o no.
- Surgen dos posibilidades para cada vértice, si puede estar incluido o no en el conjunto independiente máximo.
- Empezar inicialmente, considerando todos los vértices y aristas. Uno por uno, seleccione un vértice. Elimine ese vértice del gráfico, excluyéndolo del conjunto independiente máximo y recorra recursivamente el gráfico restante para encontrar el conjunto independiente máximo.
- De lo contrario, considere el vértice seleccionado en el conjunto independiente máximo y elimine todos sus vecinos. Proceda a encontrar el máximo conjunto independiente posible excluyendo a sus vecinos.
- Repita este proceso para todos los vértices e imprima el conjunto independiente máximo obtenido.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python Program to implement # the above approach # Recursive Function to find the # Maximal Independent Vertex Set def graphSets(graph): # Base Case - Given Graph # has no nodes if(len(graph) == 0): return [] # Base Case - Given Graph # has 1 node if(len(graph) == 1): return [list(graph.keys())[0]] # Select a vertex from the graph vCurrent = list(graph.keys())[0] # Case 1 - Proceed removing # the selected vertex # from the Maximal Set graph2 = dict(graph) # Delete current vertex # from the Graph del graph2[vCurrent] # Recursive call - Gets # Maximal Set, # assuming current Vertex # not selected res1 = graphSets(graph2) # Case 2 - Proceed considering # the selected vertex as part # of the Maximal Set # Loop through its neighbours for v in graph[vCurrent]: # Delete neighbor from # the current subgraph if(v in graph2): del graph2[v] # This result set contains VFirst, # and the result of recursive # call assuming neighbors of vFirst # are not selected res2 = [vCurrent] + graphSets(graph2) # Our final result is the one # which is bigger, return it if(len(res1) > len(res2)): return res1 return res2 # Driver Code V = 8 # Defines edges E = [ (1, 2), (1, 3), (2, 4), (5, 6), (6, 7), (4, 8)] graph = dict([]) # Constructs Graph as a dictionary # of the following format- # graph[VertexNumber V] # = list[Neighbors of Vertex V] for i in range(len(E)): v1, v2 = E[i] if(v1 not in graph): graph[v1] = [] if(v2 not in graph): graph[v2] = [] graph[v1].append(v2) graph[v2].append(v1) # Recursive call considering # all vertices in the maximum # independent set maximalIndependentSet = graphSets(graph) # Prints the Result for i in maximalIndependentSet: print(i, end =" ")
2 3 8 5 7
Complejidad temporal: O(2 N )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por joshi_arihant y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA