¿Cuál de las siguientes afirmaciones es/son VERDADERAS para un gráfico no dirigido? P: El número de vértices de grado impar es par Q: La suma de los grados de todos los vértices es par (A) Solo P (B) Solo Q (C) Tanto P como Q (D) Ni P ni Q Respuesta: (C) Explicación: P es … Continue reading «Estructuras de datos | Gráfico | Pregunta 9 – Part 1»
La secuencia de grados de un gráfico simple es la secuencia de los grados de los Nodes en el gráfico en orden decreciente. ¿Cuál de las siguientes secuencias no puede ser la secuencia de grados de ningún gráfico? I. 7, 6, 5, 4, 4, 3, 2, 1 II. 6, 6, 6, 6, 3, 3, 2, … Continue reading «Estructuras de datos | Gráfico | Pregunta 2»
En la teoría de grafos, el teorema de Vizing establece que cada gráfico simple no dirigido puede tener bordes coloreados usando una cantidad de colores que es como máximo uno más grande que el grado máximo ‘d’ del gráfico. En sentido simple, este teorema establece que el índice cromático del gráfico simple puede ser ‘d’ … Continue reading «Teorema de Vizing»
Considere un gráfico aleatorio no dirigido de ocho vértices. La probabilidad de que haya una arista entre un par de vértices es 1/2. ¿Cuál es el número esperado de ciclos desordenados de longitud tres? (A) 1/8 (B) 1 (C) 7 (D) 8 Respuesta: (C) Explicación: Se puede formar un ciclo de longitud 3 con 3 … Continue reading «Estructuras de datos | Gráfico | Pregunta 8»
Una lista de adyacencia se utiliza para representar gráficos. Aquí, para cada vértice en el gráfico, tenemos una lista de todos los otros vértices a los que el vértice en particular tiene una arista. Problema: Dada la lista de adyacencia y el número de vértices y aristas de un gráfico, la tarea es representar la … Continue reading «Imprimir lista de adyacencia para un gráfico dirigido»
¿Cuántos grafos no dirigidos (no necesariamente conexos) se pueden construir a partir de un conjunto dado V= {V 1, V 2,…V n} de n vértices? (A) n(nl)/2 (B) 2^n (C) n! (D) 2^(n(n-1)/2) Respuesta: (D) Explicación: En un gráfico no dirigido, puede haber un máximo de n(n-1)/2 aristas. Podemos elegir tener (o no tener) cualquiera … Continue reading «Estructuras de datos | Gráfico | Pregunta 6»
Árbol: – Un gráfico conexo sin ningún circuito se llama árbol. En otras palabras, un árbol es un grafo no dirigido G que satisface cualquiera de las siguientes condiciones equivalentes: Dos vértices cualesquiera de G pueden estar conectados por un único camino simple. G es acíclico y se forma un ciclo simple si se agrega … Continue reading «Algunos teoremas básicos sobre árboles»
Se sabe que la complejidad temporal de calcular el cierre transitivo de una relación binaria en un conjunto de n elementos es: (A) O(n) (B) O(nLogn) (C) O(n ^ (3/2)) (D) O(n^3) Respuesta: (D) Explicación: Consulte la pregunta 3 de https://www.geeksforgeeks.org/data-structures-and-algorithms-set-22/ Publicación traducida automáticamente Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original … Continue reading «Estructuras de datos | Gráfico | Pregunta 3»
Dado un gráfico acíclico dirigido que tiene V vértices y E aristas, donde cada arista {U, V} representa los trabajos U y V , de modo que el trabajo V solo puede iniciarse después de completar el trabajo U. La tarea es determinar el tiempo mínimo que tarda cada trabajo en completarse, donde cada trabajo … Continue reading «Tiempo mínimo que tarda cada trabajo en completarse dado por un gráfico acíclico dirigido»
Considere un grafo no ponderado no dirigido G. Haga un recorrido de G primero en anchura a partir de un Node r. Sean d(r, u) y d(r, v) las longitudes de los caminos más cortos de r a u y v respectivamente, en G. Si se visita u antes que v durante el recorrido primero … Continue reading «Estructuras de datos | Gráfico | Pregunta 5»