Test Tema 9 — Teoría de grafos

Test interactivo para repasar conceptos básicos de grafos, grafos bipartitos, planaridad, caminos y ciclos. Selecciona una respuesta por pregunta y pulsa Corregir test para ver tu puntuación y las explicaciones.

Corregir test Reiniciar

Pregunta 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.

Respuesta correcta: A. Un grafo se define mediante un conjunto de vértices (o nodos) y un conjunto de aristas que conectan pares de vértices. No tiene por qué ser completo ni contener ciclos: puede tener vértices aislados o no tener ninguna arista.

Pregunta 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.

Respuesta correcta: A. Un vértice es un nodo o punto del grafo. Las líneas que unen vértices son las aristas. En un grafo puede haber vértices de grado cero, llamados aislados, que no están unidos a ninguna arista.

Pregunta 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.

Respuesta correcta: A. En un grafo completo simple, cada pareja de vértices distintos está unida por exactamente una arista. Se suele representar como Kₙ. Por ejemplo, K₃ es un triángulo.

Pregunta 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.

Respuesta correcta: A. Dos vértices son vecinos o adyacentes cuando existe una arista que los conecta directamente. No basta con que exista un camino indirecto entre ellos.

Pregunta 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.

Respuesta correcta: B. El grado de un vértice es el número de aristas que llegan a él o salen de él en un grafo no dirigido. En un grafo simple coincide con el número de vecinos. En grafos con lazos, cada lazo cuenta dos veces.

Pregunta 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.

Respuesta correcta: B. Un grafo bipartito permite separar sus vértices en dos grupos (particiones) de modo que todas las aristas conectan un vértice de un grupo con uno del otro. No puede haber aristas dentro de una misma partición.

Pregunta 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.

Respuesta correcta: C. Todo árbol es bipartito: basta dividir los vértices según la paridad de su distancia desde una raíz. Cada arista une niveles de distinta paridad. En cambio, un ciclo impar no es bipartito y un grafo completo solo lo es en casos pequeños (K₁ y K₂).

Pregunta 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.

Respuesta correcta: B. Al recorrer un ciclo en un grafo bipartito, se alterna entre las dos particiones. Para volver al vértice inicial hay que realizar un número par de pasos. Por eso no puede haber ciclos impares.

Pregunta 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.

Respuesta correcta: C. Un grafo (no dirigido) es bipartito si y solo si no contiene ningún ciclo impar. Puede tener ciclos: por ejemplo, un cuadrado es un ciclo de longitud 4 y sí es bipartito.

Pregunta 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.

Respuesta correcta: B. Una partición válida es {A, B, C} y {D, E, F}. Todas las aristas indicadas cruzan de un grupo al otro. Que haya vértices aislados o que el grafo no sea conexo no impide que sea bipartito.

Pregunta 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.

Respuesta correcta: A. Un grafo es plano si admite una representación en el plano en la que las aristas solo se encuentran en vértices comunes y no se cruzan en otros puntos. La definición se refiere a que exista algún dibujo sin cruces, no a que cualquier dibujo los evite.

Pregunta 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.

Respuesta correcta: A. La fórmula de Euler para un grafo plano conexo es V − E + F = 2. F cuenta también la región exterior. Por ejemplo, en un triángulo dibujado en el plano: V=3, E=3 y F=2; por tanto, 3−3+2=2.

Pregunta 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.

Respuesta correcta: A. Un camino describe cómo desplazarse por el grafo: v₀, v₁, …, vₖ, donde cada pareja consecutiva está unida por una arista. La opción B se parece más a una descripción imprecisa de una estructura que conecta todos los vértices, no a un camino.

Pregunta 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.

Respuesta correcta: A. Un ciclo es un recorrido cerrado: se vuelve al vértice de partida sin repetir aristas. En la definición habitual de ciclo simple tampoco se repiten otros vértices. La opción B describe un camino simple, no necesariamente cerrado.

Pregunta 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.

Respuesta correcta: B. En el diseño de circuitos integrados es importante organizar las conexiones entre componentes evitando cruces o gestionándolos mediante capas. Los modelos de grafos planos ayudan a estudiar el diseño y el trazado de circuitos.

---

Chuleta final — Tema 9

1. Conceptos básicos de grafos

Un grafo se representa como \(G=(V,E)\):

• Vértices (V): los nodos o puntos.
• Aristas (E): las conexiones entre pares de vértices.
• Adyacentes o vecinos: dos vértices unidos directamente por una arista.
• Grado de un vértice: número de aristas que inciden en él.
• Vértice aislado: vértice de grado 0.
• Grafo completo: cada pareja de vértices distintos está conectada. Se denota \(K_n\).

2. Grafos bipartitos

Un grafo es bipartito si sus vértices se pueden dividir en dos conjuntos disjuntos \(V_1\) y \(V_2\), de forma que todas las aristas conectan un vértice de \(V_1\) con uno de \(V_2\).

• No hay aristas entre vértices de la misma partición.
• Todo árbol es bipartito.
• Un grafo es bipartito si y solo si no contiene ciclos impares.
• Por tanto, todos sus ciclos tienen longitud par.
• No hace falta que el grafo sea conexo: puede tener componentes separadas y vértices aislados.

Truco: bipartito = dos grupos; las aristas siempre cruzan de un grupo al otro.

3. Grafos planos y fórmula de Euler

Un grafo es plano si puede dibujarse sin cruces de aristas (salvo en los vértices donde se unen).

Para un grafo plano conexo:

\[ V-E+F=2 \]

• \(V\): número de vértices.
• \(E\): número de aristas.
• \(F\): número de caras, incluida la región exterior.

Ejemplo: un triángulo tiene 3 vértices, 3 aristas y 2 caras. Así, \(3-3+2=2\).

Aplicación informática: diseño y trazado de circuitos integrados.

4. Caminos y ciclos

• Camino: secuencia de vértices consecutivos unidos por aristas.
• Camino cerrado: empieza y termina en el mismo vértice.
• Ciclo: recorrido cerrado que no repite aristas; en un ciclo simple tampoco repite vértices salvo el inicial/final.

5. Resumen para memorizar

Concepto	Palabra clave
Grafo	Vértices + aristas
Vértice	Nodo
Arista	Conexión
Vecinos	Conectados directamente
Grado	Aristas incidentes
Completo	Todos con todos
Bipartito	Dos grupos, aristas cruzadas
Árbol	Siempre bipartito
Ciclo impar	Impide ser bipartito
Plano	Se puede dibujar sin cruces
Euler	\(V-E+F=2\)
Camino	Recorrido por aristas
Ciclo	Recorrido cerrado

6. Errores típicos de examen

• Un grafo no tiene por qué ser conexo ni tener ciclos.
• Un grafo completo exige conexión entre cada pareja de vértices distintos.
• Un vértice aislado no impide que el grafo sea bipartito.
• Un árbol siempre es bipartito, aunque tenga muchos vértices.
• Un grafo bipartito puede tener ciclos, pero todos son pares.
• La fórmula de Euler indicada se aplica a grafos planos conexos y cuenta también la cara exterior.
• Un dibujo con cruces no demuestra que el grafo no sea plano: puede existir otra representación sin cruces.