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 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.
La idea básica sobre el funcionamiento de la llamada por referencias en java y conceptos de 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.
Acercarse:
- La entrada del programa es una array adyacente del gráfico y aquí se da el tamaño máximo del 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.
- Método Util(): este método 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á una gran cantidad de 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 hemos 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 el ‘é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 la cantidad de vértices que se pueden asignar ‘0’ recibe ese valor.
- 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 intentando el siguiente vector de color con la eliminación del siguiente vértice. El conteo se realiza mediante el método Util3().
Pero nos estamos olvidando de un caso como 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 fig. 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 el 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 de un 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.
¿Por qué siempre aumentar?
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.
- 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 ‘ésimo’ vértice 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, buscaremos pares de configuración (en el conjunto_encontrado) para aquellos vértices que están etiquetados con ‘0’ y son comunes a ambos conjuntos. Serán etiquetados como ‘0’ en el vector de color y para el resto de la parte el procedimiento anterior será el mismo, para verificar el tamaño máximo de conjunto posible y el caso anterior.
Implementación:
Java
// Java Program to Find Independent Sets
// in a Graph using Graph Coloring
import java.io.*;
import java.util.*;
// save file with the name "GFG2.java"
public class GFG2 {
// main class
public static void main(String[] args) throws Exception
{
// inputting the graph and forming it's adjacency
// list.
System.out.println("The number of vertices in the graph is taken as 4");
int n = 4;
Vector<Vector<Integer> > adjacency_matrix
= new Vector<Vector<Integer> >(n, (n));
/* the input matrix is
0111
1011
1101
1110
*/
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);
}
Vector<Vector<Integer> > adjacency_list = new Vector<Vector<Integer> >();
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);
}
// taking the minimum size of the set required.
System.out.println("The minimum size of the set required is taken as 2");
// the 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;
// making a set_found vector to store all the
// possible sets .
Vector<Vector<Integer> > set_found
= new Vector<Vector<Integer> >();
System.out.println("Searching for the set");
for (int i = 0; i < n; ++i) {
// if set is found
if (found == 1)
break;
// a 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 in
// the set by calling function
Util(adjacency_list, color);
// finding the number of those which cannot be
// pushed in set
size = Util3(color);
if (size < min)
min = size;
// if the number of elements in set are more or
// equal to the amount required.
if (size <= y) {
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);
found = 1;
break;
}
// not sufficient nodes found
// calling util2 function
// main aim of calling this function 'x' times
// is that for any undirected graph the maximum
// number of edges with x nodes is x(x+1)/2; so
// we are trying for each possible edge .
for (int j = 0; j < x; ++j)
Util2(adjacency_list, color, j);
// repeating same procedure as discussed above
size = 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();
// searching pairwise.
// repeating same procedure as above
// this time taking those set which have common
// vertices in them and again trying for uncommon
// ones.
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);
Util(adjacency_list, color);
size = 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)
Util2(adjacency_list, color, j);
size = 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)
System.out.println(
"Found the set of given least possible size");
else
System.out.println(
"Couldn't find the set of least size given");
}
// utility function to label maximum vertices with
// 0,that can be included in the set. It takes the
// maximum number of vertices which can be removed each
// time.
public static void Util(Vector<Vector<Integer> > adjacency_list,
Vector<Integer> color)
{
int a = 0;
while (a != -1) {
a = remove_all(adjacency_list, color);
if (a != -1)
color.set(a, 0);
}
}
// This method tries whether it is possible to
// remove any adjacent vertex of any removed vertex if
// yes then it will remove that and call Util again and
// modify the set.
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));
}
// 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;
}
// returns the index of the vertex whose removal will
// give more vertex to be removed. This is basically a
// greedy approach to get the maximum possible set size.
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;
}
}
}
return a;
}
// checking that 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;
}
}
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