Want to create interactive content? It’s easy in Genially!

Get started free

J 09/26 - Grafos II

Raquel Izquierdo Pato

Created on September 13, 2024

Start designing with a free template

Discover more than 1500 professional designs like these:

Dynamic Learning Course

Akihabara Course

Minimal Course

Basic Interactive Course

Explore all templates

Transcript

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

Módulo 1

¿Podemos conjeturar?

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

¡Pista!
Módulos

Centralidad de proximidad

Centralidad de intermediación

Centralidad de grado

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

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?

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

¿Qué tubería conviene aumentar?