Algoritmos y estructuras de datos II (primer parcial)

Selecciona las 4 (cuatro) opciones correctas. Considerando las definiciones de grafos y caminos, es correcto señalar que: Un grafo es una representación gráfica. En los grafos, los arcos pueden ser bidireccionales o de único sentido de circulación. Un grafo corresponde a una terna de conjuntos finitos A y V no vacíos, y una aplicación que hace corresponder a un elemento de A un par de elementos de V. Si todos los vértices de un grafo tienen el mismo grado se dice que es regular. Un grafo es solo una dupla de aristas y vértices. Sin relación entre ellos.

Un número importante asociado a cada vértice es el "grado", que se define como el número de arcos que inciden o salen de este. Verdadero. Falso.

La teoría de grafos es una de las ramas más importantes de las matemáticas modernas, y comenzó en el siglo XVIII por una de las mentes más grandes que ha existido, Euler, quien estudiando las relaciones y funciones entre las personas, logró desarrollar y verificar la posibilidad de representar problemas con estas estructuras algebraicas llamadas grafos. Verdadero. Falso.

En el caso de los puentes de Königsberg, el grafo mantiene toda la información del problema y convierte la pregunta de sus ciudadanos en la siguiente: ¿Es posible recorrer todas las ciudades y puentes calculando las distancias recorridas?. Verdadero. Falso.

Considerando A, B, C, D, E y F los vértices de un grafo G, ¿cuál de estos caminos conforma un camino elemental?. F, B, A. A, B, C, D, E, A, F. A, B, D, E, C, D, F.

Selecciona las 4 (cuatro) opciones correctas. ¿Cuáles corresponden a la estrategia de Euler para resolver el problema de los puentes de Konigsberg?. Tomó la información relevante y se deshizo de algunos hechos. Nombró a cada ciudad como un punto (vértice) y a cada puente como una línea que une dos ciudades (aristas). Representó el problema mediante un gráfico simple. Se concentró en la relación entre las ciudades y los puentes. Buscó en la matemática moderna algoritmos de gran complejidad para representar el problema.

¿Qué se mide por la cantidad de aristas que lo compone?. La longitud de un camino. El grado de un grafo. El grado de un nodo.

Completa el fragmento con la opción correcta. Dado el siguiente camino A, B, C, D, B, F, F, es correcto señalar que __________. Contiene ciclos, es un camino compuesto. Es un camino elemental. Es un circuito hamiltoniano y compuesto.

Completa el fragmento con la opción correcta. En la teoría de grafos, es correcto afirmar que __________. Un grafo conexo o conectado es aquel en el que todos sus vértices están conectados por un camino, si el grafo es no dirigido, o por un semicamino, si se trata de un grafo dirigido. Los subgrafos conexos máximos de un grafo no dirigido se llaman componentes biconexos. En los grafos dirigidos, si se considera el sentido de las aristas, se habla de componente débilmente conexo, mientras que, si no se considera el sentido, se habla de componente fuertemente conexo.

Completa el fragmento con la opción correcta. En la teoría de grafos, es correcto definir __________. Un circuito hamiltoniano es un camino que vuelve a su punto de partida pasando por todos los vértices del grafo. Un camino hamiltoniano es el camino elemental que pasa al menos por dos de los vértices del grafo. Un camino elemental es aquel camino que utiliza más de una vez un mismo punto.

Selecciona las 4 (cuatro) opciones correctas. Estos son los tipos de grafo: Plano. Hamiltoniano. Dirigido. Conexo. Circular.

Completa el fragmento con la opción correcta. Dada la clasificación de grafos en simples, completos y multigrafos, es correcto afirmar que __________. Un grafo es simple cuando no incluye ciclos ni aristas paralelas, es un multigrafo si hay dos o más aristas que pueden conectar a un mismo vértice y es un grafo completo si hay aristas entre cada par de vértices. Un grafo es simple cuando no incluye nodos aislados, ciclos ni aristas paralelas, es un multigrafo si hay dos o más aristas que pueden conectar a un mismo vértice y es un grafo completo si hay aristas entre cada par de vértices. Un grafo es simple cuando no incluye ciclos ni aristas paralelas; es un multigrafo si hay aislados o dos o más aristas que pueden conectar a un mismo vértice; y, es un grafo completo si hay aristas entre cada par de vértices.

¿Cuál de estos grafos de 5 vértices con sus grados es un grafo simple?. 3, 3, 3, 3, 2. 1, 2, 3, 4, 4. 1, 2, 3, 4, 5.

Completa el fragmento con la opción correcta. Considerando un grafo completo de 8 vértices, es correcto afirmar que __________. Todos los vértices tienen grado 7 y el número de aristas es 28. Todos los vértices tienen grado 7 y el número de aristas es 21. Todos los vértices tienen grado 8 y el número de aristas es 28.

Completa el fragmento con la opción correcta. Si consideramos la siguiente secuencia de vértices en un camino A, C, D, E, G, E, B, F, F, A, es correcto afirmar que __________. Es un camino compuesto. Conforma un camino elemental. La secuencia de vértices conforma un camino hamiltoniano con 2 bucles.

Completa el fragmento con la opción correcta. Un grafo es plano si __________. Las curvas que representan las aristas se cortan solo en los vértices. Las aristas se cortan solo en un punto con otra arista. Una arista pasa por más de un vértice. Los puntos que representan los vértices contienen ciclos. Es una estructura algebraica que no se puede representar en el plano.

Selecciona las 4 (cuatro) opciones correctas. ¿Cuáles afirmaciones son correctas acerca de un grafo dirigido?. El grado de emisión es el número de arcos que salen de un punto cualquiera del grafo dirigido. Cada arco tiene un nodo fuente y un nodo destino. El grado de recepción es el número de arcos que llegan de un punto determinado del grafo dirigido. Cada entrada es una dupla de 2 nodos. Cada arco puede tener varios nodos destino.

Completa el fragmento con la opción correcta. Las matrices de adyacencia reflejan en acceso de cada __________. Nodo o vértice a otro de forma directa y pueden representar este acceso tanto en grafos no dirigidos como en los dirigidos. Arista de forma indirecta y pueden representar este acceso tanto en grafos no dirigidos como en los dirigidos. Nodo o vértice a otro de forma directa y pueden representar dicho acceso solo en grafos dirigidos. Nodo o vértice a otro de forma directa y pueden representar dicho acceso solo en grafos no dirigidos. Vértice a otro de forma indirecta.

Completa el fragmento con la opción correcta. Si en la matriz de adyacencia de un grafo de 4 vértices A, B, C y D, encontramos en la primera fila los valores 1, 0, 1, 0; en la segunda 0, 0, 0, 1; en la tercera 1, 0, 0, 1 y en la cuarta 0, 1, 1, 1; entonces, podemos afirmar que __________. Hay 2 bucles. No hay acceso desde B a C. Existen 2 nodos aislados.

Completa el fragmento con la opción correcta. Si consideramos los vértices de un grafo V={A, B, C, D, E, F, G} y sus conexiones que forman el siguiente conjunto C={(A, E), (A, F), (C, E), (C, G), (D, G), podemos decir que __________. Es un grafo bipartito con dos subconjuntos de vértices V1 = {A, B, C, D} y V2 = {E, F, G}. Es un grafo bipartito completo. No es un grafo bipartito porque hay un vértice aislado.

¿Qué es un grafo dirigido?. Es aquel en el que un arco tiene sentido de circulación, es decir, es unidireccional; y, si se requiere representar un camino de ida y vuelta, en el gráfico se debe agregar otra flecha en ese sentido. Es aquel en el que un arco no tiene sentido de circulación, es decir, es unidireccional. Es aquel en el que un vértice tiene sentido de circulación, y, si se requiere representar un camino de ida y vuelta, en el gráfico se debe agregar otra flecha en el mismo sentido.