Dado un gráfico dirigido, compruebe si el gráfico contiene un ciclo o no. Su función debería devolver verdadero si el gráfico dado contiene al menos un ciclo, de lo contrario devolverá falso. Ejemplo: C++ // A DFS based approach to find if there is a cycle // in a directed graph. This approach strictly follows … Continue reading «Detectar ciclo en un gráfico dirigido usando colores»
La coloración de gráficos es la tarea de asignar colores a los vértices de un gráfico para que: a los pares de vértices adyacentes se les asignan colores diferentes, y el número de colores diferentes utilizados en el gráfico es mínimo. El siguiente gráfico ha sido coloreado usando solo tres colores (rojo, azul y verde … Continue reading «Algoritmo DSatur para colorear gráficos»
Presentamos la coloración de gráficos y las aplicaciones en la publicación anterior. Como se discutió en la publicación anterior, la coloración de gráficos se usa ampliamente. Desafortunadamente, no existe un algoritmo eficiente disponible para colorear un gráfico con un número mínimo de colores, ya que el problema es un problema NP completo conocido . Sin … Continue reading «Gráfico para colorear | Conjunto 2 (algoritmo codicioso)»
Dado un gráfico no dirigido y un número m, determine si el gráfico se puede colorear con m colores como máximo, de modo que no haya dos vértices adyacentes del gráfico coloreados con el mismo color. Aquí la coloración de un gráfico significa la asignación de colores a todos los vértices. Formato de entrada-salida: Aporte: … Continue reading «m Problema de coloración | Retrocediendo-5»
Dado un árbol genérico que consta de N Nodes y (N – 1) aristas y una array de consultas consulta[] de tamaño Q que consta del tipo {A, B} , la tarea de cada consulta es verificar si la longitud de la ruta entre dos dados los Nodes A y B es par o impar. … Continue reading «Encuentre si la longitud de la ruta es par o impar entre los Nodes de árbol dados para consultas Q»
Dado un gráfico que consta de N Nodes, donde cada Node representa un examen y una array 2D Edges[][2] tal que cada par del examen (Edges[i][0], Edges[i][1]) denota el borde entre ellos, la tarea es encontrar la cantidad mínima de días necesarios para programar todos los exámenes de modo que no se programen dos exámenes … Continue reading «Número mínimo de días necesarios para programar todos los exámenes»