Investigacion de operaciones redes

GRAFICAS:

Definición: Se define una gráfica como la pareja G = (X,A), en donde X = {Xi}; i=1,2,...,n, es un conjunto de elementos que se pueden hacer corresponder a cada Xi un punto del plano llamado vértice de la gráfica y “A” es el conjunto {(Xi,Xj)} y, tal que, Xi y Xj pertenecen a “X”, haciéndole corresponder una flecha que une a Xi y Xj, que se llama arco de la gráfica. Por lo tanto“A” es el conjunto de relaciones que establecen para cada para de elemento de X. Es posible que entre dos vértices no sea único el arco que los une.
X3
X2 [pic]X5
X1 [pic]
X4
X3
X5


[pic]X2 X4
[pic]
Ejemplo: Se ilustran las redes arriba

1.2 CONCEPTOS Y TERMINOS RELACIONADOS CON GRAFICAS

1.- Sea |X| el número de vértices de la gráfica.
2.- Sea |A| el número de arcos de la gráfica.
3.- Extremo:
Sea u=(Xi,Xj), Xi se le denomina extremo inicial y a Xj extremo final del arco u.
4.- Vértices adyacentes:Dos vértices Xi y Xj se dicen adyacentes si son distintos y si existe cuando menos un arco que los una.
5.- Arcos adyacentes: Dos o más arcos son adyacentes si tienen un vértice común.
6.- Arcos incidentes a un vértice: Se dice que un arco es incidente a un vértice Xi, hacia el exterior, si Si es un extremo inicial y su extremo final es distinto de Xi.
7.- Arco incidente a un conjunto devértices: Si Y C X es un conjunto de vértices de la gráfica G=(X,A), se dice que el arco u=(Xi,Xj) es incidente a Y hacia el exterior si se tiene Xi pertenece a Y, Xj no pertenece a Y.
El conjunto de arcos incidentes a Y hacia el exterior, se representa por W+(Y).
De forma semejante se dice que el arco u = (Xk,Xe) es incidente a Y hacia el interior si se tiene Xk no pertenece a Y, Xe pertenece a Y. Elconjunto de arcos incidentes a Y hacia el interior se le representa con W-(Y). Al conjunto de arcos incidentes a Y se el representa con W(Y)=W+(Y) ( W-(Y).
8.- Camino: Un camino es una secuencia c {u1, u2,..., uk} de arcos tal que el extremo final de cada arco coincide con el extremo inicial del arco que ele sigue. Un camino también queda definido por los vértices de los arcos que lo forman.9.- Camino simple: Es un camino que no utiliza más de una vez el mismo arco. De forma contraria se dice que es compuesto.
10.- Camino elemental: Es un camino que no utiliza más de una vez el mismo vértice. En caso contrario se dice que es no-elemental.
11.- Circuito: Un circuito es un camino finito c = (u1, u2,..., uk), en el cual el extremo inicial del primer arco coincide con el extremofinal del último arco de el camino.
12.- Circuito elemental: Cuando todos los vértices que contiene son distintos a excepción del primero y el último vértice que coinciden.
13.- Anillo: Es un circuito que está constituido por sólo un vértice y un solo arco.
14.- Gráfica completa: Se dice que una gráfica es completa si toda pareja de vértices están ligados al menos en una de las dos direcciones.Esto es, G=(X,A) es completa si ( (Xi,Xj) no pertenece a “A” ( (Xi,Xj) pertenece a “A”.
15.- Gráfica fuertemente conexa: Se dice que una gráfica G=(X,A) es fuertemente conexa si ( Xi ( Xj con Xi ( Xj siempre existe un camino de Xi a Xj.
16.- Arista: Se llama arista de una gráfica G=(X,A) a un conjunto de dos vértices Xi, Xj, Xi ( Xj ( (Xi,Xj) pertenecen a “A” y/o (Xi,Xj) pertenecen a...