Dado un gráfico G y un número entero K, los núcleos K del gráfico son componentes conectados que quedan después de que se hayan eliminado todos los vértices de grado menor que k (Fuente wiki )
Ejemplo:
Input : Adjacency list representation of graph shown
on left side of below diagram
Output: K-Cores :
[2] -> 3 -> 4 -> 6
[3] -> 2 -> 4 -> 6 -> 7
[4] -> 2 -> 3 -> 6 -> 7
[6] -> 2 -> 3 -> 4 -> 7
[7] -> 3 -> 4 -> 6
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
El algoritmo estándar para encontrar un gráfico de k-núcleo consiste en eliminar todos los vértices que tienen un grado inferior a ‘K’ del gráfico de entrada. Debemos tener cuidado de que eliminar un vértice reduzca el grado de todos los vértices adyacentes, por lo que el grado de los vértices adyacentes también puede caer por debajo de ‘K’. Y por lo tanto, es posible que también tengamos que eliminar esos vértices. Este proceso puede o no continuar hasta que no queden vértices en el gráfico.
Para implementar el algoritmo anterior, hacemos un DFS modificado en el gráfico de entrada y eliminamos todos los vértices que tienen un grado inferior a ‘K’, luego actualizamos los grados de todos los vértices adyacentes, y si su grado cae por debajo de ‘K’ también los eliminaremos .
A continuación se muestra la implementación de la idea anterior. Tenga en cuenta que el siguiente programa solo imprime vértices de k núcleos, pero se puede ampliar fácilmente para imprimir los k núcleos completos, ya que hemos modificado la lista de adyacencia.
C++14
// C++ program to find K-Cores of a graph
#include<bits/stdc++.h>
using namespace std;
// This class represents a undirected graph using adjacency
// list representation
class Graph
{
int V; // No. of vertices
// Pointer to an array containing adjacency lists
list<int> *adj;
public:
Graph(int V); // Constructor
// function to add an edge to graph
void addEdge(int u, int v);
// A recursive function to print DFS starting from v
bool DFSUtil(int, vector<bool> &, vector<int> &, int k);
// prints k-Cores of given graph
void printKCores(int k);
};
// A recursive function to print DFS starting from v.
// It returns true if degree of v after processing is less
// than k else false
// It also updates degree of adjacent if degree of v
// is less than k. And if degree of a processed adjacent
// becomes less than k, then it reduces of degree of v also,
bool Graph::DFSUtil(int v, vector<bool> &visited,
vector<int> &vDegree, int k)
{
// Mark the current node as visited and print it
visited[v] = true;
// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
{
// degree of v is less than k, then degree of adjacent
// must be reduced
if (vDegree[v] < k)
vDegree[*i]--;
// If adjacent is not processed, process it
if (!visited[*i])
{
// If degree of adjacent after processing becomes
// less than k, then reduce degree of v also.
DFSUtil(*i, visited, vDegree, k);
}
}
// Return true if degree of v is less than k
return (vDegree[v] < k);
}
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}
// Prints k cores of an undirected graph
void Graph::printKCores(int k)
{
// INITIALIZATION
// Mark all the vertices as not visited and not
// processed.
vector<bool> visited(V, false);
vector<bool> processed(V, false);
int mindeg = INT_MAX;
int startvertex;
// Store degrees of all vertices
vector<int> vDegree(V);
for (int i=0; i<V; i++)
{
vDegree[i] = adj[i].size();
if (vDegree[i] < mindeg)
{
mindeg = vDegree[i];
startvertex=i;
}
}
DFSUtil(startvertex, visited, vDegree, k);
// If Graph is disconnected.
for (int i=0; i<V; i++)
if (visited[i] == false)
DFSUtil(i, visited, vDegree, k);
// Considering Edge Case (Example 3 in main() function)
for (int v=0; v<V; v++){
if (vDegree[v] >= k){
int cnt = 0;
list<int>::iterator itr;
for (itr = adj[v].begin(); itr != adj[v].end(); ++itr)
if (vDegree[*itr] >= k)
cnt++;
if(cnt < k)
vDegree[v] = cnt;
}
}
// PRINTING K CORES
cout << "K-Cores : \n";
for (int v=0; v<V; v++)
{
// Only considering those vertices which have degree
// >= K after DFS
if (vDegree[v] >= k)
{
cout << "\n[" << v << "]";
// Traverse adjacency list of v and print only
// those adjacent which have vDegree >= k after
// DFS.
list<int>::iterator itr;
for (itr = adj[v].begin(); itr != adj[v].end(); ++itr)
if (vDegree[*itr] >= k)
cout << " -> " << *itr;
}
}
}
// Driver program to test methods of graph class
int main()
{
// Create a graph given in the above diagram
int k = 3;
Graph g1(9);
g1.addEdge(0, 1);
g1.addEdge(0, 2);
g1.addEdge(1, 2);
g1.addEdge(1, 5);
g1.addEdge(2, 3);
g1.addEdge(2, 4);
g1.addEdge(2, 5);
g1.addEdge(2, 6);
g1.addEdge(3, 4);
g1.addEdge(3, 6);
g1.addEdge(3, 7);
g1.addEdge(4, 6);
g1.addEdge(4, 7);
g1.addEdge(5, 6);
g1.addEdge(5, 8);
g1.addEdge(6, 7);
g1.addEdge(6, 8);
g1.printKCores(k);
cout << endl << endl;
Graph g2(13);
g2.addEdge(0, 1);
g2.addEdge(0, 2);
g2.addEdge(0, 3);
g2.addEdge(1, 4);
g2.addEdge(1, 5);
g2.addEdge(1, 6);
g2.addEdge(2, 7);
g2.addEdge(2, 8);
g2.addEdge(2, 9);
g2.addEdge(3, 10);
g2.addEdge(3, 11);
g2.addEdge(3, 12);
g2.printKCores(k);
Graph gr(9);
gr.addEdge(0, 1);
gr.addEdge(0, 2);
gr.addEdge(1, 2);
gr.addEdge(2, 5);
gr.addEdge(2, 4);
gr.addEdge(2, 3);
gr.addEdge(2, 6);
gr.addEdge(3, 4);
gr.addEdge(3, 6);
gr.addEdge(3, 7);
gr.addEdge(4, 6);
gr.addEdge(5, 6);
gr.addEdge(5, 7);
gr.addEdge(5, 8);
gr.addEdge(8, 7);
gr.printKCores(k);
return 0;
}
Java
// Java program to find K-Cores of a graph
import java.util.*;
class GFG
{
// This class represents a undirected graph using adjacency
// list representation
static class Graph
{
int V; // No. of vertices
// Pointer to an array containing adjacency lists
Vector<Integer>[] adj;
@SuppressWarnings("unchecked")
Graph(int V)
{
this.V = V;
this.adj = new Vector[V];
for (int i = 0; i < V; i++)
adj[i] = new Vector<>();
}
// function to add an edge to graph
void addEdge(int u, int v)
{
this.adj[u].add(v);
this.adj[v].add(u);
}
// A recursive function to print DFS starting from v.
// It returns true if degree of v after processing is less
// than k else false
// It also updates degree of adjacent if degree of v
// is less than k. And if degree of a processed adjacent
// becomes less than k, then it reduces of degree of v also,
boolean DFSUtil(int v, boolean[] visited, int[] vDegree, int k)
{
// Mark the current node as visited and print it
visited[v] = true;
// Recur for all the vertices adjacent to this vertex
for (int i : adj[v])
{
// degree of v is less than k, then degree of adjacent
// must be reduced
if (vDegree[v] < k)
vDegree[i]--;
// If adjacent is not processed, process it
if (!visited[i])
{
// If degree of adjacent after processing becomes
// less than k, then reduce degree of v also.
DFSUtil(i, visited, vDegree, k);
}
}
// Return true if degree of v is less than k
return (vDegree[v] < k);
}
// Prints k cores of an undirected graph
void printKCores(int k)
{
// INITIALIZATION
// Mark all the vertices as not visited and not
// processed.
boolean[] visited = new boolean[V];
boolean[] processed = new boolean[V];
Arrays.fill(visited, false);
Arrays.fill(processed, false);
int mindeg = Integer.MAX_VALUE;
int startvertex = 0;
// Store degrees of all vertices
int[] vDegree = new int[V];
for (int i = 0; i < V; i++)
{
vDegree[i] = adj[i].size();
if (vDegree[i] < mindeg)
{
mindeg = vDegree[i];
startvertex = i;
}
}
DFSUtil(startvertex, visited, vDegree, k);
// DFS traversal to update degrees of all
// vertices.
for (int i = 0; i < V; i++)
if (!visited[i])
DFSUtil(i, visited, vDegree, k);
// PRINTING K CORES
System.out.println("K-Cores : ");
for (int v = 0; v < V; v++)
{
// Only considering those vertices which have degree
// >= K after BFS
if (vDegree[v] >= k)
{
System.out.printf("\n[%d]", v);
// Traverse adjacency list of v and print only
// those adjacent which have vDegree >= k after
// DFS.
for (int i : adj[v])
if (vDegree[i] >= k)
System.out.printf(" -> %d", i);
}
}
}
}
// Driver Code
public static void main(String[] args)
{
// Create a graph given in the above diagram
int k = 3;
Graph g1 = new Graph(9);
g1.addEdge(0, 1);
g1.addEdge(0, 2);
g1.addEdge(1, 2);
g1.addEdge(1, 5);
g1.addEdge(2, 3);
g1.addEdge(2, 4);
g1.addEdge(2, 5);
g1.addEdge(2, 6);
g1.addEdge(3, 4);
g1.addEdge(3, 6);
g1.addEdge(3, 7);
g1.addEdge(4, 6);
g1.addEdge(4, 7);
g1.addEdge(5, 6);
g1.addEdge(5, 8);
g1.addEdge(6, 7);
g1.addEdge(6, 8);
g1.printKCores(k);
System.out.println();
Graph g2 = new Graph(13);
g2.addEdge(0, 1);
g2.addEdge(0, 2);
g2.addEdge(0, 3);
g2.addEdge(1, 4);
g2.addEdge(1, 5);
g2.addEdge(1, 6);
g2.addEdge(2, 7);
g2.addEdge(2, 8);
g2.addEdge(2, 9);
g2.addEdge(3, 10);
g2.addEdge(3, 11);
g2.addEdge(3, 12);
g2.printKCores(k);
}
}
// This code is contributed by
// sanjeev2552
Python3
#saurabh_jain861
# Python program to find K-Cores of a graph
from collections import defaultdict
# This class represents a undirected graph using adjacency
# list representation
class Graph:
def __init__(self):
# default dictionary to store graph
self.graph = defaultdict(list)
# function to add an edge to undirected graph
def addEdge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
# A recursive function to call DFS starting from v.
# It returns true if vDegree of v after processing is less
# than k else false
# It also updates vDegree of adjacent if vDegree of v
# is less than k. And if vDegree of a processed adjacent
# becomes less than k, then it reduces of vDegree of v also,
def DFSUtil(self, v, visited, vDegree, k):
# Mark the current node as visited
visited.add(v)
# Recur for all the vertices adjacent to this vertex
for i in self.graph[v]:
# vDegree of v is less than k, then vDegree of
# adjacent must be reduced
if vDegree[v] < k:
vDegree[i] = vDegree[i] - 1
# If adjacent is not processed, process it
if i not in visited:
# If vDegree of adjacent after processing becomes
# less than k, then reduce vDegree of v also
self.DFSUtil(i, visited, vDegree, k)
def PrintKCores(self, k):
visit = set()
degree = defaultdict(lambda: 0)
for i in list(self.graph):
degree[i] = len(self.graph[i])
for i in list(self.graph):
if i not in visit:
self.DFSUtil(i, visit, degree, k)
# print(degree)
# print(self.graph)
for i in list(self.graph):
if degree[i] >= k:
print(str("\n [ ") + str(i) + str(" ]"), end=" ")
for j in self.graph[i]:
if degree[j] >= k:
print("-> " + str(j), end=" ")
print()
k = 3
g1 = Graph()
g1.addEdge(0, 1)
g1.addEdge(0, 2)
g1.addEdge(1, 2)
g1.addEdge(1, 5)
g1.addEdge(2, 3)
g1.addEdge(2, 4)
g1.addEdge(2, 5)
g1.addEdge(2, 6)
g1.addEdge(3, 4)
g1.addEdge(3, 6)
g1.addEdge(3, 7)
g1.addEdge(4, 6)
g1.addEdge(4, 7)
g1.addEdge(5, 6)
g1.addEdge(5, 8)
g1.addEdge(6, 7)
g1.addEdge(6, 8)
g1.PrintKCores(k)
C#
// C# program to find K-Cores of a graph
using System;
using System.Collections.Generic;
class GFG{
// This class represents a undirected
// graph using adjacency list
// representation
public class Graph
{
// No. of vertices
int V;
// Pointer to an array containing
// adjacency lists
List<int>[] adj;
public Graph(int V)
{
this.V = V;
this.adj = new List<int>[V];
for(int i = 0; i < V; i++)
adj[i] = new List<int>();
}
// Function to add an edge to graph
public void addEdge(int u, int v)
{
this.adj[u].Add(v);
this.adj[v].Add(u);
}
// A recursive function to print DFS
// starting from v. It returns true
// if degree of v after processing
// is less than k else false
// It also updates degree of adjacent
// if degree of v is less than k. And
// if degree of a processed adjacent
// becomes less than k, then it reduces
// of degree of v also,
bool DFSUtil(int v, bool[] visited,
int[] vDegree, int k)
{
// Mark the current node as
// visited and print it
visited[v] = true;
// Recur for all the vertices
// adjacent to this vertex
foreach (int i in adj[v])
{
// Degree of v is less than k,
// then degree of adjacent
// must be reduced
if (vDegree[v] < k)
vDegree[i]--;
// If adjacent is not
// processed, process it
if (!visited[i])
{
// If degree of adjacent after
// processing becomes less than
// k, then reduce degree of v also.
DFSUtil(i, visited, vDegree, k);
}
}
// Return true if degree of
// v is less than k
return (vDegree[v] < k);
}
// Prints k cores of an undirected graph
public void printKCores(int k)
{
// INITIALIZATION
// Mark all the vertices as not
// visited and not processed.
bool[] visited = new bool[V];
//bool[] processed = new bool[V];
int mindeg = int.MaxValue;
int startvertex = 0;
// Store degrees of all vertices
int[] vDegree = new int[V];
for(int i = 0; i < V; i++)
{
vDegree[i] = adj[i].Count;
if (vDegree[i] < mindeg)
{
mindeg = vDegree[i];
startvertex = i;
}
}
DFSUtil(startvertex, visited, vDegree, k);
// DFS traversal to update degrees of all
// vertices.
for(int i = 0; i < V; i++)
if (!visited[i])
DFSUtil(i, visited, vDegree, k);
// PRINTING K CORES
Console.WriteLine("K-Cores : ");
for(int v = 0; v < V; v++)
{
// Only considering those vertices
// which have degree >= K after BFS
if (vDegree[v] >= k)
{
Console.Write("\n " + v);
// Traverse adjacency list of v
// and print only those adjacent
// which have vDegree >= k after
// DFS.
foreach(int i in adj[v])
if (vDegree[i] >= k)
Console.Write(" -> " + i);
}
}
}
}
// Driver Code
public static void Main(String[] args)
{
// Create a graph given in the
// above diagram
int k = 3;
Graph g1 = new Graph(9);
g1.addEdge(0, 1);
g1.addEdge(0, 2);
g1.addEdge(1, 2);
g1.addEdge(1, 5);
g1.addEdge(2, 3);
g1.addEdge(2, 4);
g1.addEdge(2, 5);
g1.addEdge(2, 6);
g1.addEdge(3, 4);
g1.addEdge(3, 6);
g1.addEdge(3, 7);
g1.addEdge(4, 6);
g1.addEdge(4, 7);
g1.addEdge(5, 6);
g1.addEdge(5, 8);
g1.addEdge(6, 7);
g1.addEdge(6, 8);
g1.printKCores(k);
Console.WriteLine();
Graph g2 = new Graph(13);
g2.addEdge(0, 1);
g2.addEdge(0, 2);
g2.addEdge(0, 3);
g2.addEdge(1, 4);
g2.addEdge(1, 5);
g2.addEdge(1, 6);
g2.addEdge(2, 7);
g2.addEdge(2, 8);
g2.addEdge(2, 9);
g2.addEdge(3, 10);
g2.addEdge(3, 11);
g2.addEdge(3, 12);
g2.printKCores(k);
}
}
// This code is contributed by Princi Singh
Producción :
K-Cores : [2] -> 3 -> 4 -> 6 [3] -> 2 -> 4 -> 6 -> 7 [4] -> 2 -> 3 -> 6 -> 7 [6] -> 2 -> 3 -> 4 -> 7 [7] -> 3 -> 4 -> 6 K-Cores : K-Cores : [2] -> 4 -> 3 -> 6 [3] -> 2 -> 4 -> 6 [4] -> 2 -> 3 -> 6 [6] -> 2 -> 3 -> 4
La complejidad temporal de la solución anterior es O(V + E) donde V es el número de vértices y E es el número de aristas.
Conceptos relacionados:
Degeneración: La degeneración de un gráfico es el mayor valor k tal que el gráfico tiene un k-núcleo. Por ejemplo, el gráfico que se muestra arriba tiene 3 núcleos y no tiene 4 núcleos o más. Por lo tanto, el gráfico anterior es 3-degenerado.
La degeneración de un gráfico se usa para medir qué tan disperso es el gráfico.
Referencia:
https://en.wikipedia.org/wiki/Degeneracy_%28graph_theory%29
Este artículo es una contribución de Rachit Belwariar . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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