| CURSO | SEMESTRE | CARÁCTER | ECTS |
| Primero | 2 | Obligatoria | 6 |
| GUÍA DOCENTE |
Programa |
Bibliografía |
Normas evaluación |
Profesores |
| AULA VIRTUAL | Ejercicios | Enlaces y Software | ||
Tema
1. Nociones básicas de grafos y digrafos.
-
Nociones generales. Representación de grafos y
digrafos. Matriz de adyacencia.
-
Subgrafos. Operaciones con grafos. Isomorfismo de
grafos.
-
Sucesión de grados de un grafo. Caracterización de las
sucesiones gráficas.
-
Caminos en un grafo y en un digrafo. Conexión.
Vértices-corte y aristas puente.
Tema
2. Árboles. Optimización de árboles.
-
Árboles. Árboles con raíz. Búsquedas en grafos.
Recorridos en árboles.
-
Enumeración de árboles etiquetados. Fórmula de Cayley.
Código de Prüfer.
-
Árbol generador de peso mínimo: Algoritmos de Prim,
Kruskal y Boruvka.
-
Otros criterios de optimización de árboles.
Tema
3. Distancia y caminos mínimos.
-
Distancias en grafos. Excentricidad, centro y diámetro
en un grafo.
-
Caminos críticos en grafos de actividades.
-
Caminos mínimos en grafos ponderados. Algoritmos de
Dijkstra, Bellman-Ford y Floyd.
Tema
4. Complejidad de algoritmos.
-
Notación de Knuth. Crecimiento de funciones.
-
Complejidad de algoritmos. Complejidad de problemas.
-
Análisis de la complejidad de algoritmos básicos.
- Clases P y NP de problemas. Problemas NP-completos.
Tema
5. Conectividad y orientabilidad
-
Conectividad por vértices y por aristas en un grafo.
-
Caracterización por caminos: Teorema de Whitney.
-
Orientabilidad de grafos. Caracterización de los
grafos orientables.
Tema
6. Flujos en redes. Emparejamientos.
-
Flujos y capacidades en una red. Teorema de
Ford-Fulkerson.
-
Conectividad y flujos. Teoremas de Menger.
-
Emparejamientos en grafos bipartidos. Teorema de Hall.
-
Optimización de emparejamientos: Algoritmo húngaro.
Estabilidad.
-
Emparejamientos en grafos generales.
Tema
7. Recorridos en grafos
-
Grafos eulerianos. Caracterización.
-
Algoritmos de construcción de recorridos eulerianos.
Problema del cartero.
-
Grafos hamiltonianos. Propiedades.
-
Problema del viajante. Algoritmos aproximados.
Tema
8. Planaridad
-
Grafos planos. Fórmula de Euler y consecuencias.
Poliedros regulares.
-
Teorema de Kuratowski.
-
Trazado rectilíneo de grafos planos.
Tema
9. Coloración de grafos.
-
Independencia y coloración. Número cromático de un
grafo.
-
Algoritmos de coloración de vértices. Polinomio
cromático.
-
Coloración de aristas. Otros criterios de coloración
en grafos.
-
Coloración de mapas. Teorema de los cuatro colores.
Tema
10. Funciones generatrices.
-
Funciones generatrices y problemas de recuento.
-
Series de potencias. Propiedades algebraicas.
Fracciones simples.
-
Resolución de relaciones de recurrencia por funciones
generatrices.
-
Funciones generatrices exponenciales.