ing en Sistemas

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 unas relaciones: por ejemplo, losproblemas relacionados con posibilidades de comunicación (redes de comunicación y de transporte), relaciones de orden entre actividades (planificación de proyectos mediante PERT) o estructuras deproducto complejas (gestión de inventarios mediante MRP).
Los grafos son una herramienta que permite modelizar relaciones de esta naturaleza, de modo que se puedan resolver problemas asociados a esascircunstancias, 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 la nomenclatura yconceptos asocia- dos a estas representaciones de relaciones entre elementos, así como sus diversas formas de representación.
Seguidamente se definirá formalmente un grafo, pasando posteriormente a mostrarlas 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
Un grafo 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 de losvé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. Un grafo noorientado puede siempre convertirse en orientado, expresando la doble relación entre los vértices


Representación de grafos
Existen múltiples maneras de representar un grafo. Tomemos un grafoorientado 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)}
Mé todos cuantitativos en organización industrial...