T.G.S GRAFOS

INTRODUCCION

Los grafos son apropiados para resolver problemas de  sistemas, ya que permiten analizar como interacciones las partes del sistema y como fluye la información

Los conceptos que estudiaremos pueden ser aplicados a cualquier tipo  de sistema

GRAFO. Un grafo es un conjunto de puntos (vértices) y un conjunto de arcos  (líneas) entre pares de vértices.

Usamos las vértices para representar las partes  de un sistema  y los arcos nos indican los efectos  de unos vértices sobre los otros.

Es decir un grafo muestra que parte de le sistema  examinando su estructura y su tecnología insistiremos  con estos dos conceptos.

La estructura de un sistema es la descripción de como las partes interaccionan

La tecnología  del sistema establece como el comportamiento  de la otra parte con la cual esta relacionada.

FIGURA 42

FIGURA 42

Asi, por ejemplo, supongamos la estructura de un sistema donde los vértices a y b afectan la acción del c como se muestra en la fig 42 anterior

Esta estructura es valida  para cualquier problema que se presente la anterior relación entre A,B    y C. En cambio la tecnología es diferente según consideremos un problema de mecánica, empresa agricultura, etc.

PRESENTACION DE LA ESTRUCTURA DE LOS SISTEMAS

Definiremos algunos elementos de la teoría de los grafos que nos serán útiles en nuestro estudio, por  ello, consideremos el grafo de la figura  sig.

En esta figura 43 la flecha que va de el vértice 1 al 2, implica que el nodo 1 afecta el nodo 2.

FIGURA 43 GRAFO SIN CIRCUITO.

FIGURA 43 GRAFO SIN CIRCUITO.

Camino, es una sucesión, de arcos tal que el extremo final de cada uno corresponde al extremo inicial del siguiente (según el sentido de la flecha)

En la fig. (1,2,5)es un camino

Efecto directo. Es  el indicado por un arco, por ejemplo, la parte 1 afecta directamente la parte  2

Efecto indirecto Es el indirecto por un camino con dos o más arcos, por ejemplo, el camino (1,2,5)

Longitud de un camino. Es el número de arcos que contiene el camino A si la longitud del camino.

*si hay un camino de a a b, a se dice predecesor (antecesor) de b y b es el sucesor de a

Circuito. Es un camino finito, en el que el nodo inicial coincide con el final.

La figura anterior no presenta ningún circuito; en cambio en la sig. Hay varios circuitos

Asi, por ejemplo, los circuitos (1,7,1);(6,2,3,4,6);etc. Bude. Es un circuito formado por un único nodo (en el mismo nodo inicia y termina).

FIGURA 44. GRAFO CON CIRCUITOS

FIGURA 44. GRAFO CON CIRCUITOS

Subgrafo.subconjunto de vértices  y arcos de un grafo.

En nuestros análisis de estructura, asignaremos a los  vértices números. Estos números representan. El orden en que se consideran. Siguiendo el orden, determinamos las partes directamente afectadas, de esta  forma no podemos establecer arcos desde un numero mayor a un menor. En próximo veremos como se efectua el ordenamiento.

MATRIZ

Otra forma de representar la estructura de un sistema, y que es equivalente a un grafo, es por medio de una matriz

La matriz es cuadrada, con tantas filas y columnas como numero de vértices presenta el grafo.El elemento a, perteneciente a la  fila, y a la columna, se indica en la matriz con la marca x

Por convección, los elementos pertenecientes a la diagonal principal se indican con un pequeño circulo.

===================================================================================================

fig 57

Fig. 57

Paso.3 Arbitrariamente comenzamos con la fila (vértice 1) para generar una secuencia de predecesores. Elegimos,arbitrariamente, el vértice con el número más bajo como el próximo preceder, generamos la secuencia 1, 2, 7, 2 .Esto releva el circuito (2, 7,2)

Agrupamos el vértice 7 en el 2. Usamos la nueva marca+ para indicarlas.

Fig. 58

Fig. 58

Marcas introducidas en la columna 2 por plegamiento, tachamos la fila y la columna 7.Este proceso  se indica en la figura 55

Ejemplo del proceso B

Partición:

Paso 2. La fila 2 no tiene marca distinta a la diagonal principal.

Paso 4. Asignamos a la fila 2 plegada 7: próximo número de orden 2 y3 suprimes el vértice 2 y sus arcos, tachamos en la matriz la fila y columnas 2. Obtenemos la figura 57.

Ejemplo de proceso B

Partición:

Paso 2 .Toda fila tiene una marca distinta a la de la diagonal principal.

Fig. 57

Fig. 57

Paso3. Generamos la secuencia de procederes 1, 12, 10, 4, 6,1.

Revela el circuito (1, 6, 4, 10, 12,1).

Plegamos 4, 6, 10,12 en 1 .Obtenemos  la figura 59 que puede verse encima de estas líneas.

Ejemplo del proceso B

Partición:

Paso 2 Toda fila tiene una marca distinta a la de la diagonal principal.

Paso 3 Generamos la secuencia de predecedores1, 5,1.

Plegamos 5 en 1 .Obtenemos así la figura en la página siguiente.

 

 

 

I-J 1 2 3 4 5 6 7 8 9
1 X                
2   X              
3     X            
4       X          
5         X        
6           X      
7             X    
8               X  
9                 X
10                  
11                  

 

 

Ejemplo del proceso B

Partición:

Paso2. Toda fila tiene una marca distinta ala de la diagonal principal

Paso3. Generamos la secuencia de predecesores 1, 3, 9,3

Plegamos 9 en 3. Obtenemos la figura 63.

Fig. 63

Fig. 63

Figura .62

 

 

 

I-J 1 2 3 4 5 6 7 8 9
1 X                
2   X              
3     X            
4       X          
5         X        
6           X      
7             X    
8               X  
9                 X
10                  
11                  

 

 

Ejemplo del proceso B

Partición:

Paso 2. Observamos que la fila 3 no tiene marca distinta a la diagonal principal.

Fig.

Fig.

Figura 64

I-J 1 2 3 4 5 6 7 8 9
1 X                
2   X              
3     X            
4       X          
5         X        
6           X      
7             X    
8               X  
9                 X
10                  
11                  

 

 

 

 

Paso 4. Asignamos a la fila 3 el número de orden 4 y a la fila 9 el número de orden 5 .Tachamos la fila y columna 3

Paso 2. La fila 1 no tiene marca distinta a la diagonal principal.

Paso 4. Asignamos a la fila 1 el número 6 y las filas que plegamos 4,5,6,10,y 12, los números de orden 7,8,9,10 y 11 respectivamente. Tachamos la fila y columna 1.

Fig.

Fig.

 

Figura 66.

I-J 1 2 3 4 5 6 7 8 9
1 X                
2   X              
3     X            
4       X          
5         X        
6           X      
7             X    
8               X  
9                 X
10                  
11                  

 

 

Paso 2. Finalmente observamos que la fila 11 no tiene marca distinta a la diagonal principal.

Paso 4. Asignamos a la fila 11. El número de orden 12 y tachamos la fila y columna 11. Obtenemos la figura 65.

 

 

I-J 1 2 3 4 5 6 7 8 9
1            8 2 7 3 9 1 4 5 6
2 8           x     x   x      
3 2 x x           x
4 7 x x       x    
5 3 x   x x       x
6 9     x x        
7 1 x       x x    
8 4     x   x x x  
9 5   x         x x

 

 

Ejemplo del proceso B

Partición:

Paso 2. No quedan vértices

Paso 5. Un número de orden ha sido asignado a cada vértice. En la figura 67 re ordenamos las filas y columnas de acuerdo al orden de los números para obtener el bloque de forma triangular en la matriz.

Fig. 68

Fig. 68

Bloque de forma triangular en la matriz.

En la matriz podemos observar que:

  • Las tareas en un bloque tiene asignados números enteros contiguos
  • Ningún arco va de una tarea de numero alto a una alta en otro bloque
  • Dadas dos tareas en un mismo bloque hay un cambio en cada dirección entre ellos.

Finalmente obtenemos la partición de grafo, como indica la figura 68.

Modelos

.Conceptos Generales.

Un modelo es una representación o abstracción de la realidad.

Muestra la relaciones entre causas y efectos, entre objetivos y detriciones

Problemas que no se pueden resolver por medio de soluciones directas debido a su magnitud, complejidad o estructura a menudo que se puede manejar buscando una solución aproximada por medio de modelos de solución.

Un modelo no puede representar todos los aspectos de la realidad  porque es únicamente una aproximación del objeto real o situación.

Para que un modelo sea representativo de la realidad, todos los hechos significativos deben ser retenidos en el modelo.

Los modelos ser examinados y comprobados respectivamente con datos observados para lograr un modelo aceptable.

La importancia de la IS en la actualidad radica en la presentación matemática de sistemas físicos y no en el uso de los modelos físicos.

Uno de los aspectos importantes del análisis del sistema operativos es evaluar las alternativas y predecir los efectos, para lo cual nos valemos del proceso de decisión.

Los planes alternativos no pueden ser ensayos  en sistemas operativos porque sería costosos, peligroso e insumiría mucho tiempo, por tanto debemos recurrir a los modelos.

Los modelos que son más fáciles de resolver son también  los más fáciles de comprender y aplicar. Sin embargo si el modelo se simplifica hasta el punto de donde ya no representa el mundo real, proporcionara resultados erróneos o engañosos.

 

About these ads

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s