6.6 APLICACIONES DE GRAFOS Y ARBOLES
¿Qué es un grafo? Recordemos que un grafo G es el par (V, A) que representa una relación entre un conjunto de Vértices y otro de Aristas. Representaremos cada elemento arista como un par de elementos de V. Gráficamente representaremos los vértices por puntos y las aristas por líneas que los unen. Un vértice puede tener 0 o más aristas, pero toda arista debe unir exactamente 2 vértices. Las aplicaciones más importantes de los grafos son las siguientes: • Rutas entre ciudades. • Determinar tiempos máximos y mínimos en un proceso. • Flujo y control en un programa
Los grafos son la representación natural de las redes, en las que estamos cada vez más incluidos. Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole. Un grafo simple está formado por dos conjuntos: • Un conjunto V de puntos llamados vértices o nodos. • Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados. De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos. En un grafo simple entre dos nodos sólo hay un arco.