## 27005 - Graphs and Combinatorics

### Syllabus Information

2018/19
Subject:
27005 - Graphs and Combinatorics
Faculty / School:
Degree:
453 - Degree in Mathematics
ECTS:
6.0
Year:
1
Semester:
Second semester
Subject Type:
Compulsory
Module:
---

### 3.1. Assessment tasks (description of tasks, marking system and assessment criteria)

For regular students two options:

a)     - Homework (Completion of four problem sets)  --- 20%  of the score.

- Final exam                                                     --- 80%  of the score.

b)     Only final exam (100%)

For non-regular students only option b).

### 4.1. Methodological overview

The methodology followed in this course is oriented towards the achievement of the learning objectives. A wide range of teaching and learning tasks are implemented, such as lectures, problem-solving sessions and tutorials.

This course is organized as follows:

• Lectures (30 hours). Two weekly sessions of 1 hour each.
• Problem-solving sessions (30 hours). Two weekly sessions of 1 hour each. Four problem sets will be assigned during the course. Material covered in exercises will be tested on exams. Typically, a problem set is due two weeks after it is assigned. By solving the problem sets a student can get 20% of the final score.
• Tutorials. The students  can attend office hours and send questions to him/her teacher via email.
• 4 additional sessions devoted to solving questions related with the homework. For these additional sessions the students are splitted into small groups.

### 4.3. Syllabus

This course covers elementary discrete mathematics. It emphasizes mathematical definitions and proofs as well as applicable methods.

This course will address the following topics:

Section I

• Topic 1.- Enumerative Combinatorics: Permutations and Combinations.
• Topic 2.- Binomial coefficients and binomial formula.
• Topic 3.- Recurrence relations. Some applications.
• Topic 4.- The inclusion-exclusion principle. Applications.

Section II

• Topic 5.- Generating Functions.
• Topic 6.- Rational Generating Functions.

Section III

• Topic 7.- Graphs: Definitions and notation.
• Topic 8.- Traversing a Graph. Algorithms  BFS and DFS.
• Topic 9.- Applications of Graph Traversal: Connected components, strong components, bases.
• Topic 10.-The number of trees and paths of a graph.

Section IV

• Topic 11.- Weighted Graphs. Algorithms for the minimum spanning tree problem.
• Topic 12.- The shortest path problem. Dijkstra’s algorithm.
• Topic 13.- PERT-CPM algorithms for scheduling a set of project activities.

Section V

• Topic 14.- Maximum flow in a network.
• Topic 15.- The Ford- Fulkerson method for calculating a maximum flow.
• Topic 16.- Menger’s theorems on connectivity of graphs.
• Topic 17.- Maximum matching in bipartite graphs. Hall’s theorem.
• Topic 18.- Some NP-Hard problems on graphs.

### 4.4. Course planning and calendar

Further information concerning the timetable, classroom, office hours, assessment dates and other details regarding this course will be provided on the first day of class or please refer to the Faculty of Sciences website and Moodle.

### 4.5. Bibliography and recommended resources

Bibliography.

Main:

Complementary books:

• Bóna, Miklós. A walk through combinatorics : an introduction to enumeration and graph theory / Miklos Bona . - 2nd ed.. Hackensack: World Scientific, 2008
• Brualdi, Richard A. : Introductory combinatorics / Richard A. Brualdi . - 5th ed. Upper Saddle River, New Jersey : Pearson Prentice Hall, cop. 2010
• Gross, Jonathan L.. Graph theory and its applications / Jonathan Gross, Jay Yellen . - 2nd ed. Boca Raton : Chapman & Hall/CRC, 2006
• Lint, Jacobus Hendricus Van. A course in combinatorics / J. H. van Lint and R. M. Wilson . - [1st Ed., 2nd. repr.] Cambridge : Cambridge University Press, 1996
• Pemmaraju, Sriram. Computational discrete mathematics : combinatorics and graph theory with mathematica / Sriram Pemmaraju, Steven Skiena . 1st publ., repr. Cambridge : Cambridge University Press, 2009
• Stanley, Richard P.. Enumerative combinatorics / Richard P. Stanley . Cambridge ; New York : Cambridge University Press, cop. 1997-1999

## 27005 - Grafos y combinatoria

### Información del Plan Docente

2018/19
Asignatura:
27005 - Grafos y combinatoria
Titulación:
Créditos:
6.0
Curso:
1
Periodo de impartición:
Segundo semestre
Clase de asignatura:
Obligatoria
Módulo:
---

### 1.1. Objetivos de la asignatura

#### La asignatura y sus resultados previstos responden a los siguientes planteamientos y objetivos:

Se trata de una asignatura de formación básica dentro del Grado de Matemáticas, y uno de los principales objetivos es que los conocimientos teóricos y las técnicas adquiridas sirvan como base para asignaturas de cursos posteriores.

Por otra parte, en la modelización, formulación, análisis y resolución de muchos problemas científicos, se requiere conocer los métodos de Teoría de Grafos y se necesitan las herramientas de análisis combinatorio. Por ello, otro de los objetivos de la asignatura es saber reconocer este tipo de problemas y saber aplicar las técnicas adecuadas para su resolución.

Finalmente, la asignatura tiene un gran valor formativo, ya que sirve para desarrollar la capacidad analítica, la capacidad de abstracción y el pensamiento lógico

### 1.2. Contexto y sentido de la asignatura en la titulación

Se trata de una asignatura del módulo Matemática Discreta y Optimización dedicada esencialmente al estudio de estructuras discretas y a problemas de enumeración. Para su correcto desarrollo se requieren conocimientos básicos de Algebra Lineal y Análisis Matemático.

En muchas materias del ámbito de las Matemáticas los problemas subyacentes son de tipo combinatorio, por ello una base sólida en combinatoria es esencial en casi todas las ramas clásicas de las Matemáticas, como Probabilidad, Geometría, Algebra,…

Por otra parte, las estructuras discretas de Grafos y Árboles aparecen de forma natural en las materias de Informática. Señalar por último, que también dentro del campo de la Informática, para el análisis de la complejidad computacional de algoritmos se necesita conocer y manejar los métodos de enumeración.

### 1.3. Recomendaciones para cursar la asignatura

El estudio y trabajo continuado son esenciales para superar la asignatura. Se recomienda en particular la realización de los ejercicios propuestos. Una de las dificultades de la asignatura, sobre todo en los temas de Combinatoria, radica en la dificultad de distinguir los conjuntos sobre los que se trabaja, de precisar que elementos los forman. La consulta de dudas al profesor y la clarificación de conceptos son fundamentales para progresar en la materia.

### 2.1. Competencias

#### Al superar la asignatura, el estudiante será más competente para...

Desenvolverse en el manejo de los objetivos descritos (Ver apartado “Resultados de Aprendizaje”)

Resolver problemas matemáticos mediante habilidades de cálculo combinatorio y técnicas de Teoría de Grafos.

Proponer, analizar, validar e interpretar modelos de situaciones reales sencillas, utilizando las herramientas matemáticas adecuadas a los fines que se persigan.

Comprender y utilizar el lenguaje y método matemáticos.

Conocer demostraciones rigurosas de los teoremas básicos de Combinatoria y Teoría de Grafos.

Aprender nuevos conocimientos y técnicas matemáticas de forma autónoma.

Haber desarrollado habilidades de aprendizaje necesarias para emprender estudios posteriores en Matemáticas con un alto grado de autonomía.

#### El estudiante, para superar esta asignatura, deberá demostrar los siguientes resultados...

Es capaz de resolver problemas elementales de ordenación y enumeración.

Conoce y maneja el concepto de función generatriz y el de fórmula de recurrencia.

Es capaz de utilizar las funciones generatrices para obtener fórmulas para problemas de enumeración.

Conoce el lenguaje y las aplicaciones más elementales de la teoría de grafos.

Es capaz de aplicar los algoritmos básicos de teoría de grafos para resolver problemas.

### 2.3. Importancia de los resultados de aprendizaje

Proporcionan una formación de carácter básico dentro del Grado. (Ver Contexto y sentido de la asignatura en la titulación).

Además, los problemas de tipo combinatorio, son probablemente los problemas matemáticos más frecuentes en situaciones cotidianas, como organización de turnos y horarios, distribuciones de personas en grupos, realización de sorteos, muestreo, etc. Ser capaz de resolver esos problemas básicos de combinatoria de forma clara y precisa es uno de los resultados del aprendizaje.

De la misma forma, los grafos o redes, son una de las estructuras matemáticas más frecuentes en situaciones reales, y conocer sus propiedades y los algoritmos básicos para resolución de problemas sobre ellos, es fundamental para la formación de un matemático.

### 3.1. Tipo de pruebas y su valor sobre la nota final y criterios de evaluación para cada prueba

#### El estudiante deberá demostrar que ha alcanzado los resultados de aprendizaje previstos mediante las siguientes actividades de evaluacion

Para superar esta asignatura hay que obtener al menos 50 puntos. Hay dos opciones,

a) Sólo examen final (100 puntos)

b) Examen final (80 puntos)+Puntos de clase (20 puntos)

Los puntos de clase se obtienen por:

- Realización de los ejercicios propuestos a cada estudiante (4 series de problemas).

### 4.1. Presentación metodológica general

#### El proceso de aprendizaje que se ha diseñado para esta asignatura se basa en lo siguiente:

Clases de teoría: Consisten en lecciones impartidas por el profesor siguiendo principalmente el modelo de lección magistral, utilizando el apoyo de medios audiovisuales y recursos informáticos cuando sea conveniente, y procurando también cierta interacción con los estudiantes. Como máximo supondrán el 50% de las clases.

Técnicas y herramientas para la resolución de problemas: Se enseñarán técnicas de resolución de ejercicios y problemas en clase. Se propondrán también problemas y ejercicios, personales o en grupos reducidos. Estas actividades implican que los estudiantes tendrán que realizar por su parte un trabajo personal para la resolución de los problemas propuestos y la redacción de soluciones. Supondrán al menos el 40% de las clases.

Seminarios tutelados de teoría/problemas: En estos seminarios los estudiantes plantearán las dudas y dificultades con las que se han encontrado, de manera que el papel del profesor consistirá en dar indicaciones específicas que desbloqueen la situación.

Tutorías. Además de los horarios de tutorías personales establecidos por el profesor, los estudiantes dispondrán también de una dirección de correo electrónico para hacer consultas.

Trabajo personal. El estudio individual le permitirá asentar los conceptos explicados en las clases, así como aprender y aplicar adecuadamente las técnicas explicadas. También dedicará una parte importante de su tiempo a la resolución de los ejercicios propuestos.

La asignatura aparece en el Anillo Digital Docente (ADD) de la Universidad de Zaragoza. Así, el alumno puede obtener información sobre la asignatura, apuntes, material complementario, hojas de problemas, etc.

• Clases de teoría y problemas, realización de ejercicios, tutorías y seminarios sobre los siguientes tópicos:"Combinatoria elemental","Funciones generatrices","Grafos", "Camino óptimo"y "Problemas de flujo".
• Apoyo a la formación mediante documentos y enlaces  en la página de la asignatura en el ADD de la universidad, moodle.unizar.es  (acceso restringido  a los alumnos matriculados con el NIP y la contraseña suministrada por la Universidad)

### 4.3. Programa

TEMA I

1.- Combinatoria elemental: Permutaciones y combinaciones.

2.- Coeficientes binomiales.

3.- Recurrencias. Aplicaciones.

4.- El principio de inclusión-exclusión. Aplicaciones.

TEMA II

5.- Funciones generatrices.

6.- Funciones generatrices racionales.

TEMA III

7.- Definición y notaciones para grafos.

8.- Problema de recorrido de un grafo. Algoritmos  BFS y DFS.

9.- Aplicaciones. Cálculo de componentes y bases.

10.- Número de árboles y caminos de un grafo.

TEMA IV

11.- Grafos con costos. Algoritmos para calcular el árbol mínimo.

12.- Caminos más cortos: Algoritmo de Dijkstra.

13.- Técnicas PERT-CPM de planificación de proyectos.

TEMA V

14.- Flujo en redes. Conceptos básicos.

15.- Algoritmo de Ford- Fulkerson para cálculo de máximo flujo.

16.- Teoremas de conectividad de Menger.

17.- Matching en grafos bipartitos.

18.- Algunos problemas NP-Duros sobre grafos.

### 4.4. Planificación de las actividades de aprendizaje y calendario de fechas clave

#### Calendario de sesiones presenciales y presentación de trabajos

• Las clases magistrales y de problemas (hasta 4 horas a la semana) se imparten según horario establecido por el centro, publicado con anterioridad a la fecha de comienzo del curso.

• En principio habrá cuatro series de ejercicios para realizar de forma individual. Se realizarán sesiones de seminario donde cada grupo de alumnos recibirá orientación especializada para la resolución de dudas, clarificación de enunciados y realización de esos ejercicios propuestos. Los horarios de estas sesiones y las fechas límite de entrega de cada serie de ejercicios se publicarán con suficiente antelación.

Realización de un examen escrito a final de cuatrimestre, en fecha determinada por el centro.

Realización, de forma individual, de ejercicios correspondientes a las distintas partes de la asignatura.

Desde el primer día de clase los alumnos dispondrán de un calendario detallado de fechas de exámenes y fechas de entrega de los ejercicios propuestos.

### 4.5. Bibliografía y recursos recomendados

La bibliografía recomendada es la siguiente:

• Básica.-

Apuntes de la asignatura. Disponibles online en la página de la asignatura en el ADD.

• Complementaria.-

 Bóna, Miklós. A walk through combinatorics : an introduction to enumeration and graph theory / Miklos Bona . - 2nd ed.. Hackensack: World Scientific, 2008 Brualdi, Richard A. : Introductory combinatorics / Richard A. Brualdi . - 5th ed. Upper Saddle River, New Jersey : Pearson Prentice Hall, cop. 2010 Gross, Jonathan L.. Graph theory and its applications / Jonathan Gross, Jay Yellen . - 2nd ed. Boca Raton : Chapman & Hall/CRC, 2006 Lint, Jacobus Hendricus Van. A course in combinatorics / J. H. van Lint and R. M. Wilson . - [1st Ed., 2nd. repr.] Cambridge : Cambridge University Press, 1996 Pemmaraju, Sriram. Computational discrete mathematics : combinatorics and graph theory with mathematica / Sriram Pemmaraju, Steven Skiena . 1st publ., repr. Cambridge : Cambridge University Press, 2009 Stanley, Richard P.. Enumerative combinatorics / Richard P. Stanley . Cambridge ; New York : Cambridge University Press, cop. 1997-1999

• Información sobre la asignatura, con programa detallado, calendario, apuntes de la asignatura, hojas de problemas, etc., puede hallarse en la página de la asignatura en el ADD.
• Otros enlaces con material y recursos interesantes sobre Combinatoria y Teoría de Grafos son:

http://dimacs.rutgers.edu/%7Ehochberg/undopen/

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html

Discrete Mathematics Web Site!

http://www.research.att.com/~njas/sequences/

http://www.math.fau.edu/locke/graphthe.html

http://diestel-graph-theory.com/index.html

http://www.math.upenn.edu/~wilf/DownldGF.html