Teoria de grafos

Teoría de grafos

137

7 Teoría de grafos
7.1 Introducción
En numerosos problemas cuantificables, en las organizaciones, intervienen una serie de elementos entre los que se establecen unasrelaciones: por ejemplo, los problemas relacionados con posibilidades de comunicación (redes de comunicación y de transporte), relaciones de orden entre actividades (planificación de proyectos mediantePERT) o estructuras de producto complejas (gestión de inventarios mediante MRP). Los grafos son una herramienta que permite modelizar relaciones de esta naturaleza, de modo que se puedan resolverproblemas asociados a esas circunstancias, frecuentemente de forma menos costosa que utilizando otras técnicas como la programación lineal. Una buena comprensión de la teoría de grafos pasa por dominar lanomenclatura y conceptos asociados a estas representaciones de relaciones entre elementos, así como sus diversas formas de representación. Seguidamente se definirá formalmente un grafo, pasandoposteriormente a mostrar las diversas representaciones que admite. Con estos elementos podemos definir cómodamente los diversos elementos conceptuales asociados a los grafos 7.1.1 Definición de grafo Ungrafo G (x, E) consta de un conjunto de elementos “x”, denominados nodos o vértices, y un listado de parejas de vértices E que expresa las relaciones entre dichos elementos. Si no se considera el orden delos vértices en cada pareja, dichos pares se denominan aristas, y decimos que el grafo es no orientado. Si se consideran las relaciones, el par de aristas se llama arco y el grafo es orientado. Ungrafo no orientado puede siempre convertirse en orientado, expresando la doble relación entre los vértices. 7.1.2 Representación de grafos Existen múltiples maneras de representar un grafo. Tomemos ungrafo orientado G(x, E) definido como con un conjunto de vértices y arcos: X = (1,2,3,4,5) E = {(1,5), (1,2), (2,5), (5,4), (3,4), (3,2), (2,3), (4,5)}

© Los autores, 2002; © Edicions UPC, 2002....