tema 4 md

Un grafo simple se caracteriza por: A) Tener aristas dirigidas. B) No tener bucles ni aristas paralelas. C) Tener pesos en las aristas. D) Tener al menos un ciclo.

El grafo trivial es aquel que: A) Tiene un solo vértice y una arista. B) Tiene dos vértices aislados. C) Tiene un único vértice y ninguna arista. D) No tiene vértices.

En un dígrafo, el tamaño del grafo es: A) El número de vértices. B) El número de aristas no orientadas. C) El número de arcos. D) El número de componentes conexas.

La longitud de un camino en un grafo es: A) El número de vértices distintos. B) El número de aristas que contiene. C) El peso total del camino. D) El número de ciclos que recorre.

Un camino elemental es aquel que: A) No repite aristas. B) No repite vértices. C) No repite ni vértices ni aristas. D) Es siempre cerrado.

Un circuito se define como: A) Un camino elemental cerrado. B) Un camino simple cerrado. C) Un camino elemental abierto. D) Un ciclo de longitud mayor que 3.

Todo ciclo es: A) Un camino abierto. B) Un camino simple no cerrado. C) Un circuito. D) Una cadena.

La longitud mínima de un ciclo es: A) 1. B) 2. C) 3. D) 4.

El grado de un vértice es: A) El número de vértices adyacentes. B) El número de aristas incidentes en él. C) El número de ciclos que pasan por él. D) El número de caminos que parten de él.

En un dígrafo, un vértice con grado de entrada 0 se llama: A) Sumidero. B) Fuente. C) Aislado. D) Regular.

La matriz de adyacencia de un grafo simple no dirigido es: A) Siempre triangular. B) Siempre diagonal. C) Simétrica. D) Booleana no simétrica.

El elemento 𝑎'𝑖𝑗​ de la matriz 𝐴^𝑘 representa: A) El número de aristas entre 𝑣𝑖 y 𝑣𝑗. B) El número de caminos de longitud k entre 𝑣𝑖 y 𝑣𝑗. C) El grado del vértice 𝑣𝑖. D) El número de ciclos del grafo.

La matriz de incidencia de un grafo tiene dimensiones n vertices y m aristas: A) n × n. B) m × m. C) n × m. D) m × n.

Un grafo es conexo si: A) Tiene al menos un ciclo. B) Todos los vértices tienen grado par. C) Existe un camino entre cualquier par de vértices. D) No contiene vértices aislados.

Un grafo k-regular cumple que: A) Todos los vértices tienen grado k. B) Tiene k vértices. C) Tiene k aristas. D) Tiene k componentes.

El número de aristas de un grafo completo 𝐾𝑛 es: A) 𝑛2. B) 𝑛(𝑛−1). C) (𝑛(𝑛−1))/2. D) 2𝑛.

Un grafo bipartido completo con particiones de tamaños m y n se denota por: A) 𝐾'𝑛. B) 𝐶'𝑛. C) 𝑃'𝑛. D) 𝐾'𝑚,𝑛.

Un grafo posee un circuito de Euler si y solo si: A) Es completo. B) Es bipartido. C) Es conexo y todos sus vértices son de grado par. D) Tiene exactamente dos vértices impares.

Un grafo con exactamente dos vértices de grado impar es: A) Euleriano. B) Hamiltoniano. C) Semi-euleriano. D) Regular.

En un dígrafo, existe un circuito dirigido de Euler si: A) El grafo es conexo. B) Todos los vértices tienen grado par. C) 𝑔𝑟𝑎+(𝑣)=𝑔𝑟𝑎−(𝑣) para todo vértice. D) Existe al menos un sumidero.

Un camino hamiltoniano es aquel que: A) Recorre todas las aristas. B) Recorre todos los vértices una sola vez. C) Recorre todas las aristas y vértices. D) Es siempre cerrado.

El Teorema de Dirac proporciona: A) Una condición necesaria. B) Una condición suficiente. C) Una condición necesaria y suficiente. D) Un algoritmo constructivo.

La longitud de un camino en un grafo ponderado es: A) El número de aristas. B) El número de vértices. C) La suma de los pesos de sus aristas. D) El peso máximo del camino.

El algoritmo de Dijkstra se utiliza para: A) Encontrar ciclos hamiltonianos. B) Determinar grafos eulerianos. C) Hallar caminos de longitud mínima. D) Calcular matrices de incidencia.

El algoritmo de Dijkstra: A) Funciona con pesos negativos. B) Solo se aplica a grafos completos. C) Construye iterativamente el conjunto S. D) Siempre encuentra ciclos mínimos.

Un multigrafo se caracteriza por: A) No tener bucles. B) No tener aristas paralelas. C) Tener dos o más aristas entre el mismo par de vértices. D) Tener todas las aristas dirigidas.

Una arista que conecta un vértice consigo mismo se denomina: A) Arista paralela. B) Camino trivial. C) Bucle. D) Circuito.

El grafo subyacente de un dígrafo es: A) El conjunto de sus arcos. B) El grafo no dirigido asociado al dígrafo. C) El grafo formado solo por vértices de grado par. D) El subgrafo inducido por sus fuentes.

Un camino trivial es aquel que: A) Tiene una sola arista. B) Tiene longitud cero. C) Es cerrado. D) Tiene al menos un ciclo.

Una cadena es: A) Un camino simple cerrado. B) Un camino elemental abierto. C) Un camino con vértices repetidos. D) Un circuito con peso mínimo.

¿Cuál de las siguientes afirmaciones es correcta?. A) Todo circuito es un ciclo. B) Todo ciclo es un circuito. C) Todo camino simple es elemental. D) Todo camino cerrado es un ciclo.

La suma de los grados de todos los vértices de un grafo no dirigido es: A) El número de aristas. B) El doble del número de aristas. C) El número de vértices. D) Siempre impar.

Un vértice aislado es aquel que: A) Tiene grado 1. B) Tiene grado par. C) Tiene grado 0. D) No pertenece a ningún ciclo.

En un dígrafo, un sumidero es un vértice con: A) Grado de entrada cero. B) Grado de salida cero. C) Grado total cero. D) Grado par.

En un grafo simple no dirigido sin bucles, la diagonal principal de la matriz de adyacencia es: A) Siempre 1. B) Siempre 2. C) Siempre 0. D) Depende del grado del vértice.

Si 𝐴 es la matriz de adyacencia de un grafo, el elemento 𝑎'𝑖𝑗 indica: A) El número de caminos de cualquier longitud. B) Si existe una arista entre 𝑣'𝑖 y 𝑣'𝑗. C) El grado de 𝑣'𝑖. D) El número de componentes.

La matriz de incidencia de un grafo simple no dirigido tiene en cada columna: A) Un único 1. B) Dos unos. C) Tres unos. D) Un número variable de unos.

El número de componentes conexas de un grafo G se denota por: A) |G|. B) c(G). C) k(G). D) deg(G).

Un dígrafo es conexo si: A) Tiene un circuito dirigido. B) Su grafo subyacente es conexo. C) Tiene exactamente una fuente. D) Todos los vértices tienen el mismo grado.

Un grafo regular de grado k cumple: A) 𝑘∣𝑉∣=∣𝐸∣. B) 𝑘∣𝑉∣=2∣𝐸∣. C) ∣𝑉∣=2∣𝐸∣. D) ∣𝐸∣=𝑘.

El grado de cada vértice en un grafo completo 𝐾𝑛 es: A) n. B) n − 1. C) n − 2. D) 2n.

Un grafo bipartido no puede contener: A) Caminos. B) Ciclos pares. C) Ciclos impares. D) Aristas múltiples.

Un camino de Euler: A) Recorre todos los vértices. B) Recorre todas las aristas una sola vez. C) Recorre todos los ciclos. D) Es necesariamente cerrado.

Un grafo euleriano: A) Puede tener vértices de grado impar. B) Tiene exactamente dos vértices impares. C) Tiene todos los vértices de grado par. D) No puede ser conexo.

El problema de los puentes de Königsberg no tiene solución porque: A) El grafo no es completo. B) Tiene demasiadas aristas. C) Todos sus vértices son de grado impar. D) No tiene ciclos.

Un ciclo hamiltoniano: A) Recorre todas las aristas. B) Recorre todos los vértices exactamente una vez. C) Recorre todos los vértices al menos una vez. D) Puede repetir vértices.

El teorema de Dirac se aplica a: A) Grafos dirigidos. B) Multigrafos. C) Grafos simples. D) Grafos ponderados.

El problema del viajante consiste en: A) Encontrar el camino más corto entre dos vértices. B) Encontrar un circuito de peso mínimo que visite todos los vértices. C) Determinar si un grafo es euleriano. D) Calcular el grado de cada vértice.

El algoritmo de Dijkstra finaliza cuando: A) Se visitan todos los vértices. B) No quedan aristas. C) El vértice destino pertenece al conjunto S. D) Se forma un ciclo.

Dijkstra no es aplicable cuando: A) El grafo es conexo. B) El grafo es ponderado. C) Existen pesos negativos. D) El grafo es simple.