TEORIA DE GRAFS
CODI: 11863
Càrrega docent: 7,5 crèdits
Professor coordinador: Josep Fàbrega Canudas
Altres professors: Carles Padró Laimón
Objectius del curs
L'objectiu del curs és presentar els temes bàsics de la Teoria de Grafs introduint, també, algunes de les seves aplicacions a l'enginyeria elèctrica, les ciències de la computació, la investigació operativa i el disseny de xarxes d'interconnexió.
Programa
1. Introducció i conceptes bàsics: Grafs i grafs dirigits, visió històrica, el problema de la reconstrucció.
2. Camins, circuits i cicles: Grafs eulerians, descomposició en cicles, grafs hamiltonians.
3. Arbres i arbres generadors: Caracterització dels arbres, arbres generadors, arbres generadors de pes mínim.
4. Cicles i cicles fonamentals: Cicles i talls fonamentals, subspais de cicles i de talls, aplicació a l'anàlisi de xarxes elèctriques.
5. Grafs planaris: La fórmula d'Euler, el Teorema de Kuratowski, grafs i superfícies.
6. Fluxos i connectivitat: Xarxes de transport, el Teorema de Ford i Fulkerson, els Teoremes de Menger.
7. Aparellaments: Problemes d'assignació, aparellaments en grafs bipartits, el Teorema de Hall.
8. Representació matricial de grafs: Matriu d'adjacència, espectre d'un graf, aplicació al Problema (
D,D).9. Coloració de grafs: Nombre cromàtic, polinomi cromàtic, índex cromàtic, el teorema dels quatre colors.
10. Grafs i grups: Grup d'automorfismes, diagrames de Cayley, el Teorema de Frucht, aplicació a les xarxes de permutacions.
Coneixements previs necessaris
Àlgebra Lineal i Càlcul 1.
Avaluació
El 50% de l'avaluació s'obtindrà per mitjà d'una prova escrita i de l'avaluació de treballs d'aplicació. El 50% restant s'obtindrà d'un examen final de l'assignatura.
Bibliografia
Referències bàsiques:
• Bollobás, B.: Graph Theory. Ed. Sringer verlag, 1979.
• Biggs, N.: Algebraic Graph Theory. Ed. Cambridge University Press, 1974.
• Chartrand, G.; Lesniak, L.: Graphs and Digraphs. Ed. Wadsworth & Brooks, 1986.
• Comellas, F.; Fàbrega, J.; Sànchez, A. i Serra, O.: Matemàtica Discreta. Ed. UPC, 1994.
• Diestel R.; Graph Theory, Ed. Springer Verlag, 1997.
Referències complementàries:
• Beineke, L.W. & Wison, R.J. (editors): Applications of Graph Theory. Ed. Academic Press, 1979.
• Beineke, L.W. & Wison, R.J. (editors): Selected Topics in Graph Theory I i II. Ed. Academic
Press, 1983.
• Biggs, N.; Lloyd, E.K. and Wilson, R.J.: Graph Theory 1736-1936. Ed. Clarendon Press, London, 1976.
• Harary, F.: Graph Theory. Ed. Addison-Wesley, 1972.
• Lovász, L.; Combinatorial Problems and Exercises, Ed. North Holland, 1993.