En la teoría de grafos, la coloración de los bordes de un gráfico es una asignación de «colores» a los bordes del gráfico para que no haya dos bordes adyacentes que tengan el mismo color con una cantidad óptima de colores. Se dice que dos aristas son adyacentes si están conectadas al mismo vértice. No … Continue reading «Coloración de bordes de un gráfico»
Considere el siguiente gráfico, Entre las siguientes secuencias: (I) a b e g h f (II) a b f e h g (III) a b f h g e (IV) a f g h b e ¿Cuáles son los primeros recorridos en profundidad del gráfico anterior? (A) Solo I, II y IV (B) Solo I … Continue reading «Algoritmos | Gráficos transversales | Pregunta 12 – Part 2»
Dado un grafo no dirigido G(V, E) con N vértices y M aristas. Necesitamos encontrar el número mínimo de aristas entre un par dado de vértices (u, v) . Ya hemos discutido este problema usando el enfoque BFS , aquí usaremos el enfoque DFS. Ejemplos: Entrada: para el siguiente gráfico dado, encuentre el número mínimo de … Continue reading «Número mínimo de aristas entre dos vértices de un gráfico usando DFS»
Sea G un grafo no dirigido. Considere un recorrido de G primero en profundidad, y sea T el árbol de búsqueda primero en profundidad resultante. Sea u un vértice en G y sea v el primer vértice nuevo (no visitado) visitado después de visitar u en el recorrido. ¿Cuál de las siguientes afirmaciones es siempre … Continue reading «Algoritmos | Gráficos transversales | Pregunta 12 – Part 3»
Dado un grafo conexo con N vértices y M aristas. La tarea es imprimir el recorrido BFS lexicográficamente más pequeño del gráfico a partir de 1. Nota : Los vértices están numerados del 1 al N. Ejemplos: Input: N = 5, M = 5 Edges: 1 4 3 4 5 4 3 2 1 5 … Continue reading «Imprima el BFS lexicográficamente más pequeño del gráfico a partir de 1»
¿Cuál de las siguientes condiciones es suficiente para detectar el ciclo en un gráfico dirigido? (A) Hay una ventaja desde el Node que se está visitando actualmente hasta un Node ya visitado. (B) Hay una ventaja desde el Node visitado actualmente hasta un ancestro del Node visitado actualmente en el bosque DFS. (C) Cada Node … Continue reading «Algoritmos | Gráficos transversales | Pregunta 9 – Part 1»
Dado un gráfico no dirigido, la tarea es encontrar el tamaño de cada componente conectado e imprimir el número de tamaños únicos de los componentes conectados. Como se muestra arriba, el conteo (tamaño del componente conectado) asociado con los componentes conectados es 2, 3 y 2. Ahora, el conteo único de los componentes es 2 … Continue reading «Conteo de longitudes únicas de componentes conectados para un gráfico no dirigido usando STL»
¿Es la siguiente afirmación verdadera/falsa? Un DFS de un gráfico dirigido siempre produce el mismo número de aristas de árbol, es decir, independientemente del orden en que se consideren los vértices para DFS. (Fuente http://courses.csail.mit.edu/6.006/oldquizzes/solutions/q2-f2008-sol.pdf ) (A) Verdadero (B) Falso Respuesta: (B) Explicación: Considere el siguiente gráfico. Si comenzamos desde ‘a’, entonces hay un borde … Continue reading «Algoritmos | Gráficos transversales | Pregunta 12 – Part 4»
Dado un árbol, y el costo de un subárbol se define como |S|*Y(S) donde |S| es el tamaño del subárbol y AND(S) es AND bit a bit de todos los índices de los Nodes del subárbol, la tarea es encontrar el costo máximo del posible subárbol. Requisito previo : ejemplos de unión de conjuntos disjuntos … Continue reading «Conjunto disjunto de la Unión en los árboles | conjunto 2»
Si el tiempo de terminación del DFS f[u] > f[v] para dos vértices u y v en un grafo dirigido G, y u y v están en el mismo árbol DFS en el bosque DFS, entonces u es un ancestro de v en el profundidad primer árbol. (Fuente http://courses.csail.mit.edu/6.006/oldquizzes/solutions/q2-f2007-sol.pdf ) (A) Verdadero (B) Falso Respuesta: … Continue reading «Algoritmos | Gráficos transversales | Pregunta 12 – Part 5»