Cuestionario 30 AED

¿Cuáles de las siguientes afirmaciones referidas a conceptos básicos generales sobre grafos son correctas? (Más de una puede ser correcta...). Un grafo puede tener nodos aislados: nodos que no tienen ningún arco incidente a él (ninguno de entrada y ninguno de salida). Dos nodos a y b de un grafo (dirigido o no) pueden tener varios caminos de distinta longitud que los unan. Un grafo puede tener subgrafos no unidos entre sí por arcos que los conecten (o sea, un grafo puede tener dos o más componentes conexas). Todo arco de un grafo, necesaria y obligatoriamente une dos nodos diferentes de ese grafo.

¿Cuál de las siguientes afirmaciones es FALSA respecto de los ciclos en un grafo?. Los ciclos no están permitidos en un grafo. Es válido que un ciclo conste de un único arco que permita vincular a un nodo consigo mismo. Un ciclo es un camino que parte de un nodo y lleva de vuelta al mismo nodo. Los ciclos pueden ser válidos o no, dependiendo del problema que se quiere resolver.

Suponga que se desea modelar con un grafo la estructura del plan de estudios de una carrera universitaria. El equipo de trabajo ha decidido que los vértices del grafo representen asignaturas y los arcos representen restricciones de correlativas previas. Así, el arco (x, y) que parte de la asignatura x y llega a la y indica que para cursar y debe estar regularizada x. Lo anterior implica además que el grafo debe ser dirigido. El equipo de trabajo ha determinado además algunas restricciones obvias que deben controlarse y validarse en todo momento en el sistema de gestión del plan. Indique cuáles de las siguientes situaciones no serían aceptables en el grafo propuesto, y deberían ser evitadas por procesos de validación (aclaración: más de una puede ser seleccionada): Vértices aislados, es decir, vértices a los que no llega ningún arco de entrada y de los cuales tampoco hay arcos de salida. Vértices a los que no llega ningún arco de entrada (aunque podrían tener arcos de salida). La ocurrencia de algún tipo de relación transitiva explícita, es decir, que existan al mismo tiempo los arcos (x, y), (y, z) y (x, z). La ocurrencia de ciclos en general en el grafo. La ocurrencia de auto ciclos en cualquiera de sus vértices.

¿En cuál de las siguientes situaciones no debería usar un grafo dirigido?. Para modelar un plan de estudios de una carrera universitaria. Para modelar un sistema de cañerías que transportan líquidos desde una fuente hasta un destino. Para modelar un plano de rutas entre localidades o ciudades. Para modelar un ”sociograma”: un gráfico que expresa en qué forma un grupo de personas se relacionan entre sí.

¿En cuáles de las siguientes situaciones sería ideal un grafo no dirigido? (Más de una puede ser correcta...). Para modelar un plano de rutas entre localidades o ciudades. Para modelar un sistema de rutas aéreas entre distintos aeropuertos del mundo. Para modelar un plan de estudios de una carrera universitaria. Para modelar un ”sociograma”: un gráfico que expresa en qué forma un grupo de personas se relacionan entre sí.

¿Cuáles de las siguientes expresan afirmaciones ciertas cuando se quiere implementar un grafo ponderado en forma matricial simple? (Más de una puede ser correcta...). Si se almacena solo un entero para representar al arco y su peso, sería inviable representar arcos con pesos múltiples. El problema no existe: no hay manera de representar grafos ponderados en forma matricial. Si se almacena directamente el peso del arco en cada casillero, un problema posible es el de la ambigüedad del cero: no sería posible distinguir si el cero es el peso de un arco, o el indicador de que el arco no existe. Una manera recomendable de implementar un grafo ponderado en forma matricial, es hacer que cada casilla de matriz de adyacencias apunte a un objeto que represente a un arco, y guardar en ese objeto todos los atributos que sean necesarios para la representación del arco.

Un grafo reflexivo es un grafo dirigido en el cual se cumple que todo vértice está relacionado consigo mismo (es decir, todo vértice tiene un auto ciclo). Suponga un grafo G dirigido y reflexivo con n vértices, implementado en forma matricial y asumiendo que la matriz de adyacencias almacena valores boolean en forma directa. ¿Qué se puede afirmar que es verdadero respecto de la matriz de adyacencias de G?. Todos los casilleros de la diagonal principal de la matriz de adyacencia valen True, y sólo ellos pueden valer True. Todos los casilleros de la matriz de adyacencia valen True. Todos los casilleros del triángulo superior de la matriz de adyacencia valen True. Todos los casilleros de la diagonal principal de la matriz de adyacencia valen True, pero no es obligatorio que sólo ellos puedan valer true.

Un grafo simétrico es un grafo dirigido en el cual se cumple que si existe el arco (x, y) entonces existe también el arco (y, x) (es decir, toda vez que existe un arco en un sentido, existe también el arco en sentido contrario). Suponga un grafo G dirigido y simétrico con n vértices, implementado en forma matricial y asumiendo que la matriz de adyacencias almacena valores boolean en forma directa. ¿Qué se puede afirmar que es verdadero respecto de la matriz de adyacencias de G?. Todos los casilleros del triángulo inferior de la matriz de adyacencia valen True y los del triángulo superior valen False. Todos los casilleros de la matriz son True o todos los casilleros son False. Todos los casilleros de la diagonal principal de la matriz de adyacencia valen True. La matriz es simétrica (o espejada) respecto de la diagonal principal: el valor en el casillero ady[x][y] siempre será igual al valor en ady[y][x].

Un grafo transitivo es un grafo dirigido en el cual se cumple que cada vez que existen los arcos (x, y) e (y, z) entonces existe también el arco (x, z). Suponga un grafo G dirigido y transitivo con n vértices, implementado en forma matricial y asumiendo que la matriz de adyacencias almacena valores boolean en forma directa. ¿Qué se puede afirmar que es verdadero respecto de la matriz de adyacencias de G?. Si el casillero ady[y][z] es True entonces el casillero ady[x][z] será también True, sin importar el valor de ady[x][y]. Si el casillero ady[x][y] es True entonces el casillero ady[x][z] será también True, sin importar el valor de ady[y][z]. Si los casilleros ady[x][y] y ady[y][z] son False, entonces el casillero ady[x][z] será True. Si los casilleros ady[x][y] y ady[y][z] son True, entonces el casillero ady[x][z] será también True.

¿Cuáles de las siguientes afirmaciones relativas a la idea arcos de entrada o de salida de un nodo son correctas? (Más de una puede ser correcta...). El Grado de un nodo (tanto si el grafo es dirigido como si es no dirigido) es la cantidad de arcos no incidentes a ese nodo (arcos que no tienen a ese nodo ni como partida ni como llegada). El Grado de un nodo (tanto si el grafo es dirigido como si es no dirigido) es la cantidad de arcos incidentes a ese nodo (arcos que tienen al nodo como partida o como llegada). El Entre Grado de un nodo (o Grado de Entrada) en un grafo dirigido es la cantidad de arcos que tienen a ese nodo como nodo de llegada. El Fuera de Grado de un nodo (o Grado de Salida) en un grafo dirigido es la cantidad de arcos que tienen a ese nodo como nodo de partida.