Modelo de redes

MODELOS DE REDES. PROBLEMAS DE REDES DE OPTIMIZACIÓN

INTRODUCCION
La teoría de grafos o de las gráficas estudia las propiedades de los grafos o gráficas. Konig fue uno de los precursores de esta teoría. En teoría de grafos, sólo queda lo esencial del dibujo. La forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y sepuede variar para obtener un dibujo más claro.
Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o la red de carreteras
El concepto de grafo implica un conjunto de elementos (denominados vértices) entre los que existen ligaduras (segmentos), pudiendo a su vez, estar orientados (vectores o arcos), que reflejan lascorrespondencias de unos vértices con otros.

Si tenemos un conjunto de un número finito de elementos, que designamos por las letras x1,x2,……,xn, y al conjunto por la letra X: X = {X1, X2,….., Xn}, y a cada elemento xi perteneciente a X hacemos corresponder cero, uno o varios elementos de X, se forma un grafo, según la teoría de conjuntos.
Si L es la ley de correspondencia considerada, se puederepresentar el grado mediante el símbolo:
G = (X, L)

El grafo de la figura queda expresado de la siguiente forma:

o bien, mediante una tabla de doble entrada:

X Lx
x1 - x2 x3 x4
x2 x1 - x3 -
x3 x1 x2 - x4
x4 x1 - x3 -

El grafo puede tener los segmentos:
- Sin orientar → denominándose aristas.


- Orientados →arcos. El vértice del que parte el arco se le denomina inicial uorigen (xi), y aquel en que llega se le denomina terminal, final o destino (xj).

También se puede expresar mediante una relación de orden:
(Xi < Xj) , Xi antecede a Xj;
(Xj > Xi) , xj sigue a xi.
Dos vértices consecutivos se dice que son adyacentes. De igual forma se llama a las aristas o arcos que se inician o terminan en un vértice.
Un vértice que tiene más de un arco en un sentido sedenomina nudo, y antinudo, todos los vértices que no cumplen la condición anterior.
En un grafo no orientado, al conjunto de dos o más aristas se denomina cadena, y al de una cadena que empieza y termina en el mismo vértice se llama ciclo. Ejemplo:

En un grafo orientado o dirigido, al conjunto de dos o más arcos se denomina camino, y al de un camino que empieza y termina en el mismo vérticese llama circuito. Cuando el circuito se compone de un solo arco se llama bucle. Ejemplo:

En ambos casos de grafo, orientado o no orientado, se denomina longitud de una cadena, o camino, al número de aristas o arcos que lo componen.
Tanto las cadenas como los caminos pueden ser:
- Simples → Cuando no tienen ninguna arista o arco que se repita. Estos pueden ser a su vez:
• Elementales →cuando no tienen ningún vértice que se repita.
• No elementales → En los demás casos.
- Compuestos → En los demás casos.

Las cadenas y caminos que integran a todos los vértices del grafo una sola vez se denominan hamiltonianos, pudiendo cerrarse con el vértice que se inició, y entonces serán respectivamente, ciclo y circuito hamiltonianos.

Las cadenas y caminos que integran a todos lasaristas y arcos del grafo una sola vez se denominan eulerianos. También pueden iniciarse y finalizar en el mismo vértice, y entonces serán respectivamente, ciclo y circuito eulerianos.
SUBGRAFOS
Pueden ser:
- Subgrafo respecto a los vértices → Dado un grafo, se denomina subgrafo a otro grafo tal que sus vértices son un subconjunto de los vértices del grafo inicial, y sus arcos son todos delgrafo. Ejemplo: En una red de lineas de metro, considerar solo una de las lineas de metro.
- Subgrafo respecto a las aplicaciones o grafo parcial → Cuando el conjunto de vértices no varía, pero disminuye el de aplicaciones. En una red de transportes de una ciudad (autobus, metro, tranvia) seria solo considerar la red de metro.


Componente conexa de un subgrafo, cuando para el conjunto de sus...