Test Tema 9: Teoría de grafos

Este test está basado en las 15 preguntas del cuestionario del tema. Tiene una sola respuesta correcta por pregunta. Selecciona tus respuestas y pulsa Comprobar respuestas para conocer tu nota, ver la explicación rápida de cada pregunta y consultar al final las soluciones explicadas paso a paso.

Cómo estudiar

Haz primero el test sin mirar las soluciones. Al corregirlo, lee la explicación rápida de cada pregunta y, si necesitas profundizar, despliega la explicación detallada paso a paso al final de la página.

0 de 15 respondidas ¡Empieza cuando quieras!

1. ¿Cuál de las siguientes afirmaciones describe correctamente un grafo?

A. Un grafo es un conjunto de vértices y un conjunto de aristas que conectan pares de vértices. B. Un grafo es un conjunto de vértices que están todos conectados entre sí por aristas. C. Un grafo es un conjunto de aristas sin vértices. D. Un grafo es un conjunto de vértices conectados en un ciclo cerrado.

2. ¿Qué es un vértice en el contexto de un grafo?

A. Un punto donde se encuentran varias aristas. B. Una línea que conecta dos puntos. C. Un conjunto de líneas paralelas. D. Una relación de vecindad entre dos puntos.

3. ¿Cuál de las siguientes propiedades describe correctamente un grafo completo?

A. Un grafo donde todos los vértices están conectados entre sí por una arista única. B. Un grafo que no tiene ciclos. C. Un grafo que tiene al menos un ciclo. D. Un grafo donde cada vértice tiene al menos una arista conectada.

4. ¿Qué es la relación de vecindad en un grafo?

A. La relación que existe entre dos vértices si están conectados por una arista. B. La relación que existe entre un vértice y todas las aristas del grafo. C. La relación entre dos vértices que no están conectados por una arista. D. La relación que existe entre un vértice y el grafo completo.

5. ¿Cuál de las siguientes afirmaciones describe correctamente el grado de un vértice en un grafo?

A. El número de vértices adyacentes a ese vértice. B. El número de aristas que inciden en ese vértice. C. El número total de vértices en el grafo. D. El número total de aristas en el grafo.

6. ¿Cuál de las siguientes afirmaciones describe correctamente un grafo bipartito?

A. Todos los vértices están conectados entre sí por una arista única. B. Puede dividirse en dos conjuntos disjuntos de vértices, sin aristas entre vértices del mismo conjunto. C. Es un grafo que no tiene ciclos. D. Es un grafo que tiene al menos un ciclo.

7. ¿Cuál de los siguientes grafos es siempre bipartito?

A. Un grafo completo. B. Un grafo cíclico de longitud impar. C. Un árbol. D. Un grafo dirigido.

8. ¿Cuál es una propiedad clave de los grafos bipartitos?

A. Todos los ciclos en un grafo bipartito tienen longitud impar. B. Todos los ciclos en un grafo bipartito tienen longitud par. C. Un grafo bipartito tiene vértices de grado impar. D. Un grafo bipartito no tiene vértices de grado par.

9. ¿Cuál es una condición necesaria y suficiente para que un grafo sea bipartito?

A. El grafo debe tener al menos un ciclo. B. El grafo no debe tener ciclos. C. El grafo no debe tener ciclos de longitud impar. D. El grafo debe ser dirigido.

10. Dado V = {A, B, C, D, E, F} y E = {(A,D), (A,E), (B,D), (C,F)}, ¿es bipartito el grafo definido por (V, E)?

A. No, porque tiene vértices que no están conectados. B. Sí, porque se puede dividir en dos conjuntos disjuntos sin aristas entre vértices del mismo conjunto. C. No, porque tiene ciclos de longitud impar. D. Sí, porque todos los vértices están conectados por aristas.

11. ¿Cuál de las siguientes afirmaciones describe correctamente un grafo plano?

A. Puede dibujarse en el plano de manera que sus aristas no se crucen. B. Tiene un ciclo cerrado. C. Cada vértice tiene al menos dos aristas. D. Puede dividirse en dos conjuntos disjuntos de vértices.

12. ¿Cuál es una propiedad clave de los grafos planos en términos de la fórmula de Euler?

A. V − E + F = 2, donde V es el número de vértices, E el de aristas y F el de caras. B. V + E + F = 2. C. V × E = F. D. V + E − F = 2.

13. ¿Cuál de las siguientes afirmaciones describe correctamente un camino en un grafo?

A. Una secuencia de vértices en la que cada par consecutivo está conectado por una arista. B. Un conjunto de aristas que conectan todos los vértices del grafo. C. Un ciclo que no tiene vértices repetidos. D. Un grafo en el que todas las aristas están conectadas a un solo vértice.

14. ¿Qué es un ciclo en el contexto de un grafo?

A. Un camino que comienza y termina en el mismo vértice y no repite ninguna arista. B. Un camino que no repite ningún vértice. C. Un conjunto de aristas que forman una línea recta. D. Un grafo donde todos los vértices tienen el mismo grado.

15. ¿Cuál de las siguientes aplicaciones es un ejemplo de uso de grafos planos en informática?

A. Optimización de redes eléctricas. B. Diseño de circuitos integrados. C. Análisis de redes sociales. D. Algoritmos de búsqueda en Internet.

Comprobar respuestas Reiniciar test

Soluciones explicadas: aprende pregunta por pregunta

1. Respuesta correcta: A — Definición matemática de grafo

Un **grafo** $G$ es un par ordenado $G = (V, E)$ compuesto por: - $V$: Un conjunto no vacío de **vértices** o nodos. - $E$: Un conjunto de **aristas** o enlaces, donde cada arista relaciona un par de vértices de $V$. **Aclaraciones:** - No todos los vértices deben estar conectados (pueden existir vértices aislados de grado 0). - No requiere ser un grafo completo ($K_n$) ni estructurarse obligatoriamente como ciclo.

2. Respuesta correcta: A — Vértices o nodos

Un **vértice** es la unidad o punto fundamental del conjunto $V$. - Es el elemento abstracto sobre el que inciden o donde concurren las aristas del grafo. - La línea o conexión entre dos vértices se denomina **arista**.

3. Respuesta correcta: A — Grafo Completo K_n

Un **grafo completo** (denotado $K_n$) es un grafo simple con $n$ vértices en el que **existe una arista única conectando cada par distinto de vértices**. El número total de aristas en un grafo completo de $n$ vértices viene dado por la fórmula combinatoria: \[ |E| = \binom{n}{2} = \frac{n(n-1)}{2} \]

4. Respuesta correcta: A — Adyacencia y Vecindad

En un grafo $G = (V, E)$, dos vértices $u, v \in V$ son **adyacentes** (o **vecinos**) si existe una arista $e = \{u, v\} \in E$ que los conecta directamente. El conjunto vecindario de un vértice $u$, denotado $N(u)$, agrupa a todos sus vértices adyacentes: \[ N(u) = \{v \in V \mid \{u, v\} \in E\} \]

5. Respuesta correcta: B — Grado de un vértice

El **grado** de un vértice $v$, denotado $\operatorname{deg}(v)$, es el número de aristas que inciden en él. **Teorema del Apretón de Manos (Handshaking Lemma):** En todo grafo no dirigido, la suma de los grados de todos sus vértices equivale exactamente al doble del número total de aristas: \[ \sum_{v \in V} \operatorname{deg}(v) = 2|E| \] *(Un bucle o lazo sobre un mismo vértice suma +2 a su grado).*

6. Respuesta correcta: B — Estructura de un Grafo Bipartito

Un grafo $G = (V, E)$ es **bipartito** si su conjunto de vértices $V$ puede dividirse en dos subconjuntos disjuntos $V_1$ y $V_2$ ($V = V_1 \cup V_2$ con $V_1 \cap V_2 = \emptyset$) tales que: - Toda arista $e = \{u, v\} \in E$ tiene un extremo en $V_1$ y el otro en $V_2$. - No existen aristas conectando dos vértices pertenecientes al mismo subconjunto.

7. Respuesta correcta: C — Árboles como grafos bipartitos

Un **árbol** es un grafo conexo y acíclico. - Al no contener ciclos de ningún tipo (y en particular, carecer de ciclos de longitud impar), por el **Teorema de Kőnig** todo árbol es **garantizadamente bipartito**. - La partición se puede construir fácilmente asignando los vértices según si su distancia a la raíz es par ($V_1$) o impar ($V_2$).

8. Respuesta correcta: B — Longitud de ciclos en grafos bipartitos

En cualquier grafo bipartito, para partir de un vértice $u \in V_1$, recorrer un camino cerrado y regresar al mismo $u$, se requiere alternar obligatoriamente entre los subconjuntos de la partición: \[ V_1 \to V_2 \to V_1 \to V_2 \to \dots \to V_1 \] Este recorrido alternado exige realizar un número par de transiciones. Por consiguiente, **todos los ciclos en un grafo bipartito tienen longitud par**.

9. Respuesta correcta: C — Teorema de Kőnig para bipartición

El **Teorema de Kőnig** (1916) establece la condición necesaria y suficiente para los grafos bipartitos: \[ G \text{ es bipartito} \iff G \text{ no contiene ningún ciclo de longitud impar.} \] Pueden existir ciclos en un grafo bipartito siempre que todos ellos sean de longitud par (por ejemplo, el ciclo $C_4$).

10. Respuesta correcta: B — Verificación de partición bipartita

Dado $V = \{A, B, C, D, E, F\}$ y $E = \{(A,D), (A,E), (B,D), (C,F)\}$: - Si definimos $V_1 = \{A, B, C\}$ y $V_2 = \{D, E, F\}$: - Arista $(A,D)$: une $A \in V_1$ con $D \in V_2$. - Arista $(A,E)$: une $A \in V_1$ con $E \in V_2$. - Arista $(B,D)$: une $B \in V_1$ con $D \in V_2$. - Arista $(C,F)$: une $C \in V_1$ con $F \in V_2$. Como ninguna arista une elementos de $V_1$ entre sí ni de $V_2$ entre sí, el grafo es **bipartito**.

11. Respuesta correcta: A — Definición de Grafo Plano

Un grafo es **plano** si es isomórfico a un grafo dibujado en el plano euclídeo de forma que sus aristas no se crucen (sus únicas intersecciones se producen en sus vértices incidentes comunes). **Teorema de Kuratowski:** Un grafo es plano si y solo si no contiene ningún subgrafo homeomorphic a $K_5$ (grafo completo de 5 vértices) o a $K_{3,3}$ (grafo bipartito completo de 3+3 vértices).

12. Respuesta correcta: A — Fórmula de Euler para grafos planos

Para todo grafo plano y conexo con $V$ vértices, $E$ aristas y $F$ caras (incluyendo la región exterior no acotada), se verifica la **Fórmula de Euler**: \[ V - E + F = 2 \] *Ejemplo:* Para $K_3$ (un triángulo): $V = 3$, $E = 3$, $F = 2$ (interior y exterior) $\implies 3 - 3 + 2 = 2$.

13. Respuesta correcta: A — Definición de camino

Un **camino** en un grafo $G = (V, E)$ es una secuencia alternada de vértices $v_0, v_1, \dots, v_k$ tal que para todo $i \in \{0, \dots, k-1\}$, el par $\{v_i, v_{i+1}\} \in E$. - La **longitud del camino** es el número de aristas $k$ que lo componen. - Si no se repite ningún vértice, el camino se denomina **camino simple**.

14. Respuesta correcta: A — Definición de ciclo

Un **ciclo** es un camino cerrado de longitud $k \ge 1$ donde: - El vértice de inicio coincide con el vértice final ($v_0 = v_k$). - No se repite ninguna arista en su recorrido. - Si además todos los vértices intermedios $v_0, v_1, \dots, v_{k-1}$ son distintos entre sí, se trata de un **ciclo simple**.

15. Respuesta correcta: B — Aplicación de planaridad en VLSI

En ingeniería informática y diseño de microchips (**VLSI** - Very Large Scale Integration): - El trazado de pistas conductoras sobre una capa dieléctrica de una placa de circuito impreso (PCB) no puede tener cruces físicos directos para evitar cortocircuitos. - La teoría de **grafos planos** permite verificar algorítmicamente si un circuito se puede implementar en una sola capa o requiere múltiples capas mediante "vías".

---

Chuleta final: lo imprescindible para aprobar

1. Elementos de un grafo G = (V, E)

• Vértices (\(V\)): Nodos del grafo. \(|V| = n\).
• Aristas (\(E\)): Conexiones entre pares de vértices. \(|E| = m\).
• Adyacencia: Dos vértices unidos por una arista.
• Grado (\(\operatorname{deg}(v)\)): Número de aristas incidentes en \(v\).
• Lema del Apretón de Manos: \(\sum_{v \in V} \operatorname{deg}(v) = 2|E|\).

2. Tipos de grafos especiales

• Grafo Completo (\(K_n\)): Todas las aristas posibles están presentes. \(|E| = \frac{n(n-1)}{2}\).
• Grafo Bipartito: \(V = V_1 \cup V_2\) sin aristas internas en \(V_1\) ni en \(V_2\).
• Grafo Bipartito Completo (\(K_{m,n}\)): Todos los nodos de \(V_1\) (\(m\)) conectados a todos los de \(V_2\) (\(n\)). Total aristas: \(m \cdot n\).
• Árbol: Grafo conexo y acíclico (\(|E| = |V| - 1\)). Siempre es bipartito.

3. Teoremas de Bipartición y Planaridad

Teorema / Regla	Concepto
Teorema de Kőnig	\(G\) es bipartito \(\iff\) NO tiene ciclos impares (todos son de longitud par).
Grafo Plano	Se puede dibujar en el plano sin cruces de aristas.
Fórmula de Euler	En grafos planos conexos: \(V - E + F = 2\) (\(F\) incluye la cara exterior).
Kuratowski	\(G\) es plano \(\iff\) no contiene subgrafos no planos homomorfos a \(K_5\) o \(K_{3,3}\).

4. Recorridos

• Camino: Secuencia de vértices conectados por aristas.
• Ciclo: Camino cerrado (\(v_0 = v_k\)) sin repetir aristas.