• Descripción

En este curso se hace una introducción a la teoría de grafos que incluye temas relacionados con el diseño y manipulación de redes. Se estudian las familias de grafos más usadas, operaciones con grafos, algoritmos de exploración de grafos, grafos planares, coloración de vértices, problemas de optimización relacionados con el concepto de distancia en grafos, así como algunos fundamentos de la teoría espectral de grafos.  Además, se estudian las medidas de centralidad en grafos y medidas de centralización, incluyendo índices topológicos, la medida de bipartividad de una red y medidas de fiabilidad en redes con pesos. Los contenidos estudiados se pueden aplicar al análisis de redes complejas que incluyen redes sociales, foodwebs, redes de interacción de proteínas, entre otros. Los estudiantes matriculados obtendrán una amplia introducción a los trabajos recientes en este ámbito.

• La asignatura en el conjunto del plan de estudios

La asignatura Grafos y Aplicaciones es una asignatura optativa de 6 créditos que se oferta a los estudiantes durante el primer semestre. El contenido de la asignatura se enmarca dentro de la matemática discreta y es fundamental para el diseño, manipulación y análisis de redes. Se recomienda a los estudiantes hacer esta asignatura antes de hacer Redes Complejas.

• Conocimientos previos

Formación básica en matemática

• Objetivos y competencias

El objetivo principal de este curso es  introducir al estudiante a la investigación en teoría de grafos.

• Contenidos

En este curso se hace una introducción a la teoría de grafos que incluye temas relacionados con el diseño y manipulación de redes. Se estudian las familias de grafos más usadas, operaciones con grafos, algoritmos de exploración de grafos, grafos planares, coloración de vértices, problemas de optimización relacionados con el concepto de distancia en grafos, así como algunos fundamentos de la teoría espectral de grafos.  Además, se estudian las medidas de centralidad en grafos y medidas de centralización, incluyendo índices topológicos, la medida de bipartividad de una red y medidas de fiabilidad en redes con pesos. Los contenidos estudiados se pueden aplicar al análisis de redes complejas que incluyen redes sociales, foodwebs, redes de interacción de proteínas, entre otros. 

• Consulta de los recursos de aprendizaje que dispone la asignatura

• Bibliografía y fuentes de información

* E. Estrada, J. A. Rodriguez-Velazquez, Spectral measures of bipartivity in complex networks, Physical Review E 72 (2005) 046105.
URL http://link.aps.org/doi/10.1103/PhysRevE.72.046105

*  E. Estrada, J. A. Rodriguez-Velazquez, Subgraph centrality in complex networks, Physical Review E 71 (2005) 056103.
URL http://link.aps.org/doi/10.1103/PhysRevE.71.056103

* T. Doslic, Bipartivity of fullerene graphs and fullerene stability, Chemical Physics Letters 412 (4{6) (2005) 336-340.
URL http://www.sciencedirect.com/science/article/pii/S0009261405010274

* J. A. Rodriguez, E. Estrada, A. Gutierrez, Functional centrality in graphs, Linear and Multilinear Algebra 55 (3) (2007) 293-302.
URL http://www.tandfonline.com/doi/full/10.1080/03081080601002221

* J. A. Rodriguez-Velazquez, A. Kamisalic, J. Domingo-Ferrer, On reliability indices of communication networks, Computers & Mathematics with Applications 58 (7) (2009) 1433-1440.
URL http://www.sciencedirect.com/science/article/pii/S089812210900491X

• Metodología

The correct monitoring of the course involves reading the study material, solving the recommended exercises and conducting the continuous assessment tests.

Through the communication spaces of the classroom the teacher will deliver the continuous assessment activities. he/she will answer any questions related to the learning process and monitor the course planning.

It is advisable to follow the recommended timing and check the classroom spaces regularly.

• Información sobre la evaluación en la UOC

La Normativa académica de la UOC dispone que el proceso de evaluación se fundamenta en el trabajo personal del estudiante y presupone la autenticidad de la autoría y la originalidad de los ejercicios realizados.

La falta de originalidad en la autoría o el mal uso de las condiciones en las que se hace la evaluación de la asignatura es una infracción que puede tener consecuencias académicas graves.

Se calificará al estudiante con un suspenso (D/0) si se detecta falta de originalidad en la autoría de alguna actividad evaluable (práctica, prueba de evaluación continua (PEC) o final (PEF), o la que se defina en el plan docente), ya sea porque ha utilizado material o dispositivos no autorizados, ya sea porque ha copiado de forma textual de internet, o ha copiado de apuntes, de materiales, manuales o artículos (sin la citación correspondiente) o de otro estudiante, o por cualquier otra conducta irregular.

La calificación de suspenso (D/0) en la evaluación continua (EC) puede conllevar la obligación de hacer el examen presencial para superar la asignatura (si hay examen y si superarlo es suficiente para superar la asignatura según indique este plan docente).

Cuando esta mala conducta se produzca durante la realización de las pruebas de evaluación finales presenciales, el estudiante puede ser expulsado del aula, y el examinador hará constar todos los elementos y la información relativos al caso.

Además, esta conducta puede dar lugar a la incoación de un procedimiento disciplinario y la aplicación, si procede, de la sanción que corresponda.

La UOC habilitará los mecanismos que considere oportunos para velar por la calidad de sus titulaciones y garantizar la excelencia y la calidad de su modelo educativo.

• Consulta del modelo de evaluación