J 09/26 - Grafos II

¡Vamos!

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

Teoría de grafos II

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

TEORÍA DE GRAFOS II

Módulo 1

Algunos grafos para dibujar

Módulo 3

Algunos grafos para dibujar

Módulo 3

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

¿Podemos conjeturar?

Módulo 1

¡Pista!

Prueba a contar el número de aristas que salen de cada vértice...

Centralidad de intermediación

Centralidad de proximidad

Centralidad de grado

Módulos

Objetivos

Dos problemas más sobre teoría de grafos

Centralidad de intermediación

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 proximidad

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 grado

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".

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?

El problema de los horarios

• 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

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?

¿Qué tubería conviene aumentar?