Examen UD5 — Teoría de grafos
Duración estimada: 60 minutos. Lee con atención y marca la(s) respuesta(s) correcta(s). Algunas preguntas pueden tener más de una respuesta válida.
Instrucciones
- Responde marcando la opción correcta (a, b, c, d). Puede haber más de una correcta: marca todas las que correspondan.
- En las preguntas de cálculo se pide elegir la(s) opción(es) correcta(s); debajo de cada pregunta se incluye la solución desarrollada para estudiar.
Pregunta 2
Sea \(G\) un grafo no dirigido conexo. ¿Cuál(es) condición(es) garantizan que \(G\) tiene un ciclo euleriano?
Pregunta 3
Sea \(G\) un grafo no dirigido conexo con exactamente dos vértices de grado impar. ¿Qué se puede afirmar?
Pregunta 4
Aplicando Dirac: si \(G\) es simple con \(n=10\) vértices y grado mínimo \(\delta(G)=5\), ¿qué se puede afirmar?
Pregunta 6
Sea un grafo simple con matriz de adyacencia \(A\). ¿Cuál(es) afirmación(es) es/son correcta(s)?
Pregunta 7
En un grafo no dirigido con matriz de adyacencia \(A\), ¿qué representa el elemento \((A^2)_{ij}\)?
Pregunta 9
Considera el grafo ponderado con vértices \(\{A,B,C,D\}\) y aristas (no dirigidas) con pesos:
¿Cuál es el peso total de un árbol de expansión mínima (MST)?
Pregunta 10
En el mismo grafo ponderado (aristas no dirigidas) con \(AB=1,\; AC=4,\; BC=2,\; BD=6,\; CD=3\), ¿cuál es la distancia mínima de \(A\) a \(D\)?
Pregunta 11
En un recorrido BFS (búsqueda en anchura) en un grafo no ponderado, ¿qué propiedad garantiza respecto a un vértice origen \(s\)?
Los resultados del cuestionario se guardan en el almacenamiento local de tu navegador y persistirán entre sesiones.
Progreso del cuestionario
0 / 0 preguntas respondidas (0%)
0 correctas
Soluciones desarrolladas
Solución pregunta 1 — Aristas de K_9
En un grafo completo \(K_n\) cada par de vértices forma una arista. Por tanto
Para \(n=9\):
Solución pregunta 2 — Ciclo euleriano
Teorema de Euler (grafos no dirigidos): un grafo conexo tiene ciclo euleriano si y sólo si todos sus vértices tienen grado par.
- Si exactamente dos vértices son impares, entonces hay camino euleriano abierto (no ciclo).
Solución pregunta 3 — Camino euleriano
Teorema de Euler (camino): un grafo conexo tiene un camino euleriano abierto si y sólo si tiene exactamente dos vértices de grado impar.
Solución pregunta 4 — Dirac (hamiltoniano)
Teorema de Dirac: si \(G\) es simple, \(n\ge 3\) y \(\delta(G)\ge \frac{n}{2}\), entonces \(G\) es hamiltoniano.
Aquí \(n=10\) y \(\delta(G)=5\).
Por tanto, \(G\) es hamiltoniano.
Solución pregunta 5 — Propiedades de árboles
Un árbol es un grafo conexo y sin ciclos. Además cumple la relación clásica:
Por tanto son verdaderas:
- Un árbol con \(n\) vértices tiene \(n-1\) aristas.
- Un árbol es conexo y acíclico.
Solución pregunta 6 — Matriz de adyacencia
Para un grafo no dirigido, si hay arista entre \(v_i\) y \(v_j\) entonces también entre \(v_j\) y \(v_i\), así \(A_{ij}=A_{ji}\) y la matriz es simétrica.
En un grafo sin lazos, no hay aristas \(v_i\to v_i\), por tanto \(A_{ii}=0\) para todo \(i\) (diagonal nula).
Además, la suma de la fila \(i\) da el grado de \(v_i\), no el número total de aristas del grafo.
Solución pregunta 7 — Interpretación de (A^2)_{ij}
Se tiene:
Cada término \(A_{ik}A_{kj}\) cuenta un paso \(i\to k\) y otro \(k\to j\); al sumar en \(k\) contamos todos los caminos (walks) de longitud 2 de \(v_i\) a \(v_j\).
Solución pregunta 8 — Bipartitos
Un grafo es bipartito si y sólo si no contiene ciclos de longitud impar.
- Si hay un ciclo impar, no se puede 2-colorear.
- Si no hay ciclos impares, existe una partición (por niveles BFS) que lo 2-colorea.
Solución pregunta 9 — MST
Ordenamos aristas por peso: \(AB(1)\), \(BC(2)\), \(CD(3)\), \(AC(4)\), \(BD(6)\).
Aplicando Kruskal:
- Tomamos \(AB(1)\).
- Tomamos \(BC(2)\) (no forma ciclo con \(AB\)).
- Tomamos \(CD(3)\) (conecta \(D\) sin formar ciclo).
Ya tenemos \(n-1=3\) aristas y el grafo es conexo, por tanto es un MST.
Peso total:
Solución pregunta 10 — Dijkstra (distancia mínima)
Calculamos rutas de \(A\) a \(D\):
- \(A\to C\to D\): \(4+3=7\).
- \(A\to B\to D\): \(1+6=7\).
- \(A\to B\to C\to D\): \(1+2+3=6\).
La menor es 6.
Solución pregunta 11 — BFS
BFS explora el grafo por capas: primero todos los vértices a distancia 1 (en aristas) del origen, luego los de distancia 2, etc.
Por eso devuelve distancias mínimas en número de aristas en grafos no ponderados.
Solución pregunta 12 — Dijkstra
Dijkstra es correcto cuando todos los pesos son no negativos; si hay un peso negativo puede fijar un nodo como “definitivo” demasiado pronto.
También es común implementarlo con una cola de prioridad para extraer el vértice con menor distancia provisional.