-
7/25/2019 S3 1 Presentacion Tema Semana 3 Resized Revisado
1/6
3.1 Introduccin a losgrafos ponderados
Aplicaciones de laTeora de Grafosa la vida real
Alberto Conejero y Cristina JordnDepto. Matemtica Aplicada
E.T.S. Ingeniera Informtica
Universitat Politcnica de Valncia
-
7/25/2019 S3 1 Presentacion Tema Semana 3 Resized Revisado
2/6
Introduccin
3.1. Introduccin a los grafos ponderados
Aplicaciones de la Teora de Grafos a la vida real
Los grafos muestran relaciones dentro de elementos, pero hasta
ahora dada una
pareja de vrtices (pudiendo precisar si estn ordenados) slo haba
dos opciones :
Los vrtices Sestn conectados (1 en la matriz de adyacencia).
Los vrtices NOestn conectados (0 en la matriz de
adyacencia).
Vamos a plantearnos una serie de problemas donde cada conexin
pueda tener unvalor o una importancia determinada.
Sin embargo,NO TODAS LAS CONEXIONES HAN DE SER IGUAL DE
IMPORTANTES.
-
7/25/2019 S3 1 Presentacion Tema Semana 3 Resized Revisado
3/6
Aplicaciones de la Teora de Grafos a la vida real
Dadas dos plazas, si cada arco representa una calle que las
conectaCul es el camino ms corto entre dos de ellas dadas?
Supongamos que todas las calles de la urbanizacin no tienen la
misma longitud.
3.1. Introduccin a los grafos ponderados
Diseo de una urbanizacin
-
7/25/2019 S3 1 Presentacion Tema Semana 3 Resized Revisado
4/6
Aplicaciones de la Teora de Grafos a la vida real
Red de ordenadores
Qu conexiones debemos mantener de manera queel tiempo de conexin
global entre los ordenadores de la red
sea mnimo?
Supongamos que los tiempos de conexin entre dos ordenadores son
constantes
pero distintos para cada pareja de ordenadores.
3.1. Introduccin a los grafos ponderados
Supongamos adems que queremos simplificar la red y eliminar
algunas de las
conexiones.
-
7/25/2019 S3 1 Presentacion Tema Semana 3 Resized Revisado
5/6
Aplicaciones de la Teora de Grafos a la vida real
Grupo de alumnos
Cmo podemos asignar los alumnos a sus destinos de manera que la
sumade las puntuaciones de cada alumno con el destino asignado
sea mxima?
Cada alumno ha sido entrevistado por un profesor de cada una de
las universidades
para la que ha solicitado una beca de intercambio.
3.1. Introduccin a los grafos ponderados
Sumando la puntuacin del expediente de cada alumno a la de la
entrevista, cada
alumno ha obtenido una puntuacin para cada destino.
-
7/25/2019 S3 1 Presentacion Tema Semana 3 Resized Revisado
6/6
Grupo de alumnos
Aplicaciones de la Teora de Grafos a la vida real
Cmo podemos hacer las parejas de manera queno se de el caso de
que a dos alumnos les interese romper sus parejas para
formar una nueva?
El profesor ha decidido proponer un concurso de debate entre los
alumnos.
Ha propuesto a Francisco como moderador y quieren que el resto
hagan 4 parejas
para enfrentarse en una liguilla.
3.1. Introduccin a los grafos ponderados
Le pide a cada alumno que priorice con qu compaeros quiere hacer
pareja.
