Supongamos que la relación de adyacencia de los vértices de un gráfico se representa en una tabla Adj(X,Y). ¿Cuál de las siguientes consultas no puede expresarse mediante una expresión de álgebra relacional de longitud constante?
(A) Lista de todos los vértices adyacentes a un vértice dado
(B) Lista de todos los vértices que tienen bucles propios
(C) Lista de todos los vértices que pertenecen a ciclos de menos de tres vértices
(D) Lista de todos los vértices alcanzables desde un vértice dado
Respuesta: (D)
Explicación: (A) Esta es una consulta simple ya que necesitamos encontrar (X, Y) para una X dada.
(B) Esto también es simple ya que es necesario encontrar (X, X)
(C) :-> Ciclo < 3 . Significa ciclo de longitud 1 y 2. El ciclo de longitud 1 es fácil. Igual que el bucle automático. El ciclo de longitud 2 tampoco es demasiado difícil de calcular. Aunque será un poco complejo, tendrá que hacer como (X,Y) y (Y, X) ambos presentes y X!= Y,. Podemos hacer esto con una consulta RA constante.
(D) :-> Esta es la parte más difícil. Aquí necesitamos encontrar el cierre de vértices. Esto necesitará una especie de bucle. Si el gráfico es como un árbol sesgado, nuestra consulta debe repetirse para O(N) veces. No podemos hacer una consulta de longitud constante aquí.
La respuesta es :-> D
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA