J 09/26 - Grafos II

Teoría de grafos II

Programa de desarrollo del talento matemático - IDEO 1º y 2º ESO - Curso 2024/25 Raquel Izquierdo Pato

¡Vamos!

Módulo 1

TEORÍA DE GRAFOS II

El problema de los puentes de Koninsberg. ¿Cuál es el nodo más importante del grafo?

Módulo 3

Algunos grafos para dibujar

Módulo 3

Algunos grafos para dibujar

¡Pista!

Módulo 1

¿Podemos conjeturar?

1. ¿Qué grafos hemos podido dibujar sin levantar el lápiz? 2. ¿Qué tienen en común estos grafos?

Módulos

Centralidad de grado

Centralidad de proximidad

Centralidad de intermediación

Dos problemas más sobre teoría de grafos

Objetivos

Si por ejemplo, vamos a jugar un partido de fútbol contra un equipo que se organiza de esta manera, nos interesa defender al jugador del centro del campo. Ahora, el vértice más importante es aquel que más veces se encuentra en el camino mínimo entre otros dos.

Centralidad de intermediación

Si, por ejemplo, tenemos que decidir donde poner un hospital, quizá nos interese elegir aquel vértice del grafo que más "cerca" esté de todos los demás. En lenguaje matemático, diremos que queremos minimizar la suma de las distancias al resto de nodos.

Centralidad de proximidad

A simple vista parece que el número de aristas que sale de un vértice determina cuál va a ser el más importante del grafo, pero veremos que esto no tiene por qué ser así. Dependerá de cuál sea nuestra definición de "importancia".

Centralidad de grado

El problema de los horarios

Llega el comienzo de curso y hay que hacer los horarios de clase para 1ºA y 1ºB, pero no es fácil.

• Las dos clases tienen una sesión de lengua al día (con el mismo profesor) y otra de mates (también comparten profesor).
• Algunos alumnos de 1ºA van a biología junto a algunos alumnos de 1ºB. Los demás, van a física (también se juntan los alumnos de 1ºA y 1ºB).

¿Cómo podemos hacer los horarios usando teoría de grafos?

¿Qué tubería conviene aumentar?

A continuación se muestra el flujo de agua por las tuberías de una población. ¿Cuál es el máximo flujo que llega a cada casa?

• Embalse (E) → Distribuidora 1 (D1): 10 l/s
• Embalse (E) → Distribuidora 2 (D2): 15 l/s
• Distribuidora 1 (D1) → Residencial A (A): 5 l/s
• Distribuidora 1 (D1) → Residencial B (B): 8 l/s
• Distribuidora 2 (D2) → Distribuidora 1 (D1): 4 l/s
• Distribuidora 2 (D2) → Residencial B (B): 10 l/s
• Distribuidora 2 (D2) → Residencial C (C): 10 l/s
• Residencial B (B) → Residencial C (C): 5 l/s