Cuente el número de Prime Cliques en un gráfico no dirigido

Dado un gráfico con N Nodes y E aristas, la tarea es contar el número de camarillas que tienen su tamaño como número primo o número primo de Nodes en el gráfico dado. 

Una camarilla es un subgrafo completo de un grafo dado.

Ejemplos:

Entrada: N = 5, aristas[] = { {1, 2}, {2, 3}, {3, 1}, {4, 3}, {4, 5}, {5, 3} } 
 

Salida:
Explicación: 
En el gráfico no dirigido dado, 1->2->3 y 3->4->5 son los dos subgrafos completos, ambos de tamaño 3, que es un número primo. 
Además, 1-2, 2->3, 3->1, 4->3, 4->5 y 5->3 son subgrafos completos de tamaño 2. 
Por lo tanto, hay 8 camarillas principales. 

Enfoque: Para resolver el problema mencionado anteriormente, la idea principal es utilizar la recursividad . Se encuentran todos los vértices cuyo grado es mayor o igual a (K-1) y se comprueba qué subconjunto de K vértices forman una camarilla. Cuando se agrega otro borde a la lista actual, se verifica si al agregar ese borde, la lista todavía forma una camarilla o no. Se pueden seguir los siguientes pasos para calcular el resultado: 

  • Para comprobar si el tamaño de la camarilla es primo o no, la idea es usar Sieve Of eratosthenes . Crea un tamiz que nos ayude a identificar si el tamaño es primo o no en tiempo O(1) .
  • Forme una función recursiva con tres parámetros, Node inicial, longitud del conjunto actual de Nodes y arreglo primo (para comprobar los números primos).
  • El índice inicial parece que no se puede agregar ningún Node al conjunto actual menos que ese índice. Entonces se ejecuta un bucle desde ese índice hasta n.
  • Encuentre que después de agregar un Node al conjunto actual , el conjunto de Nodes sigue siendo una camarilla. En caso afirmativo, se agrega ese Node, luego se verifica el tamaño actual de la camarilla, si es primo, la respuesta aumenta en 1 y luego se llama a la función recursiva con los parámetros índice del nuevo Node agregado + 1, longitud del conjunto actual + 1 y la array principal.
  • Los vértices se suman hasta que la lista no forma una camarilla. Al final, se imprime la respuesta que contiene el número de camarillas principales.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation to Count the number
// of Prime Cliques in an undirected graph
 
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 100;
 
// Stores the vertices
int store[MAX], n;
 
// Graph
int graph[MAX][MAX];
 
// Degree of the vertices
int d[MAX];
 
// To store the count of prime cliques
int ans;
 
// Function to create
// Sieve to check primes
void SieveOfEratosthenes(
    bool prime[], int p_size)
{
    // false here indicates
    // that it is not prime
    prime[0] = false;
    prime[1] = false;
 
    for (int p = 2; p * p <= p_size; p++) {
 
        // Condition if prime[p]
        // is not changed,
        // then it is a prime
        if (prime[p]) {
 
            // Update all multiples of p,
            // set them to non-prime
            for (int i = p * 2; i <= p_size; i += p)
                prime[i] = false;
        }
    }
}
 
// Function to check
// if the given set of
// vertices in store array
// is a clique or not
bool is_clique(int b)
{
 
    // Run a loop for all set of edges
    for (int i = 1; i < b; i++) {
        for (int j = i + 1; j < b; j++)
 
            // If any edge is missing
            if (graph[store[i]][store[j]] == 0)
                return false;
    }
    return true;
}
 
// Function to find the count of
// all the cliques having prime size
void primeCliques(int i, int l,
                  bool prime[])
{
    // Check if any vertices from i+1
    // can be inserted
    for (int j = i + 1; j <= n; j++) {
 
        // Add the vertex to store
        store[l] = j;
 
        // If the graph is not
        // a clique of size k then
        // it cannot be a clique
        // by adding another edge
        if (is_clique(l + 1)) {
 
            // increase the count of
            // prime cliques if the size
            // of current clique is prime
            if (prime[l])
                ans++;
 
            // Check if another edge
            // can be added
            primeCliques(j, l + 1, prime);
        }
    }
}
 
// Driver code
int main()
{
    int edges[][2] = { { 1, 2 },
                       { 2, 3 },
                       { 3, 1 },
                       { 4, 3 },
                       { 4, 5 },
                       { 5, 3 } };
 
    int size = sizeof(edges)
               / sizeof(edges[0]);
    n = 5;
 
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
 
    SieveOfEratosthenes(prime, n + 1);
 
    for (int i = 0; i < size; i++) {
        graph[edges[i][0]][edges[i][1]] = 1;
        graph[edges[i][1]][edges[i][0]] = 1;
        d[edges[i][0]]++;
        d[edges[i][1]]++;
    }
 
    ans = 0;
    primeCliques(0, 1, prime);
 
    cout << ans << "\n";
 
    return 0;
}

Java

// Java implementation to Count the number
// of Prime Cliques in an undirected graph
import java.io.*;
import java.util.*;
 
class GFG {
     
static final int MAX = 100;
 
// Stores the vertices
static int[] store = new int[MAX];
static int n;
 
// Graph
static int[][] graph = new int[MAX][MAX];
 
// Degree of the vertices
static int[] d = new int[MAX];
 
// To store the count of prime cliques
static int ans;
 
// Function to create
// Sieve to check primes
static void SieveOfEratosthenes(boolean prime[],
                                int p_size)
{
     
    // False here indicates
    // that it is not prime
    prime[0] = false;
    prime[1] = false;
 
    for(int p = 2; p * p <= p_size; p++)
    {
         
       // Condition if prime[p]
       // is not changed,
       // then it is a prime
       if (prime[p])
       {
            
           // Update all multiples of p,
           // set them to non-prime
            for(int i = p * 2; i <= p_size; i += p)
               prime[i] = false;
       }
    }
}
 
// Function to check
// if the given set of
// vertices in store array
// is a clique or not
static boolean is_clique(int b)
{
 
    // Run a loop for all set of edges
    for(int i = 1; i < b; i++)
    {
       for(int j = i + 1; j < b; j++)
        
          // If any edge is missing
          if (graph[store[i]][store[j]] == 0)
             return false;
    }
    return true;
}
 
// Function to find the count of
// all the cliques having prime size
static void primeCliques(int i, int l,
                         boolean prime[])
{
     
    // Check if any vertices from i+1
    // can be inserted
    for(int j = i + 1; j <= n; j++)
    {
        
       // Add the vertex to store
       store[l] = j;
        
       // If the graph is not
       // a clique of size k then
       // it cannot be a clique
       // by adding another edge
       if (is_clique(l + 1))
       {
            
           // Increase the count of
           // prime cliques if the size
           // of current clique is prime
           if (prime[l])
               ans++;
                
           // Check if another edge
           // can be added
           primeCliques(j, l + 1, prime);
       }
    }
}
     
// Driver code
public static void main(String[] args)
{
    int edges[][] = { { 1, 2 },
                      { 2, 3 },
                      { 3, 1 },
                      { 4, 3 },
                      { 4, 5 },
                      { 5, 3 } };
 
    int size = edges.length;
    n = 5;
 
    boolean[] prime = new boolean[n + 1];
    Arrays.fill(prime, true);
 
    SieveOfEratosthenes(prime, n);
 
    for(int i = 0; i < size; i++)
    {
       graph[edges[i][0]][edges[i][1]] = 1;
       graph[edges[i][1]][edges[i][0]] = 1;
       d[edges[i][0]]++;
       d[edges[i][1]]++;
    }
     
    ans = 0;
    primeCliques(0, 1, prime);
 
    System.out.println(ans);
}
}
 
// This code is contributed by coder001

Python3

# Python3 implementation to Count the number
# of Prime Cliques in an undirected graph
MAX = 100
  
# Stores the vertices
store = [0 for i in range(MAX)]
n = 0
  
# Graph
graph = [[0 for j in range(MAX)]
            for i in range(MAX)]
  
# Degree of the vertices
d = [0 for i in range(MAX)]
  
# To store the count of prime cliques
ans = 0
  
# Function to create
# Sieve to check primes
def SieveOfEratosthenes(prime, p_size):
     
    # false here indicates
    # that it is not prime
    prime[0] = False
    prime[1] = False
     
    p = 2
     
    while (p * p <= p_size):
         
        # Condition if prime[p]
        # is not changed,
        # then it is a prime
        if (prime[p]):
             
            # Update all multiples of p,
            # set them to non-prime
            for i in range(p * 2, p_size + 1, p):
                prime[i] = False
                 
        p += 1
         
# Function to check if the given
# set of vertices in store array
# is a clique or not
def is_clique(b):
  
    # Run a loop for all set of edges
    for i in range(1, b):
        for j in range(i + 1, b):
  
            # If any edge is missing
            if (graph[store[i]][store[j]] == 0):
                return False
     
    return True
 
# Function to find the count of
# all the cliques having prime size
def primeCliques(i, l, prime):
     
    global ans
     
    # Check if any vertices from i+1
    # can be inserted
    for j in range(i + 1, n + 1):
  
        # Add the vertex to store
        store[l] = j
  
        # If the graph is not
        # a clique of size k then
        # it cannot be a clique
        # by adding another edge
        if (is_clique(l + 1)):
  
            # Increase the count of
            # prime cliques if the size
            # of current clique is prime
            if (prime[l]):
                ans += 1
  
            # Check if another edge
            # can be added
            primeCliques(j, l + 1, prime)
     
# Driver code
if __name__=='__main__':
     
    edges = [ [ 1, 2 ], [ 2, 3 ],
              [ 3, 1 ], [ 4, 3 ],
              [ 4, 5 ], [ 5, 3 ] ]
     
    size = len(edges)
     
    n = 5
  
    prime = [True for i in range(n + 2)]
  
    SieveOfEratosthenes(prime, n + 1)
  
    for i in range(size):
        graph[edges[i][0]][edges[i][1]] = 1
        graph[edges[i][1]][edges[i][0]] = 1
        d[edges[i][0]] += 1
        d[edges[i][1]] += 1
     
    ans = 0
    primeCliques(0, 1, prime)
     
    print(ans)
 
# This code is contributed by rutvik_56

C#

// C# implementation to count the number
// of Prime Cliques in an undirected graph
using System;
 
class GFG{
     
static readonly int MAX = 100;
 
// Stores the vertices
static int[] store = new int[MAX];
static int n;
 
// Graph
static int[,] graph = new int[MAX, MAX];
 
// Degree of the vertices
static int[] d = new int[MAX];
 
// To store the count of prime cliques
static int ans;
 
// Function to create
// Sieve to check primes
static void SieveOfEratosthenes(bool []prime,
                                int p_size)
{
     
    // False here indicates
    // that it is not prime
    prime[0] = false;
    prime[1] = false;
 
    for(int p = 2; p * p <= p_size; p++)
    {
        
       // Condition if prime[p]
       // is not changed,
       // then it is a prime
       if (prime[p])
       {
            
           // Update all multiples of p,
           // set them to non-prime
           for(int i = p * 2; i <= p_size;
                   i += p)
              prime[i] = false;
       }
    }
}
 
// Function to check if the given
// set of vertices in store array
// is a clique or not
static bool is_clique(int b)
{
 
    // Run a loop for all set of edges
    for(int i = 1; i < b; i++)
    {
       for(int j = i + 1; j < b; j++)
        
          // If any edge is missing
          if (graph[store[i],store[j]] == 0)
              return false;
    }
    return true;
}
 
// Function to find the count of
// all the cliques having prime size
static void primeCliques(int i, int l,
                         bool []prime)
{
     
    // Check if any vertices from i+1
    // can be inserted
    for(int j = i + 1; j <= n; j++)
    {
        
       // Add the vertex to store
       store[l] = j;
        
       // If the graph is not
       // a clique of size k then
       // it cannot be a clique
       // by adding another edge
       if (is_clique(l + 1))
       {
            
           // Increase the count of
           // prime cliques if the size
           // of current clique is prime
           if (prime[l])
               ans++;
            
           // Check if another edge
           // can be added
           primeCliques(j, l + 1, prime);
       }
    }
}
     
// Driver code
public static void Main(String[] args)
{
    int [,]edges = { { 1, 2 },
                     { 2, 3 },
                     { 3, 1 },
                     { 4, 3 },
                     { 4, 5 },
                     { 5, 3 } };
                      
    int size = edges.GetLength(0);
    n = 5;
 
    bool[] prime = new bool[n + 1];
    for(int i = 0; i < prime.Length; i++)
       prime[i] = true;
 
    SieveOfEratosthenes(prime, n);
 
    for(int i = 0; i < size; i++)
    {
       graph[edges[i, 0],edges[i, 1]] = 1;
       graph[edges[i, 1],edges[i, 0]] = 1;
       d[edges[i, 0]]++;
       d[edges[i, 1]]++;
    }
     
    ans = 0;
    primeCliques(0, 1, prime);
 
    Console.WriteLine(ans);
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
    // Javascript implementation to count the number
    // of Prime Cliques in an undirected graph
     
    let MAX = 100;
  
    // Stores the vertices
    let store = new Array(MAX);
    store.fill(0);
    let n;
 
    // Graph
    let graph = new Array(MAX);
    for(let i = 0; i < MAX; i++)
    {
        graph[i] = new Array(MAX);
    }
 
    // Degree of the vertices
    let d = new Array(MAX);
    d.fill(0);
 
    // To store the count of prime cliques
    let ans;
 
    // Function to create
    // Sieve to check primes
    function SieveOfEratosthenes(prime, p_size)
    {
 
        // False here indicates
        // that it is not prime
        prime[0] = false;
        prime[1] = false;
 
        for(let p = 2; p * p <= p_size; p++)
        {
 
           // Condition if prime[p]
           // is not changed,
           // then it is a prime
           if (prime[p])
           {
 
               // Update all multiples of p,
               // set them to non-prime
               for(let i = p * 2; i <= p_size;
                       i += p)
                  prime[i] = false;
           }
        }
    }
 
    // Function to check if the given
    // set of vertices in store array
    // is a clique or not
    function is_clique(b)
    {
 
        // Run a loop for all set of edges
        for(let i = 1; i < b; i++)
        {
           for(let j = i + 1; j < b; j++)
 
              // If any edge is missing
              if (graph[store[i]][store[j]] == 0)
              {
                  return false;
              }
        }
        return true;
    }
 
    // Function to find the count of
    // all the cliques having prime size
    function primeCliques(i, l, prime)
    {
 
        // Check if any vertices from i+1
        // can be inserted
        for(let j = i + 1; j <= n; j++)
        {
 
           // Add the vertex to store
           store[l] = j;
 
           // If the graph is not
           // a clique of size k then
           // it cannot be a clique
           // by adding another edge
           if (is_clique(l + 1))
           {
 
               // Increase the count of
               // prime cliques if the size
               // of current clique is prime
               if (prime[l])
                   ans++;
               else
               {
                   ans-=1.3;
               }
              
               // Check if another edge
               // can be added
               primeCliques(j, l + 1, prime);
           }
        }
    }
     
    let edges = [ [ 1, 2 ],
                     [ 2, 3 ],
                     [ 3, 1 ],
                     [ 4, 3 ],
                     [ 4, 5 ],
                     [ 5, 3 ] ];
                       
    let size = edges.length;
    n = 5;
  
    let prime = new Array(n + 1);
    for(let i = 0; i < prime.length; i++)
       prime[i] = true;
  
    SieveOfEratosthenes(prime, n);
  
    for(let i = 0; i < size; i++)
    {
       graph[edges[i][0],edges[i][1]] = 1;
       graph[edges[i][1],edges[i][0]] = 1;
       d[edges[i][0]]++;
       d[edges[i][1]]++;
    }
      
    ans = 0;
    primeCliques(0, 1, prime);
  
    document.write(ans);
 
// This code is contributed by suresh07.
</script>
Producción: 

8

 

Publicación traducida automáticamente

Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *