En la ventana de impresión, elige «Guardar como PDF» para conservar una copia en tu dispositivo.
1Fórmulas y métodos
Teoría de grafos
Lema del apretón de manos
Σ deg(v) = 2|E|
Grafos completos
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Grafo regular
|E| = n·k/2
Árbol y bosque
|E| = n − 1, |E| = n − c
Hojas de un árbol
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
circuito: todos los grados pares; camino: exactamente 2 grados impares
Circuitos de Hamilton en Kn
(n − 1)!/2
Actualización de Dijkstra
d(v) = min(d(v), d(u) + w(u, v))
Recorridos de longitud L
(Mᴸ)ij
Método
Anota el grado de cada vértice; los grados suman el doble del número de aristas.
En las preguntas de Euler, comprueba que el grafo sea conexo y cuenta los vértices de grado impar.
En los árboles, usa n − 1 aristas y el lema del apretón de manos.
En Dijkstra, lleva una tabla de distancias provisionales y fija en cada ronda el vértice no fijado de menor distancia.
Para un árbol generador mínimo, ordena las aristas por peso y descarta toda arista que cierre un ciclo (Kruskal), o haz crecer un único árbol desde un vértice inicial (Prim).
2Problemas de práctica
1.Algoritmos y complejidadMedia
¿Es correcto decir que un algoritmo O(n²) también es O(n³)?
ANo, porque O grande debe dar siempre el ritmo de crecimiento exacto de la función
BSí, pero solo si n es menor que 100
CNo, porque n³ es menor que n² para n grande
DSí, porque O grande es una cota superior y n² no crece más deprisa que n³
2.Algoritmos y complejidadDifícil
¿Cuál es el tiempo de ejecución del algoritmo de Dijkstra con un montículo binario en un grafo con V vértices y E aristas?
AO(V + E)
BO((V + E) log V)
CO(V³)
DO(V × E)
3.Estructuras de datosMedia
Las claves 50, 30, 70, 20, 40 se insertan en este orden en un árbol binario de búsqueda vacío. ¿Cuál es el hijo izquierdo de 30?
A40
B70
C50
D20
4.Estructuras de datosDifícil
En el BST con raíz 50, subárbol izquierdo 30 (hijos 20, 40) y subárbol derecho 70 (hijos 60, 80), se elimina la raíz usando el sucesor en orden. ¿Qué clave pasa a ser la nueva raíz?
A60
B40
C70
D80
5.Teoría de grafosMedia
Un árbol tiene 3 vértices de grado 3, 4 vértices de grado 4, 2 vértices de grado 2, y todos sus demás vértices son hojas (grado 1). ¿Cuántas hojas, L, tiene?
3 × deg 34 × deg 42 × deg 2
L =
6.Teoría de grafosDifícil
¿Cuántos recorridos cerrados de longitud 2 empiezan y terminan en B? Un recorrido puede repetir vértices y aristas. Llama al número N.
M = matriz de adyacenciaL = 2
N =
3Disoluciones
1.Algoritmos y complejidad
Respuesta: D · Sí, porque O grande es una cota superior y n² no crece más deprisa que n³
Por qué esta es la respuesta
O grande es una cota superior, así que la afirmación es cierta pero no ajustada; Θ(n²) indica el ritmo de crecimiento exacto.
Respuesta
D · Sí, porque O grande es una cota superior y n² no crece más deprisa que n³
2.Algoritmos y complejidad
Respuesta: B · O((V + E) log V)
Por qué esta es la respuesta
Hay V operaciones extract-min y hasta E operaciones decrease-key, cada una O(log V); un montículo de Fibonacci lo mejora a O(E + V log V).
Respuesta
B · O((V + E) log V)
3.Estructuras de datos
Respuesta: D · 20
Por qué esta es la respuesta
20 es menor que 50 y menor que 30, así que pasa a ser el hijo izquierdo de 30; 40 pasa a ser su hijo derecho.
Respuesta
D · 20
4.Estructuras de datos
Respuesta: A · 60
Por qué esta es la respuesta
El nodo situado más a la izquierda del subárbol derecho es 60, así que 60 sustituye a 50 y se elimina su posición anterior; usar el predecesor daría 40.
Respuesta
A · 60
5.Teoría de grafos
Respuesta: L = 13
Euler, Hamilton y árboles: un grafo conexo tiene un circuito euleriano (cada arista una vez, volviendo al inicio) cuando todos los vértices tienen grado par, y un camino euleriano que no es un circuito cuando exactamente dos vértices tienen grado impar; entonces el camino va de un vértice impar al otro. Un circuito hamiltoniano visita cada vértice una vez; Kn tiene (n − 1)!/2 de ellos. Un árbol de n vértices tiene n − 1 aristas, y un grafo conexo con m aristas conserva un árbol generador tras quitarle m − n + 1 aristas.
Lema del apretón de manos para un árbol
L + 29 = 2(L + 9) − 2
L = 13
Respuesta
L = 13
Atajo: L = 2 + Σ (d − 2) sobre los vértices de grado d ≥ 3.
6.Teoría de grafos
Respuesta: N = 3
Grados: el grado de un vértice es el número de aristas que inciden en él. Cada arista tiene dos extremos, así que los grados suman el doble del número de aristas: Σ gr(v) = 2|E| (el lema del apretón de manos). Por tanto, el número de vértices de grado impar es par. Kn tiene n(n − 1)/2 aristas, un grafo k-regular de n vértices tiene nk/2, y un árbol de n vértices tiene n − 1 aristas.