Los conjuntos independientes son conjuntos de vértices o aristas en los que el par de vértices o aristas cualesquiera no son adyacentes entre sí. Asumiendo que los conjuntos independientes significan conjuntos independientes de vértices, tenemos que encontrar un conjunto de tales vértices en el que dos pares cualesquiera de vértices no sean adyacentes entre sí. Usando la coloración de gráficos podemos resolver este problema. Modificaremos el método de coloreado del gráfico ya que en lugar de usar diferentes colores, solo usaremos dos colores, es decir, 0,1. Entonces supondremos que esos vértices que están etiquetados como 0 son parte del conjunto y otros no. Entonces, los vértices etiquetados con 0 no tienen ningún vértice adyacente etiquetado con 0.
Acercarse:
La idea básica sobre el funcionamiento de la llamada por referencias en Java y los conceptos del vector es imprescindible. Además, asumimos el índice etiquetado como el nombre del vértice y el valor en el vector en ese índice como el color de ese vértice (ya sea 0 o 1). La variable encontrada inicialmente se establece en falso, es decir, no se encuentra ningún conjunto del tamaño deseado. Usaremos la palabra eliminado y el color ‘0’ para cualquier vértice. Ambos indican lo mismo que el vértice en particular se puede quitar del gráfico y se puede incluir en el conjunto.
Procedimiento:
Se ilustra junto con la ayuda de los métodos que se utilizan en el programa y se explican secuencialmente para fines de comprensión de la siguiente manera:
- La entrada del programa es una array adyacente del gráfico y aquí se da el tamaño máximo de un conjunto. Primero, tenemos que hacer la lista de adyacencia de la array gráfica. Ahora vamos a ejecutar un ciclo para cada vértice, dando primero el color ‘0’ al i-ésimo vértice y luego encontrando todos los demás vértices posibles a los que se les puede dar el color ‘0’ (incluido en el conjunto).
- Así que estamos creando un vector llamado ‘color’ e inicializando el vector con el color de todos los índices (vértices) como ‘1’ y el i-ésimo vértice como ‘0’. Luego, revisaremos todos los vértices posibles a los que se les puede dar el color ‘0’ (incluido en el conjunto) usando un método Util() , que se describe a continuación.
- El método Util() llama a otros dos métodos llamados can_remove() y remove_all() . El objetivo principal de este método es eliminar todos los vértices que se pueden eliminar del vector de color si se elimina el ‘ésimo’ vértice (asignado ‘0’). Este método encuentra el índice del vértice que se puede eliminar usando los dos métodos anteriores. Luego asigna ‘0’ a ese vértice, y continúa haciendo esto hasta que no queda más vértice para eliminar. Devuelve el vector de color modificado.
- El método can_remove() comprueba si al vértice dado se le puede asignar ‘0’ sin ninguna dificultad. Compara cada vértice vecino para el vértice dado y verifica si hay algún vecino con ‘0’ o no. Si no hay ningún vértice en tal caso, a este vértice se le asigna un valor ‘0’. Devuelve un valor booleano que indica sí o no.
- El método remove_all() se usa para encontrar el vértice cuya eliminación dará numerosos vértices para eliminar cada vez. Este paso es principalmente un enfoque codicioso. Encuentra la cantidad de vértices que se pueden eliminar después de la eliminación de un vértice en particular y encuentra el valor máximo de todos esos números y devuelve el índice de ese vértice en particular cuya eliminación dará como resultado la eliminación del máximo de vértices. Luego, este vértice se elimina en el método Util().
- Así que hasta ahora habíamos entendido lo que están haciendo los métodos Util(), remove_all() y can_remove(). Básicamente, para cada ‘i-ésimo vector de color con ‘ésimo’ vértice siendo ‘0’, estos métodos intentan encontrar el número de vértices que se pueden eliminar del gráfico (asignados ‘0’). entonces, después de llamar a este método Util(), el vector de color se modifica y se le asigna ese valor al número de vértices que se pueden asignar ‘0’.
- Ahora que el vector de color se modifica, tenemos que contar el número de vértices que se asignan a ‘0’ (lo que significa los vértices que se pueden incluir en el conjunto). Si el recuento es mayor que el tamaño deseado, hemos encontrado la solución y la variable encontrada se establece en verdadero y la salida se realiza y los bucles se interrumpen; de lo contrario, continúa probando el siguiente vector de color con la eliminación del siguiente vértice. El recuento se realiza mediante el método Util3() .
- Aún así, nos estamos perdiendo el caso de borde que se muestra en la siguiente imagen. Aquí, en lugar de colorear el segundo vértice coloreado en el primer diagrama, colorearemos uno de sus vértices adyacentes como se muestra en la segunda figura. Al hacerlo, obtendremos muchos vértices en el conjunto. Por lo tanto, para cada vector de color, llamaremos al método Util2(). Este caso puede surgir solo cuando hay un cierto vértice que tiene un valor ‘1’ (sin color) y tiene solo un vértice adyacente coloreado como se muestra arriba.
- El método *Util2() básicamente verifica cada vértice que no se elimina (que tiene ‘1’), si ese vértice tiene solo un vértice adyacente coloreado (valor ‘1’). Si encuentra alguno de esos vértices, este método intercambiará el color entre los vértices y recuperará el método Util() para actualizar el vector de color. Esto se puede demostrar fácilmente que este método siempre aumentará el número del vértice con ‘0’ o el número permanecerá igual. Nunca disminuirá el número de vértices coloreados.
Entonces, este enfoque resulta más beneficioso para nuestro enfoque.
Nota: ¿Por qué siempre aumenta?
Solo hay intercambio de color entre dos vértices adyacentes. Por lo tanto, el recuento seguirá siendo el mismo hasta ahora. Pensando en el resto de la configuración, podemos decir que antes de intercambiar el vértice recién coloreado no tiene más de un vértice adyacente coloreado. Entonces, después del intercambio, tampoco hay vértices adyacentes que estén coloreados. Esto mantendrá la propiedad de los conjuntos independientes.
Implementación:
Hasta ahora, si tenemos alguna solución, la estableceremos como verdadero; de lo contrario, guardaremos la configuración del vector de color para su uso posterior. Todo esto se hace para cada vértice ‘ith’ en el bucle y el vector de color modificado se almacena en el vector de vectores denominado set_found en el programa.
Si no se encuentra el tamaño deseado hasta ahora, probaremos nuestro último caso en el que realizaremos la intersección por pares de todos los conjuntos de configuraciones generados.
En este, repetiremos el mismo procedimiento comenzando nuevamente con el vector de color y manteniendo las configuraciones generadas. La única diferencia es que no comenzaremos asignando ‘0’ al i-ésimo vértice. En lugar de eso, comprobaremos pares de configuraciones (en el set_found) para aquellos vértices que están etiquetados con ‘0’ y son comunes a ambos conjuntos. Se etiquetarán como ‘0’ en el vector de color y, lo mejor, el procedimiento anterior será el mismo, para verificar el tamaño máximo del conjunto posible y el caso anterior.
Ejemplo
Java
// Java Program to Find Independent Sets in a Graph
// by Graph Coloring
// Importing input output classes
import java.io.*;
// Importing utility classes from java.util package
import java.util.*;
// Class 1
// Helper class
class GFGUTIL {
// Method 1
// Utility function to label maximum vertices with
// 0,that can be included in the set
public static void
Util(Vector<Vector<Integer> > adjacency_list,
Vector<Integer> color)
{
int a = 0;
// Condition check
while (a != -1) {
a = remove_all(adjacency_list, color);
if (a != -1)
color.set(a, 0);
}
}
// Method 2
// This method that tries whether it is possible to
// remove any adjacent vertex of any removed vertex
public static void
Util2(Vector<Vector<Integer> > adjacency_list,
Vector<Integer> color, int j)
{
int cnt = 0;
Vector<Integer> tmp_color = new Vector<Integer>();
for (int g = 0; g < color.size(); ++g)
tmp_color.add(color.get(g));
for (int i = 0; i < color.size(); ++i) {
if (tmp_color.get(i) == 1) {
int sum = 0;
int idx = -1;
for (int g = 0; g < adjacency_list.get(i).size(); ++g)
if (tmp_color.get(adjacency_list.get(i).get(g)) == 0) {
idx = g;
sum++;
}
if (sum == 1 && color.get(adjacency_list.get(i).get(idx))== 0) {
tmp_color.set(adjacency_list.get(i).get(idx), 1);
tmp_color.set(i, 0);
Util(adjacency_list, tmp_color);
++cnt;
}
if (cnt > j)
break;
}
}
for (int g = 0; g < color.size(); ++g)
color.set(g, tmp_color.get(g));
}
// Method 3
// Returning the number of vertices
// that can't be included in the set
public static int Util3(Vector<Integer> color)
{
int cnt = 0;
for (int i = 0; i < color.size(); i++)
if (color.get(i) == 1)
++cnt;
return cnt;
}
// Method 4
// Returning the index of the vertex
public static int
remove_all(Vector<Vector<Integer> > adjacency_list, Vector<Integer> color)
{
int a = -1, max = -1;
for (int i = 0; i < color.size(); ++i) {
if (color.get(i) == 1 && can_remove(adjacency_list.get(i), color) == 1) {
Vector<Integer> tmp_color = new Vector<Integer>();
for (int j = 0; j < color.size(); ++j)
tmp_color.add(color.get(j));
tmp_color.set(i, 0);
int sum = 0;
for (int j = 0; j < tmp_color.size(); ++j)
if (tmp_color.get(j) == 1 && can_remove(adjacency_list.get(j), tmp_color) == 1)
++sum;
if (sum > max) {
max = sum;
a = i;
}
}
}
// Index of the vertex
return a;
}
// Method 5
// To check whether a vertex can be removed or not
public static int can_remove(Vector<Integer> adj_list, Vector<Integer> color)
{
int check = 1;
for (int i = 0; i < adj_list.size(); ++i)
if (color.get(adj_list.get(i)) == 0)
check = 0;
return check;
}
}
// Class 2
// Main class
public class GFG {
// Main driver method
public static void main(String[] args) throws Exception
{
// inputting the graph and forming it's adjacency
// list.
// Display message for better readability
System.out.println("The number of vertices in the graph is taken as 4");
// Custom input is taken here
int n = 4;
// Creating a vector object for adjacency matrix.
Vector<Vector<Integer> > adjacency_matrix = new Vector<Vector<Integer> >(n, (n));
// Input matrix is
// 0111
// 1011
// 1101
// 1110
// Nested for loops for iterations
for (int i = 0; i < n; ++i) {
Vector<Integer> adj = new Vector<Integer>(n);
for (int j = 0; j < n; ++j)
if (i == j)
adj.add(0);
else
adj.add(1);
adjacency_matrix.add(adj);
}
// Creating a vector object for adjacency list
Vector<Vector<Integer> > adjacency_list
= new Vector<Vector<Integer> >();
// Nested for loops for iterations
for (int i = 0; i < n; ++i) {
Vector<Integer> adj_list = new Vector<Integer>();
for (int j = 0; j < n; ++j) {
if (adjacency_matrix.get(i).get(j) == 1)
adj_list.add(j);
}
adjacency_list.add(adj_list);
}
// Display message only for
// taking the minimum size of the set required.
System.out.println("The minimum size of the set required is taken as 2");
// Declaring and initializing variable with
// least size of the set required
int x = 2;
// Complement of the size
int y = n - x;
int found = 0;
int size = 0;
int min = n + 1;
// Creating a set found vector to
// store all the possible set
Vector<Vector<Integer> > set_found = new Vector<Vector<Integer> >();
// Display message
System.out.println("Searching for the set");
for (int i = 0; i < n; ++i) {
// If set is found
if (found == 1)
// Hault the further execution of Program
break;
// Cover vector to have the state of all the
// vertices initially
Vector<Integer> color = new Vector<Integer>(n);
for (int j = 0; j < n; ++j)
color.add(1);
// Starting by putting the ith node in set
color.set(i, 0);
// then finding all the nodes to be pushed
GFGUTIL.Util(adjacency_list, color);
// Finding the number of those which cannot be
// pushed in set
size = GFGUTIL.Util3(color);
if (size < min)
min = size;
// If the number of elements in set are more or
// equal
if (size <= y) {
// Print and display the size
System.out.println("Independent set of size " + (n - size) + "found");
for (int j = 0; j < n; ++j)
if (color.get(j) == 0)
System.out.print(j + 1 + " ");
System.out.println();
set_found.add(color);
// Set flag to 1
found = 1;
// Hault the further execution of Program
break;
}
// If sufficient nodes are not found then
// we call util2 function
for (int j = 0; j < x; ++j)
GFGUTIL.Util2(adjacency_list, color, j);
size = GFGUTIL.Util3(color);
if (size < min)
min = size;
System.out.println("Independent set of size " + (n - size) + "found");
for (int j = 0; j < n; ++j)
if (color.get(j) == 0)
System.out.print(j + 1 + " ");
System.out.println();
set_found.add(color);
if (size <= y) {
found = 1;
break;
}
}
int r = set_found.size();
// Now searching pairwise and
// repeating same procedure as above discussed
for (int a = 0; a < r; ++a) {
if (found == 1)
break;
for (int b = a + 1; b < r; ++b) {
if (found == 1)
break;
Vector<Integer> color = new Vector<Integer>(n);
for (int j = 0; j < n; ++j)
color.add(1);
for (int c = 0; c < n; ++c)
if (set_found.get(a).get(c) == 0
&& set_found.get(b).get(c) == 0)
color.set(c, 0);
GFGUTIL.Util(adjacency_list, color);
size = GFGUTIL.Util3(color);
if (size < min)
min = size;
if (size <= y) {
System.out.println("Independent set of size" + (n - size));
for (int j = 0; j < n; ++j)
if (color.get(j) == 0)
System.out.print(j + 1 + " ");
System.out.println();
found = 1;
break;
}
for (int j = 0; j < y; ++j)
GFGUTIL.Util2(adjacency_list, color, j);
size = GFGUTIL.Util3(color);
if (size < min)
min = size;
System.out.println("Independent set of size " + (n - size) + "found");
for (int j = 0; j < n; ++j)
if (color.get(j) == 0)
System.out.print(j + 1 + " ");
System.out.println();
if (size <= y) {
found = 1;
break;
}
}
}
// If found
if (found == 1)
// Display command
System.out.println("Found the set of given least possible size");
else
// Display command
System.out.println("Couldn't find the set of least size given");
}
}
The number of vertices in the graph is taken as 4 The minimum size of the set required is taken as 2 Searching for the set Independent set of size 1found 1 Independent set of size 1found 2 Independent set of size 1found 2 Independent set of size 1found 2 Independent set of size 1found 1 Independent set of size 1found 1 Independent set of size 1found 1 Independent set of size 1found 2 Independent set of size 1found 2 Independent set of size 1found 2 Couldn't find the set of least size given
Publicación traducida automáticamente
Artículo escrito por harshkumarchoudhary144 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA