Guía docente de la asignatura
(7293) GRAFOS Y OPTIMIZACIÓN DISCRETA

Curso académico 2026/2027

  1. Identificación

    1. De la asignatura

      Curso Académico
      2026/2027
      Titulación
      GRADO EN MATEMÁTICAS
      PROGRAMA ACADÉMICO DE SIMULTANEIDAD DE DOBLE TITULACIÓN CON ITINERARIO ESPECIFICO DE GRADO EN MATEMÁTICAS Y GRADO EN INGENIERÍA INFORMÁTICA
      PROGRAMA ACADÉMICO DE SIMULTANEIDAD DE DOBLE TITULACIÓN CON ITINERARIO ESPECÍFICO DE GRADO EN MATEMÁTICAS Y GRADO EN FÍSICA
      Nombre de la asignatura
      GRAFOS Y OPTIMIZACIÓN DISCRETA
      Código
      7293
      Curso
      TERCERO
      CUARTO
      TERCERO
      Carácter
      OBLIGATORIA
      Número de grupos
      3
      Créditos ECTS
      6.0
      Estimación del volumen de trabajo
      150.0
      150.0
      150.0
      Organización temporal
      1º Cuatrimestre
      1º Cuatrimestre
      2º Cuatrimestre
      Idiomas en que se imparte
      Español
      Curso Académico 2026/2027
      Titulación

      GRADO EN MATEMÁTICAS,

      PROGRAMA ACADÉMICO DE SIMULTANEIDAD DE DOBLE TITULACIÓN CON ITINERARIO ESPECIFICO DE GRADO EN MATEMÁTICAS Y GRADO EN INGENIERÍA INFORMÁTICA,

      PROGRAMA ACADÉMICO DE SIMULTANEIDAD DE DOBLE TITULACIÓN CON ITINERARIO ESPECÍFICO DE GRADO EN MATEMÁTICAS Y GRADO EN FÍSICA

      Nombre de la asignatura GRAFOS Y OPTIMIZACIÓN DISCRETA
      Código 7293
      Curso TERCERO CUARTO TERCERO
      Carácter OBLIGATORIA
      Número de grupos 3
      Créditos ECTS 6.0
      Estimación del volumen de trabajo 150.0 150.0 150.0
      Organización temporal 1º Cuatrimestre 1º Cuatrimestre 2º Cuatrimestre
      Idiomas en que se imparte Español
    2. Del profesorado: Equipo docente

      • MARIN PEREZ, ALFREDO N. Docente: GRUPO 1, GRUPO DTIE Coordinación de los grupos: GRUPO 1, GRUPO DTIE Coordinador de la asignatura

        Categoría

        CATEDRATICOS DE UNIVERSIDAD

        Área

        ESTADÍSTICA E INVESTIGACIÓN OPERATIVA

        Departamento

        ESTADÍSTICA E INVESTIGACIÓN OPERATIVA

        Correo electrónico / Página web / Tutoría electrónica

        amarin@um.es Tutoría electrónica: No

        Teléfono, horario y lugar de atención al alumnado

        Duración:
        A
        Día:
        Miércoles
        Horario:
        11:00-14:00
        Lugar:
        868883627, Facultad de Matemáticas y Aulario General B1.2.009 (DESPACHO PROF. ALFREDO MARÍN PÉREZ)
        Observaciones:
        Mi despacho es el 2.11 de la Facultad de Matemáticas. Las horas de tutorías pueden solaparse con otras actividades. Estaré disponible para tutorías siempre que esté en el despacho, pero es muy conveniente pedir cita por correo para evitar al alumno pérdidas innecesarias de tiempo.
        Duración:
        A
        Día:
        Jueves
        Horario:
        11:00-14:00
        Lugar:
        868883627, Facultad de Matemáticas y Aulario General B1.2.009 (DESPACHO PROF. ALFREDO MARÍN PÉREZ)
        Observaciones:
        Mi despacho es el 2.11 de la Facultad de Matemáticas. Las horas de tutorías pueden solaparse con otras actividades. Estaré disponible para tutorías siempre que esté en el despacho, pero es muy conveniente pedir cita por correo para evitar al alumno pérdidas innecesarias de tiempo.
      • PULIDO CAYUELA, MANUEL ANDRES Docente: GRUPO DTIE Coordinación de los grupos: GRUPO DTIE

        Categoría

        PROFESORES TITULARES DE UNIVERSIDAD

        Área

        ESTADÍSTICA E INVESTIGACIÓN OPERATIVA

        Departamento

        ESTADÍSTICA E INVESTIGACIÓN OPERATIVA

        Correo electrónico / Página web / Tutoría electrónica

        mpulido@um.es Tutoría electrónica: Sí

        Teléfono, horario y lugar de atención al alumnado

  2. Presentación

    Los grafos resumen la información de un conjunto de objetos que se relacionan, o no, entre sí. Si además se añade una medida de esta relación, el concepto de grafo se extiende al de red. Puede modelarse mediante un grafo un mapa de carreteras o metro, una red de comunicaciones, de tendidos eléctricos, gasísticos, etcétera. Pero también pueden usarse los grafos en otros casos menos obvios, como la modelización de la incompatibilidad (países con fronteras comunes no pueden colorearse de la misma forma en un mapa), del movimiento de una ficha en un juego, incluso veremos aplicaciones en química y biología. La Teoría de Grafos es muy extensa, y contempla muchos puntos de vista distintos. En esta asignatura intentaremos, en lo posible, que el alumno tenga una visión amplia de la materia que le sirva de base para hipotéticas ampliaciones de conocimientos.

    Entre los problemas más interesantes que se presentan sobre estructuras modelizables como grafos están los de optimización discreta. Estudiaremos la forma de formularlos y resolverlos como problemas de programación lineal entera y nos introduciremos en las principales técnicas subyacentes en los algoritmos utilizados comúnmente por el software específico del campo.

  3. Condiciones de acceso a la asignatura

    1. Incompatibilidades

      No constan

    2. Requisitos

      No constan

    3. Recomendaciones

      Es recomendable haber superado la asignatura de Optimización Lineal

  4. Contenidos

    1. Teoría

      Bloque 1: Teoría de Grafos

      Tema 1: Conceptos básicos en Teoría de Grafos

      Definiciones y ejemplo. Primero resultados.Ejercicios

      Tema 2: Conexión

      Conexión y componentes conexas. Algunos resultados sobre conexión. k-conexión. Ejercicios

      Tema 3: Árboles

      Introducción y árboles con raíz. Árboles binarios. Árboles generadores de peso mínimo. Algoritmos de Kruskal y Prim. Ejercicios

      Tema 4: Camino más corto. Recorridos por aristas y vértices

      Caminos más cortos. Algoritmo de Dijkstra. Grafos eulerianos. Grafos hamiltonianos. El problema del viajante de comercio. Ejercicios.

      Tema 5: Grafos planos. Coloración de grafos

      Coloración. Teorema fundamental de reducción. Planaridad. Coloreado de grafos planares. Ejercicios.

      Bloque 2: Optimización Discreta

      Tema 1: Modelo de programación entera

      Repaso de Optimización Lineal. Algoritmo dual. Modelo de Programación Entera. Formulación de problemas de optimización sobre grafos. Indicaciones para formular. Ejercicios.

      Tema 2: Ramificación y acotación. Hiperplanos de corte

      Algoritmo de ramificación y acotación. Hiperplano de corte todo entero. Hiperplano de corte mixto. Ejercicios.

    2. Prácticas

      • Práctica 1: Resolución de problemas de Optimización Discreta

        Las prácticas se llevarán a cabo en un aula de ordenadores con el software xpress para Optimización Discreta, siguiendo un cuadernillo preparado al efecto

        Relacionado con:
        • Tema 1: Conceptos básicos en Teoría de Grafos
        • Tema 2: Conexión
        • Tema 3: Árboles
        • Tema 4: Camino más corto. Recorridos por aristas y vértices
        • Tema 5: Grafos planos. Coloración de grafos
        • Tema 1: Modelo de programación entera
        • Tema 2: Ramificación y acotación. Hiperplanos de corte

  5. Actividades Formativas

    Actividad Formativa Metodología Horas Presencialidad
    AF1: Exposición teórico-práctica 24.0 100.0
    AF2: Resolución de ejercicios y problemas en grupo completo 5.0 100.0
    AF3: Resolución de ejercicios y problemas en grupos reducidos 15.0 100.0
    AF4: Prácticas con ordenador 10.0 100.0
    AF8: Trabajo autónomo del estudiante 90.0 0.0
    AF10: Realización de pruebas de evaluación 6.0 100.0
    Totales 150,00

  6. Horario de la asignatura

    https://www.um.es/web/estudios/grados/matematicas/2026-27#horarios

  7. Sistemas de Evaluación

    Identificador Denominación del instrumento de evaluación Criterios de Valoración Ponderación
    SE1 Examen global teórico-práctico

    Se responderá preguntas de teoría (enunciados, demostraciones y cuestiones teóricas sobre los resultados centrales de la asignatura) contando un 40% de la calificación

    El 60% restante consistirá en la resolución por escrito de cuestiones prácticas, ejercicios y problemas.

    80.0
    SE2 Valoración de prácticas de ordenador

    Al final de la asignatura, se llevará a cabo un control para evaluar las prácticas de xpress.

    10.0
    SE3 Valoración del progreso

    En el control de xpress se incluirá la formulación de un problema de optimización discreta.

    10.0

  8. Fechas de exámenes

    https://www.um.es/web/estudios/grados/matematicas/2026-27#examenes

  9. Resultados del Aprendizaje

    • RA01 (): Utilizar con rigor el lenguaje matemático con el fin de desarrollar argumentos lógicos.
    • RA02 (): Comunicar correctamente, tanto por escrito como de forma oral, conocimientos e ideas matemáticas.
    • RA03 (): Entender demostraciones de teoremas de forma autónoma.
    • RA04 (): Comprobar con demostraciones o refutar con contraejemplos propiedades de objetos matemáticos.
    • RA05 (): Desarrollar una actitud (auto)crítica ante los razonamientos matemáticos, en particular identificando errores en razonamientos que son incorrectos.
    • RA06 (): Resolver problemas y cuestiones prácticas del ámbito de las matemáticas aplicando los conocimientos teóricos.
    • RA07 (): Modelar problemas de la realidad, utilizando las herramientas matemáticas más adecuadas a los fines perseguidos.
    • RA08 (): Aplicar técnicas informáticas y de programación para la resolución de problemas en el ámbito de las matemáticas.
    • RA24 (): Conocer los fundamentos teóricos de la optimización lineal y discreta y de la investigación operativa.
    • RA25 (): Aplicar los conocimientos de optimización lineal y discreta y de investigación operativa a la resolución de problemas.

  10. Bibliografía

    Bibliografía complementaria

    No constan

  11. Observaciones

    NECESIDADES EDUCATIVAS ESPECIALES

    Aquellos estudiantes con discapacidad o necesidades educativas especiales podrán dirigirse al Servicio de Atención a la Diversidad y Voluntariado (ADYV - https://www.um.es/adyv) para recibir orientación sobre un mejor aprovechamiento de su proceso formativo y, en su caso, la adopción de medidas de equiparación y de mejora para la inclusión, en virtud de la Resolución Rectoral R-358/2016. El tratamiento de la información sobre este alumnado, en cumplimiento con la LOPD, es de estricta confidencialidad.

    EVALUACIÓN

    En el procedimiento de evaluación resultarán de aplicación el artículo 135.1.v) de los Estatutos de la Universidad de Murcia, el artículo 8.6 del Reglamento de Evaluación de Estudiantes (REVA) y la instrucción SG 18/2026 del secretario general de la Universidad de Murcia que interpreta estas normas, disponible en este enlace: https://sede.um.es/sede/documento/normativa/instruccion-del-secretario-general-sg-18-2026-sobre-la-interpretacion-y-aplicacion-del-art-135-1-v-estatutos-umu/24199.pdf

    Se recuerda asimismo que el artículo 22.1 del Reglamento de Evaluación de Estudiantes (REVA) estipula que "el o la estudiante que se valga de conductas fraudulentas, incluida la indebida atribución de identidad o autoría, o esté en posesión de medios o instrumentos que faciliten dichas conductas, obtendrá la calificación de cero en el procedimiento de evaluación y, en su caso, podrá ser objeto de sanción, previa apertura de expediente disciplinario".

    OBSERVACIONES DEL EQUIPO DOCENTE

    El plagio y/o copia en cualquier proceso de la evaluación de la asignatura es un comportamiento poco ético y tendrá como consecuencia, de forma automática, el suspenso en la actividad evaluada.

    Esta asignatura no se encuentra vinculada de forma directa con los Objetivos de Desarrollo Sostenible

    Al final del periodo de docencia de cada grupo (hay grupos en los dos cuatrimestres), los estudiantes que estén en ese grupo (y solo ellos) recibirán dos notas de Evaluación Continua correspondiente a los sistemas de evaluación SE2 y SE3. En dicha convocatoria, la calificación será la ponderación establecida en el punto 7 para las notas de los tres sistemas de evaluación . Es decir, 0.8*SE1 + 0.1*SE2 + 0.1*SE3. En convocatorias sucesivas de dicho grupo, los estudiantes podrán optar por mantener su calificación de los sistemas SE2 y SE3 (esto es lo que se debe hacer si no solicitan nada), o solicitar que se les evalúe de nuevo de las competencias cubiertas por dichos sistemas de evaluación. En este caso, el examen global incluirá pruebas que permitan al estudiante obtener la máxima nota en dichos sistemas de evaluación. De nuevo, la calificación global será 0.8*SE1 + 0.1*SE2 + 0.1*SE3. Los estudiantes deberán solicitar dicha evaluación mediante Mensaje Privado del Aula Virtual con una antelación mínima de 7 días a la fecha del examen final correspondiente.

    Debido a la proliferación de estudiantes que utilizan la IA u otros medios digitales para prepararse la asignatura, debe quedar claro que cualquier respuesta en los exámenes que utilice resultados, procedimientos, algoritmos, conocimientos o cualquier otra fuente no impartida por los profesores de la asignatura será considerada errónea. Como ejemplos, valgan (i) el uso de notación o terminología discordante con la explicada, (ii) recurrir a resultados teóricos no vistos en clase que no sea explícitamente demostrados en la respuesta del examen, (iii) uso de algoritmos no incluidos en la materia impartida, (iv) uso de fórmulas que, aun siendo correctas, no hayan sido desarrolladas en clase ni estén justificadas en la respuesta del examen, como hiperplanos de corte alternativos. En general se desaconseja el uso de la IA para preparar la asignatura, ya que en muchas ocasiones entra en conflicto con la notación y/o resultados vistos en clase.