Dado un grafo completo no dirigido con N Nodes o vértices. Los bordes del gráfico están coloreados, encuentre el subconjunto más grande de vértices con bordes de 2 o más colores. Se nos da un gráfico como array de adyacencia C[][] donde C[i][j] es el color del borde desde el vértice i hasta el vértice j. Dado que el gráfico no está dirigido, los valores C[i][j] de C[j][i] son los mismos.
Definimos C[i][i] como cero, aunque no existe tal borde presente. es decir, el gráfico no contiene bucles automáticos.
Ejemplos:
Ejemplo 1:
Entrada: C[][]= {{0, 1, 2},
{1, 0, 3},
{2, 3, 0}}
Salida : 3
Ejemplo 2:
Entrada: C[][]= {{0, 1, 1},
{1, 0, 3},
{1, 3, 0}}
Salida : 0
Dado que el gráfico está completo, cada borde puede ser uno de n*(n-1)/2 +1 colores diferentes. Estos colores están etiquetados de 0 a n*(n-1)/2, inclusive. Pero no es necesario utilizar todos estos colores n*(n-1)/2 +1. es decir, es posible que dos bordes diferentes puedan tener el mismo color.
Llamemos a un vértice «malo» si todos sus vecinos son del mismo color. Obviamente, no podemos tener ningún vértice tan malo en nuestro subconjunto, así que elimine ese vértice malo del gráfico. Esto podría introducir más vértices malos, pero podemos seguir repitiendo este proceso hasta que encontremos un subconjunto libre de vértices malos. Entonces, por fin, deberíamos permanecer en un gráfico que no tiene ningún vértice malo, lo que significa que cada vértice de nuestro subconjunto tiene al menos dos bordes de color diferente con otros vértices adyacentes.
Ejemplo:
Entrada:
let C[6][6]:
{{0, 9, 2, 4, 7, 8},
{9, 0, 9, 9, 7, 9},
{2, 9, 0, 3 , 7, 6},
{4, 9, 3, 0, 7, 1},
{7, 7, 7, 7, 0, 7},
{8, 9, 6, 1, 7, 0}};
Paso I: En primer lugar, podemos ver que la fila 5 (Node ‘e’) contiene solo 7, lo que significa que el Node ‘e’ está conectado a través de bordes que tienen el código de color 7, por lo que no tiene más de un borde de color, por lo que debemos eliminar 5 del subconjunto. Ahora, nuestro gráfico contendrá solo 5 vértices y son como:
C[5][5]:
{{0, 9, 2, 4, 8},
{9, 0, 9, 9, 9},
{2, 9 , 0, 3, 6},
{4, 9, 3, 0, 1},
{8, 9, 6, 1, 0}};
Paso II: Además, podemos ver que la fila 2 (Node ‘b’) tampoco contiene más de 1 borde de color, por lo que también debemos eliminar la fila 2 y la columna 2. Lo que da como resultado nuestro nuevo gráfico como:
C[4][4]:
{{0, 2, 4, 8},
{2, 0, 3, 6},
{4, 3, 0, 1},
{8, 6, 1, 0}};
Paso III: Ahora, podemos ver que cada vértice tiene más de 1 borde de color diferente. Entonces, el número total de vértices en el subconjunto es 4.
Implementación:
C++
// C++ program to find size of subset of graph vertex
// such that each vertex has more than 1 color edges
#include <bits/stdc++.h>
using namespace std;
// Number of vertices
const int N = 6;
// function to calculate max subset size
int subsetGraph(int C[][N])
{
// set for number of vertices
set<int> vertices;
for (int i = 0; i < N; ++i)
vertices.insert(i);
// loop for deletion of vertex from set
while (!vertices.empty())
{
// if subset has only 1 vertex return 0
if (vertices.size() == 1)
return 1;
// for each vertex iterate and keep removing
// a vertex while we find a vertex with all
// edges of same color.
bool someone_removed = false;
for (int x : vertices)
{
// note down different color values
// for each vertex
set<int> values;
for (int y : vertices)
if (y != x)
values.insert(C[x][y]);
// if only one color is found
// erase that vertex (bad vertex)
if (values.size() == 1)
{
vertices.erase(x);
someone_removed = true;
break;
}
}
// If no vertex was removed in the
// above loop.
if (!someone_removed)
break;
}
return (vertices.size());
}
// Driver program
int main()
{
int C[][N] = {{0, 9, 2, 4, 7, 8},
{9, 0, 9, 9, 7, 9},
{2, 9, 0, 3, 7, 6},
{4, 9, 3, 0, 7, 1},
{7, 7, 7, 7, 0, 7},
{8, 9, 6, 1, 7, 0}
};
cout << subsetGraph(C);
return 0;
}
Java
// Java program to find size of
// subset of graph vertex such that
// each vertex has more than 1 color edges
import java.util.*;
class GFG
{
// Number of vertices
static int N = 6;
// function to calculate max subset size
static int subsetGraph(int C[][])
{
// set for number of vertices
HashSet<Integer> vertices = new HashSet<>();
for (int i = 0; i < N; ++i)
{
vertices.add(i);
}
// loop for deletion of vertex from set
while (!vertices.isEmpty())
{
// if subset has only 1 vertex return 0
if (vertices.size() == 1)
{
return 1;
}
// for each vertex iterate and keep removing
// a vertex while we find a vertex with all
// edges of same color.
boolean someone_removed = false;
for (int x : vertices)
{
// note down different color values
// for each vertex
HashSet<Integer> values = new HashSet<>();
for (int y : vertices)
{
if (y != x)
{
values.add(C[x][y]);
}
}
// if only one color is found
// erase that vertex (bad vertex)
if (values.size() == 1)
{
vertices.remove(x);
someone_removed = true;
break;
}
}
// If no vertex was removed in the
// above loop.
if (!someone_removed)
{
break;
}
}
return (vertices.size());
}
// Driver code
public static void main(String[] args)
{
int C[][] = {{0, 9, 2, 4, 7, 8},
{9, 0, 9, 9, 7, 9},
{2, 9, 0, 3, 7, 6},
{4, 9, 3, 0, 7, 1},
{7, 7, 7, 7, 0, 7},
{8, 9, 6, 1, 7, 0}
};
System.out.println(subsetGraph(C));
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 program to find size of subset # of graph vertex such that each vertex # has more than 1 color edges # function to calculate max subset size def subsetGraph(C): global N # set for number of vertices vertices = set() for i in range(N): vertices.add(i) # loop for deletion of vertex from set while (len(vertices) != 0): # if subset has only 1 vertex return 0 if (len(vertices) == 1): return 1 # for each vertex iterate and keep removing # a vertex while we find a vertex with all # edges of same color. someone_removed = False for x in vertices: # note down different color values # for each vertex values = set() for y in vertices: if (y != x): values.add(C[x][y]) # if only one color is found # erase that vertex (bad vertex) if (len(values) == 1): vertices.remove(x) someone_removed = True break # If no vertex was removed in the # above loop. if (not someone_removed): break return len(vertices) # Driver Code # Number of vertices N = 6 C = [[0, 9, 2, 4, 7, 8], [9, 0, 9, 9, 7, 9], [2, 9, 0, 3, 7, 6], [4, 9, 3, 0, 7, 1], [7, 7, 7, 7, 0, 7], [8, 9, 6, 1, 7, 0]] print(subsetGraph(C)) # This code is contributed by PranchalK
C#
// C# program to find size of
// subset of graph vertex such that
// each vertex has more than 1 color edges
using System;
using System.Collections.Generic;
class GFG
{
// Number of vertices
static int N = 6;
// function to calculate max subset size
static int subsetGraph(int [,]C)
{
// set for number of vertices
HashSet<int> vertices = new HashSet<int>();
for (int i = 0; i < N; ++i)
{
vertices.Add(i);
}
// loop for deletion of vertex from set
while (vertices.Count != 0)
{
// if subset has only 1 vertex return 0
if (vertices.Count == 1)
{
return 1;
}
// for each vertex iterate and keep removing
// a vertex while we find a vertex with all
// edges of same color.
Boolean someone_removed = false;
foreach (int x in vertices)
{
// note down different color values
// for each vertex
HashSet<int> values = new HashSet<int>();
foreach (int y in vertices)
{
if (y != x)
{
values.Add(C[x, y]);
}
}
// if only one color is found
// erase that vertex (bad vertex)
if (values.Count == 1)
{
vertices.Remove(x);
someone_removed = true;
break;
}
}
// If no vertex was removed in the
// above loop.
if (!someone_removed)
{
break;
}
}
return (vertices.Count);
}
// Driver code
public static void Main(String[] args)
{
int [,]C = {{0, 9, 2, 4, 7, 8},
{9, 0, 9, 9, 7, 9},
{2, 9, 0, 3, 7, 6},
{4, 9, 3, 0, 7, 1},
{7, 7, 7, 7, 0, 7},
{8, 9, 6, 1, 7, 0}};
Console.WriteLine(subsetGraph(C));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find size of
// subset of graph vertex such that
// each vertex has more than 1 color edges
// Number of vertices
let N = 6;
// Function to calculate max subset size
function subsetGraph(C)
{
// Set for number of vertices
let vertices = new Set();
for(let i = 0; i < N; ++i)
{
vertices.add(i);
}
// Loop for deletion of vertex from set
while (vertices.size != 0)
{
// If subset has only 1 vertex return 0
if (vertices.size == 1)
{
return 1;
}
// For each vertex iterate and keep removing
// a vertex while we find a vertex with all
// edges of same color.
let someone_removed = false;
for(let x of vertices.values())
{
// Note down different color values
// for each vertex
let values = new Set();
for(let y of vertices.values())
{
if (y != x)
{
values.add(C[x][y]);
}
}
// If only one color is found
// erase that vertex (bad vertex)
if (values.size == 1)
{
vertices.delete(x);
someone_removed = true;
break;
}
}
// If no vertex was removed in the
// above loop.
if (!someone_removed)
{
break;
}
}
return (vertices.size);
}
// Driver code
let C = [ [ 0, 9, 2, 4, 7, 8 ],
[ 9, 0, 9, 9, 7, 9 ],
[ 2, 9, 0, 3, 7, 6 ],
[ 4, 9, 3, 0, 7, 1 ],
[ 7, 7, 7, 7, 0, 7 ],
[ 8, 9, 6, 1, 7, 0 ] ];
document.write(subsetGraph(C));
// This code is contributed by rag2127
</script>
4
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA