TEORÍA DE GRAFOS
| Código | Plan | Tipo | Curso/s | Cuatrim. | Créditos | |||||
|---|---|---|---|---|---|---|---|---|---|---|
| Teóric. | Práctic. | Clínic. | Problem. | Total | ECTS | |||||
| Curso/s: 0 = Complementos de formación; P = Proyecto fin de carrera; El 1er curso de una titulación de solo 2º ciclo será 1º Tipo de asignatura: Tr = Troncal; Ob = Obligatoria; Op = Optativa; Le = Libre Elección | ||||||||||
| 0702013 | 1997 | Op | 2º | Primero | 3.00 | 3.00 | 0.00 | 0.00 | 6.00 | 5.00 |
| Idiomas | Español, | |||||||||
| Campus | LEON |
|---|---|
| Centro | ESCUELA DE INGENIERIAS INDUSTRIAL E INFORMATICA |
| Titulación | Ingeniería Informática |
| Departamento |
Matemáticas |
| Area |
Matemática Aplicada |
| Nombre de la asignatura en inglés: | GRAPH THEORY |
| Contenido | Grafos. Planaridad y coloración. Circuitos y flujo de redes. |
| Contenido en inglés | Graphs. Planarity and colouring. Cicles and network flows. |
| Profesorado | ||||
|---|---|---|---|---|
| Apellidos/Nombre | Situación | Teoría | Práctica | |
| JAVIER GÓMEZ PÉREZ | jgomp@unileon.es | Responsable | SI | SI |
| Tutorías: Martes y miércoles de 11:00 a 13:00. Jueves de 10:00 a 12:00. | ||||
| MARÍA JESÚS PISABARRO MANTECA | mjpism@unileon.es | Resp. Suplente | SI | SI |
| Información Académica |
|---|
| Objetivos de la asignatura |
|
Uno de los aspectos más importantes de la Teoría de Grafos radica en la relevancia que esta materia tiene en la fundamentación matemática de las Ciencias de la Computación, así como en otras disciplinas. Muchos fenómenos discretos pueden modelizarse mediante el uso de la Teoría de Grafos. Además, son de gran importancia para la comprensión de estructuras de datos y en el análisis de Algoritmos. Este curso tiene varios objetivos bien determinados. En primer lugar, establecer una notación que seguiremos durante el curso debido a la falta de homogeneidad en este sentido con respecto a esta materia. Simultáneamente, haremos uso de los conceptos y términos sobre Teoría de Grafos intentando encontrar las relaciones entre estos términos y algunos problemas que se puedan resolver mediante el uso de grafos. En todo momento tendremos en cuenta de forma especial en los aspectos algorítmicos que tiene esta asignatura. One of the most important aspects of the Graph Theory is in the relevance that this subject has in the mathematical foundation as well in Computer Science as in other subjects. Many discreet phenomena can be modelled by means of the use of Graph Theory. Moreover, they have a very important role for the meaning of data structures and algorithms analysis. This course has many well determined objectives. First all, we establish the notation we follow all along the semester due to the lack of homogeneity in this sense on this subject. We shall, simultaneously, make use of the concepts and terms of Graph Theory by trying to find the relationship between those and some problems which can be solved by using a graph. We shall specially consider at any moment the algorithmic point of view that this subject has. |
| Programa temario |
|
TEMA 1. INTRODUCCIÓN A LOS GRAFOS: Los puentes de Königsberg. Distribución de casas y servicios. Los cubos mágicos. TEMA 2. GRAFOS. CONCEPTOS BASICOS: Algunos conceptos sobre grafos. Ejemplos de grafos. El grado: propiedades. Representación matricial de Grafos: Matrices de adyacencia y de incidencia. TEMA 3. TRAYECTORIAS Y CIRCUITOS. GRAFOS EULERIANOS Y GRAFOS HAMILTONIANOS: Algunas definiciones. Conexión y distancia en grafos. Optimización en grafos: Algoritmo de Dijkstra. Vulnerabilidad en grafo: Redes fiables y Teorema de Menger. Grafos eulerianos. Grafos Hamiltonianos. Aplicaciones. TEMA 4. ÁRBOLES: Árboles. Primeras propiedades. Enumeración de árboles. El problema del conector mínimo. Arboles raíz. TEMA 5. PLANARIDAD: Inmersión de grafos. Curvas de Jordan. La fórmula de Euler. Caracterización de los grafos planares. Sólidos platónicos. Inmersión de Grafos en superficies. Grafos duales. Aplicaciones de la planaridad. TEMA 6. COLORACIÓN: Coloreado de vértices: el número cromático. Coloreado de mapas. Coloreado de aristas. Polinomios cromáticos. Notas sobre el Teorema de los cuatro colores. Aplicaciones de la coloración. TEMA 7. DIGRAFOS: Definición y conceptos iniciales. Grados en Digrafos. Conexión. Digrafos Eulerianos y Hamiltonianos. Torneos. Representación matricial de Digrafos. TEMA 8. FLUJO DE REDES: Redes básicas. Optimización en redes: Algoritmo de Dijstra. Trayectorias de aumento de flujo. Teorema del flujo máximo y el corte mínimo. Algoritmo del flujo máximo y el corte mínimo. Redes multifuente y multisumidero. |
| Metodología Docente |
|
La asignatura se estructura en - Clases Teóricas - Clases Prácticas de resolución de ejercicios y problemas - Resolución individualizada de problemas que se entregarán a lo largo del desarrollo de la asignatura. - Opcionalmente, elaboración de programas con implementación de algoritmos sobre grafos. |
| Procedimientos de Evaluación y criterios de corrección de exámenes |
| Se realizará un examen final escrito que podrá constar tanto de preguntas teóricas asi como de ejercicios prácticos. Los criterios de corrección se fijarán el mismo día de la prueba. Así mismo, se valorarán las actitudes que el alumno manifieste y desarrolle en el transcurso de la asignatura. A lo largo del curso se irán proponiendo ejercicios, problemas y trabajos sobre la materia estudiada para resolver independientemente o en grupos de trabajo. La entrega de estos trabajos PUEDE SER obligatoria, y la calificación de los mismos se reflejará en la nota final. |
| Otras actividades a desarrollar |
| Se propondrá, opcionalmente, la elaboración de programas, con el uso de alguno de los lenguajes habituales de programación, en los que se implementen algoritmos de utilización frecuente en el ámbito de los grafos y digrafos. |
| Bibliografía recomendada |
|
- R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, algorithms and applications, Prentice Hall, Upper Saddle River, NJ, 1993. - G. Chartrand, O. R. Oellermann, Applied and Algorithmic Graph Theory. Ed. McGraw-Hill, 1993. - G. Chartrand, L. Lesniak, Graphs and Digraphs. Ed. Chapman & Hall, 2000. - J. Gross, J. Yellen, Graph Theory and its Applications. CRC Press, 1999. - R. G. Wilson, Introducción a la Teoría de Grafos. Alianza, 1983. - D. B. West, Introduction to Graph Theory, second edition. Prentice Hall, 2001. |
| Bibliografía adicional |
|
- J. Aldous, A. Dolan, Networks and Algorithms. Wiley, 1993. - B. Bollobás, Modern Graph Theory. Springer, 1998. - J. Clark, D. Holton, A First Look at Graph Theory. World Scientific, 1991. - R. Diestel, Graph Theory. Springer, 1997. - A. Gibbons, Algorithmic Graph Theory. Cambridge Univ. Press, 1985. - W. Kocay, D. L. Kreher, Graphs, Algorithms and Optimization, Chapman & Hall/CRC, Boca Raton, FL, 2005. |
| Enlaces de interés |
|
En el aula virtual de la asignatura se aloja, periódicamente, información de utilidad. Para contactar con el profesor, puede utilizarse la dirección de correo electrónico: jgomp@unileon.es. |
| Fecha ultima modificación: 20/05/2010 |