Guía del curso
Descripción I Programa y contenido I Bibliografía

Programa y contenido

Capítulo I. Grafos. Nociones básicas.

1.1        Introducción.
1.2        Definiciones y ejemplos.
1.3        Tipos de grafos.
1.4        Representación de grafos. Matriz de incidencia. Matriz de adyacencia.
1.5        Representación de grafos en el ordenador.
1.6        Conectividad. Componentes conexas. Vértice y aristas de corte. 

Capítulo II. Grafos y algoritmos

2.1        Complejidad de un algoritmo.
2.2        NP-completitud.
2.3        Algoritmos de ordenación.
2.4        Algoritmos de búsqueda.
2.5        Algoritmo voraz.

Capítulo III. Árboles

3.1        Árboles. Árboles enraizados.
3.2        Algoritmo de búsqueda en profundidad.
3.3        Algoritmo de búsqueda en anchura.
3.4        Algoritmos de Kruskal, Prim

Capítulo IV. Caminos y distancias

4.1        Distancia en grafos. Distancia en grafos ponderados.
4.2        Algoritmo del camino crítico.
4.3        El problema del cartero. Grafos eulerianos. Digrafos eulerianos.
4.4        El problema del viajante. Grafos hamiltonianos.

Capítulo V. Redes y flujos. Emparejamientos

5.1        Redes. Flujos y cortes.
5.2        Teorema del flujo máximo y corte mínimo.
5.3        Algoritmo de etiquetado para flujos en redes. Complejidad.
5.4        Algoritmos de emparejamiento máximo en grafos bipartitos.
5.5        Algoritmo de emparejamiento máximo en grafos en general.

Capítulo VI. Coloreo de un grafo

6.1       Coloreo vértice de un grafo. Número cromático.
6.2       Polinomio cromático.
6.3       Coloreo arista de un grafo.
6.4       El problema de los cuatro colores.
6.5       Algoritmos de coloración.

Capítulo VII. Grafos planos

9.1       Diseño de circuitos.
9.2       Grafos planos. Teorema de Kuratowski.
9.3       Algoritmos de planaridad de un grafo.