J 09/26 - Grafos II
Raquel Izquierdo Pato
Created on September 13, 2024
More creations to inspire you
Transcript
¡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).
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?