Trabajo grafos y matrices

OBJETIVO Nº8
ANALIZAR LOS METODOS DE ORDENAMIENTO DE MATRICES SISMETRICAS, POSITIVO DEFINIDA Y DISPERSA Y/O ALGORITMO DE CUTHILL – MCKEE PARA LA RESOLUCION DE PROBLEMAS NUMERICOS
PLANTEAMIENTO:
Una compañía de alimentos está analizando los fletes entre las diferentes plantas de distribución obteniendo los siguientes resultados:
A B C D E F G
A - - 3 4 - - -
B - - 2 5 - - -
C 3 2 - 7 8 6-
D 4 5 7 - - 4 9
E - - 8 - - 5 -
F - - 6 4 5 - 3
G - - - 9 - 3 -

CON LOS DATOS DEL PROBLEMA ANTERIOR ANALICE EL ALGORITMO DE CUTHILL-MCKEE Y REALICE LO QUE SE LE INDICA A CONTINUACION:
a) Construya el grafo asociado al problema.
b) Halle la matriz dispersa asociada al grafo.
c) Calcule el ancho de banda de la matriz.
d) Aplique el algoritmo de Cuthill – Mckee,
e) Calcule el nuevoancho de banda de la matriz.
f) Conclusiones.

Solución Parte A




Solución Parte B
Para mayor comodidad, utilizare la siguiente nomenclatura:

1  
2  
  3   
  4  
 5 
  6
  7
A = 1;
B = 2;
C = 3;
D = 4; A =
E = 5;
F = 6;
G = 7

Solución Parte C
Para el cálculo de banda utilizaremos la siguiente tabla:
Fila (i) i (A) βi(A) = i - i (A)
1 1 1 - 1= 0
2 2 2 - 2= 0
3 1 3 - 1= 2
4 1 4 - 1= 3
5 3 5 - 3= 2
6 4 6 - 4= 2
7 4 7 - 4= 3

Por tanto el ancho de banda de la matriz es elmáximo de los valores de la ultima columna del cuadro anterior; entonces tenemos que β(A)= 3
Solución Parte D
Para aplicar el algoritmo de Cuthill – Mckee vamos a resumir los pasos en la siguiente tabla:
Vértices con la etiqueta dada en el grafo Vecinos no etiquetados Grado Etiqueta de los vecinos dada por el algoritmo
V7 V4
V6 5
4 V3
V2
V2 V3
V4 5
5 V4
V3
V3 V1
V2
V4
V5
V6 2
2
5
24 V7
V6
V3
V5
V2
V5 V3
V6 5
4 V4
V2
V4 V1
V2
V3
V6
V7 2
2
5
4
2 V7
V6
V4
V2
V1

de donde se obtiene el nuevo grafo:Solución Parte E
Nueva matriz dispersa y se usará como nomenclatura:

1  
 2   
  3   
  4   
  5
  6
  7
w1 = 1;
w2 = 2;
w3 = 3;
w4 = 4; A =
w5 = 5;
w6 = 6;
w7 = 7

y el nuevo ancho de banda de la matriz es:

Fila (i) i (A) βi(A) = i - i(A)
1 1 1 - 1= 0
2 1 2 - 1= 1
3 1 3 - 1= 2
4 2 4 - 2= 2
5 2 5 - 2= 3
6 3 6 - 3= 2
7 3 7 - 3= 4

βi (A) = 4

Solución Parte F
Como podemos observar las matrices obtenidas al inicio y después de aplicar el algoritmo Cuthill – Mckee se obtienen Bi(A) = 3 y 4 respectivamente, lo que implica que hubo un aumento después de la aplicación del algoritmo.

OBJETIVO Nº 6
ANALIZAR LOSDIFERENTES METODOS NUMERICOS DIRECTOS Y/O ITERATIVOS DE FACTORIZACION DE MATRICES SIMETRICAS Y POSITIVAS DEFINIDAS, EN LA RESOLUCION DE SISTEMAS DE ECUACIONES LINEALES

PLANTEAMIENTO:
Dado el siguiente sistema de ecuaciones lineales:
10 X1 – X2 + 2X3 = 6
- X1 + 11X2 – X3 + 3X4 = 25
2 X1 – X2 + 10X3 – X4= -11
3X2 – X3 + 8X4 = 15
Y analizando los Métodos de Jacobi y Gauss – Seidel realice lo siguiente:
a. Una breve explicación de los algoritmos Jacobi y Gauss – Seidel.
b. Calcule los primeros 3 términos de la sucesión generada a partir del punto Po = (0, 0, 0,0) utilizando los algoritmos antes mencionados (use...