Estructura de Datos

Modelizacion de la World-Wide Web
Estudio de la topología de la Web (conectividad, diámetro).
Formulación de algoritmos de valoración de las paginas web (p.e. algoritmo
PageRank de Google).



Aplicación a la Ecología.
Estudio de la conectividad del paisaje (Urban et al.)



Análisis del camino critico.
Formulación del problema: Planificar las actividades de un proyecto de forma
que el tiempo total para realizarlo sea el menor posible.
Modelizacion: Dado el correspondiente grafo de actividades, hallar el camino
mas largo entre los v ertices que representan los estados `inicio' y ` fin'.



El problema de los `horarios'
Formulaci on del problema: Confeccionar un calendario de examenes, que
comprenda el mínimo numero de días, teniendo en cuenta que un estudiante
no puede realizar mas de un examen en un mismo día.
El problema de la asignación de frecuencias en una red celular de
teléfono a móvil.
Formulación del problema: Asignar a cada celda un rango de frecuencias de
manera que celdas contiguas tengan rangos disjuntos (`bien separados').
Como debe hacerse dicha asignación con el fin de minimizar el total de
frecuencias usadas.
Modelizaci on: Dado el grafo de incompatibilidades, hallar una vértice
coloración del mismo utilizando el menor numero de colores posible.

El problema del camino m nimo (Dijkstra, 1959)
Formulaci on del problema: Dada una red de transporte hallar la ruta optima
entre cada par de elementos de la misma.
Modelización: Calcular la distancia y encontrar un camino minimo entre cada
par de vértices de un grafo conexo y ponderado.



El problema de los de cuatro colores (Appel y Haken 1976)
Conjetura (Francis Guthrie, 1852): Todo mapa trazado sobre una hoja de
papel puede colorearse usando solamente cuatro tintas de manera que
los paises" con \frontera com un" tengan colores diferentes.



An alisis de redes el ectricas (Kirchho , 1847).


Enumeración de is-omeros quimicos (Cayley, 1857).


Comentario.
Nos sirven para dar una mejor interpretación sobre un problema que tengamos y por medio de un algoritmo matemático poder resolverlo de la mejor manera.

Bibliografía.
Aplicaciones de los grafos.12 mayo 2010
http://web.udl.es/usuaris/p4088280/teaching/grafos_modelos.pdf