Número mínimo de colores necesarios para colorear un gráfico

Posted on by Rudeus Greyrat

Dado un grafo con N vértices y E aristas. Los bordes se dan como U[] y V[] de modo que para cada índice i, U[i] está conectado a V[i] . La tarea es encontrar el número mínimo de colores necesarios para colorear el gráfico dado.
Ejemplos 
 

Entrada: N = 5, M = 6, U[] = { 1, 2, 3, 1, 2, 3 }, V[] = { 3, 3, 4, 4, 5, 5 }; 
Salida: 3 
Explicación: 
Para el gráfico anterior, los Nodes 1, 3 y 5 no pueden tener el mismo color. Por lo tanto, la cuenta es 3. 
 

Enfoque: 
mantendremos dos arreglos count[] y colors[] . La array count[] almacenará el recuento de bordes para cada Node y colors[] almacenará los colores de cada Node. Inicialice el recuento de cada vértice en 0 y el color de cada vértice en 1. 
Pasos: 
 

  1. Haga una lista de adyacencia para el conjunto de aristas dado y mantenga el conteo de aristas para cada Node
  2. Iterar sobre todos los Nodes e insertar el Node en la cola Q que no tiene borde.
  3. Si bien Q no está vacío, haga lo siguiente: 
    • Extraiga el elemento de la cola.
    • Para todos los Nodes conectados al Node emergente: 
      1. Disminuya la cuenta del borde actual para el Node reventado.
      2. Si el color del actual es menor o igual al color de su padre (el Node que se abrió), actualice el color del Node actual = 1 + color del Node abierto
      3. Si el recuento es cero , inserte este Node en la cola Q.
  4. El elemento máximo en la array colors[] dará el número mínimo de colores necesarios para colorear el gráfico dado.

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

C++

// C++ program to find the minimum
// number of colors needed to color
// the graph
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the minimum
// number of color required
void minimumColors(int N, int E,
                   int U[], int V[])
{
 
    // Create array of vectors
    // to make adjacency list
    vector<int> adj[N];
 
    // Initialise colors array to 1
    // and count array to 0
    vector<int> count(N, 0);
    vector<int> colors(N, 1);
 
    // Create adjacency list of
    // a graph
    for (int i = 0; i < N; i++) {
        adj[V[i] - 1].push_back(U[i] - 1);
        count[U[i] - 1]++;
    }
 
    // Declare queue Q
    queue<int> Q;
 
    // Traverse count[] and insert
    // in Q if count[i] = 0;
    for (int i = 0; i < N; i++) {
        if (count[i] == 0) {
            Q.push(i);
        }
    }
 
    // Traverse queue and update
    // the count of colors
    // adjacent node
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
 
        // Traverse node u
        for (auto x : adj[u]) {
            count[x]--;
 
            // If count[x] = 0
            // insert in Q
            if (count[x] == 0) {
                Q.push(x);
            }
 
            // If colors of child
            // node is less than
            // parent node, update
            // the count by 1
            if (colors[x] <= colors[u]) {
                colors[x] = 1 + colors[u];
            }
        }
    }
 
    // Stores the minimumColors
    // requires to color the graph.
    int minColor = -1;
 
    // Find the maximum of colors[]
    for (int i = 0; i < N; i++) {
        minColor = max(minColor, colors[i]);
    }
 
    // Print the minimum no. of
    // colors required.
    cout << minColor << endl;
}
 
// Driver function
int main()
{
    int N = 5, E = 6;
    int U[] = { 1, 2, 3, 1, 2, 3 };
    int V[] = { 3, 3, 4, 4, 5, 5 };
 
    minimumColors(N, E, U, V);
    return 0;
}

Java

// Java program to find the minimum
// number of colors needed to color
// the graph
import java.util.*;
 
class GFG
{
 
// Function to count the minimum
// number of color required
static void minimumColors(int N, int E,
                int U[], int V[])
{
 
    // Create array of vectors
    // to make adjacency list
    Vector<Integer> []adj = new Vector[N];
 
    // Initialise colors array to 1
    // and count array to 0
    int []count = new int[N];
    int []colors = new int[N];
    for (int i = 0; i < N; i++) {
        adj[i] = new Vector<Integer>();
        colors[i] = 1;
    }
     
    // Create adjacency list of
    // a graph
    for (int i = 0; i < N; i++) {
        adj[V[i] - 1].add(U[i] - 1);
        count[U[i] - 1]++;
    }
 
    // Declare queue Q
    Queue<Integer> Q = new LinkedList<>();
 
    // Traverse count[] and insert
    // in Q if count[i] = 0;
    for (int i = 0; i < N; i++) {
        if (count[i] == 0) {
            Q.add(i);
        }
    }
 
    // Traverse queue and update
    // the count of colors
    // adjacent node
    while (!Q.isEmpty()) {
        int u = Q.peek();
        Q.remove();
 
        // Traverse node u
        for (int x : adj[u]) {
            count[x]--;
 
            // If count[x] = 0
            // insert in Q
            if (count[x] == 0) {
                Q.add(x);
            }
 
            // If colors of child
            // node is less than
            // parent node, update
            // the count by 1
            if (colors[x] <= colors[u]) {
                colors[x] = 1 + colors[u];
            }
        }
    }
 
    // Stores the minimumColors
    // requires to color the graph.
    int minColor = -1;
 
    // Find the maximum of colors[]
    for (int i = 0; i < N; i++) {
        minColor = Math.max(minColor, colors[i]);
    }
 
    // Print the minimum no. of
    // colors required.
    System.out.print(minColor +"\n");
}
 
// Driver function
public static void main(String[] args)
{
    int N = 5, E = 6;
    int U[] = { 1, 2, 3, 1, 2, 3 };
    int V[] = { 3, 3, 4, 4, 5, 5 };
 
    minimumColors(N, E, U, V);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to find the minimum
# number of colors needed to color
# the graph
from collections import deque
 
# Function to count the minimum
# number of color required
def minimumColors(N, E, U, V):
 
    # Create array of vectors
    # to make adjacency list
    adj = [[] for i in range(N)]
 
    # Initialise colors array to 1
    # and count array to 0
    count = [0]*N
    colors = [1]*(N)
 
    # Create adjacency list of
    # a graph
    for i in range(N):
        adj[V[i] - 1].append(U[i] - 1)
        count[U[i] - 1] += 1
 
    # Declare queue Q
    Q = deque()
 
    # Traverse count[] and insert
    # in Q if count[i] = 0
    for i in range(N):
        if (count[i] == 0):
            Q.append(i)
 
    # Traverse queue and update
    # the count of colors
    # adjacent node
    while len(Q) > 0:
        u = Q.popleft()
 
        # Traverse node u
        for x in adj[u]:
            count[x] -= 1
 
            # If count[x] = 0
            # insert in Q
            if (count[x] == 0):
                Q.append(x)
 
            # If colors of child
            # node is less than
            # parent node, update
            # the count by 1
            if (colors[x] <= colors[u]):
                colors[x] = 1 + colors[u]
 
    # Stores the minimumColors
    # requires to color the graph.
    minColor = -1
 
    # Find the maximum of colors[]
    for i in range(N):
        minColor = max(minColor, colors[i])
 
    # Print the minimum no. of
    # colors required.
    print(minColor)
 
# Driver function
N = 5
E = 6
U = [1, 2, 3, 1, 2, 3]
V = [3, 3, 4, 4, 5, 5]
 
minimumColors(N, E, U, V)
 
# This code is contributed by mohit kumar 29

C#

// C# program to find the minimum
// number of colors needed to color
// the graph
using System;
using System.Collections.Generic;
 
class GFG
{
  
// Function to count the minimum
// number of color required
static void minimumColors(int N, int E,
                int []U, int []V)
{
  
    // Create array of vectors
    // to make adjacency list
    List<int> []adj = new List<int>[N];
  
    // Initialise colors array to 1
    // and count array to 0
    int []count = new int[N];
    int []colors = new int[N];
    for (int i = 0; i < N; i++) {
        adj[i] = new List<int>();
        colors[i] = 1;
    }
      
    // Create adjacency list of
    // a graph
    for (int i = 0; i < N; i++) {
        adj[V[i] - 1].Add(U[i] - 1);
        count[U[i] - 1]++;
    }
  
    // Declare queue Q
    List<int> Q = new List<int>();
  
    // Traverse []count and insert
    // in Q if count[i] = 0;
    for (int i = 0; i < N; i++) {
        if (count[i] == 0) {
            Q.Add(i);
        }
    }
  
    // Traverse queue and update
    // the count of colors
    // adjacent node
    while (Q.Count!=0) {
        int u = Q[0];
        Q.RemoveAt(0);
  
        // Traverse node u
        foreach (int x in adj[u]) {
            count[x]--;
  
            // If count[x] = 0
            // insert in Q
            if (count[x] == 0) {
                Q.Add(x);
            }
  
            // If colors of child
            // node is less than
            // parent node, update
            // the count by 1
            if (colors[x] <= colors[u]) {
                colors[x] = 1 + colors[u];
            }
        }
    }
  
    // Stores the minimumColors
    // requires to color the graph.
    int minColor = -1;
  
    // Find the maximum of colors[]
    for (int i = 0; i < N; i++) {
        minColor = Math.Max(minColor, colors[i]);
    }
  
    // Print the minimum no. of
    // colors required.
    Console.Write(minColor +"\n");
}
  
// Driver function
public static void Main(String[] args)
{
    int N = 5, E = 6;
    int []U = { 1, 2, 3, 1, 2, 3 };
    int []V = { 3, 3, 4, 4, 5, 5 };
  
    minimumColors(N, E, U, V);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript program to find the minimum
// number of colors needed to color
// the graph
 
// Function to count the minimum
// number of color required
function minimumColors(N,E,U,V)
{
    // Create array of vectors
    // to make adjacency list
    let adj = new Array(N);
   
    // Initialise colors array to 1
    // and count array to 0
    let count = new Array(N);
    let colors = new Array(N);
    for (let i = 0; i < N; i++) {
        adj[i] = [];
        colors[i] = 1;
        count[i]=0;
    }
       
    // Create adjacency list of
    // a graph
    for (let i = 0; i < N; i++) {
        adj[V[i] - 1].push(U[i] - 1);
        count[U[i] - 1]++;
    }
   
    // Declare queue Q
    let Q = [];
   
    // Traverse count[] and insert
    // in Q if count[i] = 0;
    for (let i = 0; i < N; i++) {
        if (count[i] == 0) {
            Q.push(i);
        }
    }
   
    // Traverse queue and update
    // the count of colors
    // adjacent node
    while (Q.length!=0) {
        let u = Q.shift();
         
   
        // Traverse node u
        for (let x=0;x<adj[u].length;x++) {
            count[adj[u][x]]--;
   
            // If count[x] = 0
            // insert in Q
            if (count[adj[u][x]] == 0) {
                Q.push(adj[u][x]);
            }
   
            // If colors of child
            // node is less than
            // parent node, update
            // the count by 1
            if (colors[adj[u][x]] <= colors[u]) {
                colors[adj[u][x]] = 1 + colors[u];
            }
        }
    }
   
    // Stores the minimumColors
    // requires to color the graph.
    let minColor = -1;
   
    // Find the maximum of colors[]
    for (let i = 0; i < N; i++) {
        minColor = Math.max(minColor, colors[i]);
    }
   
    // Print the minimum no. of
    // colors required.
    document.write(minColor +"\n");
}
 
// Driver function
let N = 5, E = 6;
let U = [ 1, 2, 3, 1, 2, 3 ];
let V = [ 3, 3, 4, 4, 5, 5 ];
 
minimumColors(N, E, U, V);
 
 
// This code is contributed by unknown2108
</script>
Producción: 

3

 

Complejidad temporal: O(N+E), donde N = número de vértices y E = número de aristas
 

Publicación traducida automáticamente

Artículo escrito por lalit kumar 7 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 *