Presentación del grupo 4300 - 2009-2.

Digráficas

Prerrequisitos: No se necesitan conocimientos previos, es conveniente que tengan conocimientos generales de los tres primeros semestres del tronco común, en particular de Álgebra Superior I y II y de Álgebra Lineal I. Es muy recomendable que hayan tomado el curso de Teoría de Gráficas o el de Gráficas y Juegos, aunque no es necesario.

Evaluación: Se hará mediante tareas y exposiciones de temas a repartir, pueden ser de libros o artículos.

Bibliografía: El curso no está basado en un solo libro, la siguiente es una lista de los libros que revisaremos parcialmenteo o de algunos libros que pueden servir de apoyo o referencia.

1. Aldous, J. M., Wilson, R. J. Graphs and Applications. An Introductory Approach. The Open University
2. Bang-Jensen, J., Gutin, G. Digraphs: Theory, Algorithms and Applications. Springer-Verlag.
3. Bondy, J. A., Murty, R. Graph Theory. Springer-Verlag.
4. Bondy, J. A., Murty, R. Graph Theory with Applications. North-Holland.
5. Chartrand, G., Lesniak, L. Graphs & Digraphs, Fourth Edition. Chapman & Hall.
6. Diestel, R. Graph Theory, 3rd Edition. Springer.

Temas propuestos:

Introducción.
Definiciones básicas.
Caminos dirigidos. Ciclos Dirigidos.
Orientaciones.
Conexidad fuerte y Unilateralidad.
Distancias. Trayectorias máximas y mínimas en una digráfica.
Matrices de incidencia y adyacencia. Número de caminos dirigidos en una digráfica.

Algunas clases de digráficas.
Torneos.
Diráficas de comparabilidad. Transitivas y cuasitransitivas.
Digraficas localmente semicompletas.

Dominación, independencia y absorbencia.
Reyes.
Núcleos.
Seminúcleos.
(k,l)-núcleos.
Núcleos por trayectorias dirigidas monocromáticas.

Redes.
Flujos.
Teorema del Flujo máximo-Corte mínimo.
Coloración de mapas y flujos.
Teorema de Menger.

Algunas aplicaciones.
Tambores rotatorios.
Calles de un solo sentido.
Asignación de lugares (ranking) a los participantes de un torneo.
Modelos para redes sociales.
Dinámica simbólica.
Algoritmos en digráficas.
Algunos juegos sobre digráficas.

Este es un temario tentativo y se puede modificar el orden y los contenidos deacuerdo a los intereses del grupo.