|
Programa:
Valida como:
curso de postgrado en ingeniería y
en matemática, materia tipo A' para la licenciatura en
matemática, como curso de actualización para ingenieros y
como optativa para ingeniería en computación.
Responsable de la asignatura: Eduardo
A. Canale
Instituto: IMERL
Fecha de inicio y finalización:15
/3/2007 al 30/6/2007
Lugar: Salón de seminarios del IMERL
Horas Presenciales: 48 Nº de
Créditos: 10
Cupos:
Si
hubieren menos de 5 alumnos, las clases se dictarán en la
modalidad
de lecturas dirigidas. En caso de 6 o más, serán clases
presenciales. Máxima cantidad de alumnos 20.
Horarios: miércoles y viernes de
9:30 a 11:30, salvo el miércoles 29 de agosto que se adelanta
para el lunes 27 y el miércoles 5 de setiembre que se adelanta
para el martes 4 de setiembre
Objetivos: Aprender
las técnicas básicas de la teoría algebraica de
grafos, cuyo objetivo es estudiar la relación entre ciertos
invariantes algebraicos y las propiedades invariantes bajo
isomorfismos. En particular se estudiaran tres invariantes
fundamentales: el espectro de la matriz de adyacencia del grafo, el
polinomio cromático del grafo y el grupo de automorfismos del
grafo.
Conocimientos previos exigidos: Álgebra
lineal y teoría de grupos
Conocimientos previos recomendados: Teoría
de grafos.
Metodología de enseñanza: 23
clases
teóricas y 23 clases prácticas durante 13 semanas.
Se darán dos días por semana. Cada día
constará de un teórico de 50 minutos un descanso de 10 y
un práctico de una hora, donde se discutirán aplicaciones
del teórico correspondiente y/o tópicos adicionales. El
curso seguirá como guía el libro de Norman Biggs Algebraic
Graph Theory
complementado con artículos específicos según el
interés de los participantes, pero relacionados con el tema que
se esté dando. Se dará aproximadamente una sección
del libro de Biggs por clase.
Forma de evaluación:
Constará de un trabajo domiciliario con una defensa del mismo
más examen teórico posiblemente en forma de oral.
Temario: Se
trabajará sobre tres invariantes fundamentales de los grafos
simples no dirigidos: el espectro, el polinomio de Tutte y el grupo de
automorfismos.
Primera parte:
El espectro: definición; espectro de los grafos regulares y los
grafos linea; Ciclos y cortes; árboles recubridores; Expansiones
por determinantes; el espectro y las particiones de vértices.
Segunda parte:
Polinomios asociados: el polinomio cromático; expansions por
subgrafos. Expansiones multiplicativas; el polinomio de Tutte.
Tercera parte
Simetría y regularidad. Automorfismos de grafos. Grafos
vértice-transitivos. Grafos simétricos. Cubrimiento de
grafos. Grafos distancia transitivos. Grafos regulares mínimos
con un girth
dado.
Bibliografía:
1 Algebraic Graph Theory- Norman Biggs- ISBN 0 521
45897 8 -1996
2 Algebraic Graph Theory- Chris Godsil, Gordon Royle -
ISBN 0 387 95220 9 - 2001
3 Spectra of Graphs Theory and application- Cvetkovic,
Dragos M.; Doob, Michael; Sachs, Horst - ISBN 0 12 195150 2 - 1979
|