El curso de Grafos y Matrices presenta los conceptos de grafos y dígrafos, algunas relaciones importantes que se pueden establecer como cadena, camino, ciclo y circuito así como también ciertas propiedades basadas en estas definiciones. Luego contiene un análisis y aplicación de los diferentes métodos para la resolución de grandes sistemas de ecuaciones lineales, para finalizar con un estudio algorítmico de problemas de recorrido y búsqueda de caminos en grafos.
Objetivo general de la asignatura
Analizar con sentido crítico y lógico, problemas numéricos relacionados con las matrices simétricas, positivo definidas y dispersas, utilizando métodos y técnicas relacionadas con la teoría de grafos, así como también los diferentes esquemas de búsqueda eficiente en grafos.
Fundamentos de la teoría de grafos
Resumen histórico de los inicios del álgebra lineal
Objetivo 1
Describir las propiedades básicas de los grafos, digrafos y su representación matricial en una situación dada.
Los grafos como par de conjuntos. Conjunto de vértices. Aristas y Arcos. Grado de un vértice. Adyacencia y Vecindad de un vértice. Definición de dígrafo. Matrices de Adyacencia e Incidencia. Subgrafo. Subgrafos parciales. Grafo Simétrico, Grafo Antisimétrico. Cadenas y Ciclos en un grafo. La noción de conectividad. Caminos y Circuitos en dígrafos. Componentes Conexas. Número Conectividad. Ciclos de Euler y de Hamilton. Árboles y Forestas.
Ciclos Eulerianos
Ciclo Hamiltoniano
Objetivo 2
Aplicar las propiedades de grafos y dígrafos en la resolución de problemas numéricos.
Completitud en grafos y dígrafos. Grafos y dígrafos bipartitos. Grafos y dígrafos con Acoplamientos y Acoplamientos Perfectos. Conjuntos independientes y estables en grafos y dígrafos.
Grafo bipartito
Número cromático
Grafo planar
Objetivo 3
Aplicar los diferentes algoritmos y esquemas de recorrido y búsqueda en grafos y dígrafos para la resolución de problemas numéricos.
Caminos más cortos. Ruta Crítica en grafos. Algoritmos de Dijkstra. Algoritmos de búsqueda primero en profundidad. Algoritmos de búsqueda primero en anchura.
Algoritmo de Dijkstra
Objetivo 4
Aplicar el Método de la Eliminación Gaussiana en una matriz asociada a un sistema de ecuaciones lineales para la obtención de su solución.
Sistemas de ecuaciones lineales. Matrices triangulares. Eliminación gaussiana con y sin pivoteo. Método del valor absoluto. Complejidad algorítmica.
Método de eliminación gaussiano
Objetivo 5
Aplicar los métodos de factorización LU, Doolitle y Crout de una matriz simétrica y definida positiva, en la resolución de sistemas de ecuaciones lineales.
Eliminación gaussiana y factorización LU de una matriz. Matrices especiales: triangulares, tridiagonales, etc. Método de factorización de Doolitle. Método de factorización de Crout.
Descomposición LU
Método de Crout teoría
Ejercicio
Método de Doolittle teoría
Ejercicio
Objetivo 6
Analizar los diferentes métodos numéricos directos y/o iterativos de factorización de matrices simétricas y positivas definidas, en la resolución de sistemas de ecuaciones lineales.
Descomposición LU y el Factor de Cholesky de una matriz simétrica y positiva definida. Introducción a los métodos numéricos directos. Factorización de Cholesky. Método de Thomas. Conteo de Operaciones mínimas para la implementación de los algoritmos asociados a estos métodos. Métodos numéricos iterativos. Métodos directos contra métodos iterativos. Método de Jacobi. Método de Gauss – Seidel. Conteo de Operaciones mínimas para la implementación de los algoritmos asociados a estos métodos.
Objetivo 7
Analizar los esquemas de almacenamiento para matrices simétrica, positivo definida y dispersa.
Matrices dispersas. Estructura nula – no-nula de una matriz. Esquemas de almacenamiento: Arreglos, Listas, Listas enlazadas, Listas contiguas.
Objetivo 8
Analizar los métodos de ordenamiento de matrices simétricas, positivo definida y dispersa y/o el Algoritmo de Cuthill- Mckee para la resolución de problemas numéricos.
Esquemas de ordenamiento de una matriz. Método de la Banda. Método de la Envolvente. Algoritmo de Cuthill – McKee y su inverso. Complejidad del algoritmo.
Objetivo 9
Analizar el Modelo de Grafos de Eliminación usando la noción de alcanzabilidad entre vértices, para la optimización del ordenamiento dado por la Eliminación Gaussiana.
La noción de grafos de eliminación. Introducción al grafo cociente. Alcanzabilidad entre vértices de un grafo y su relación con los grafos de eliminación. Grafos de eliminación y la eliminación gaussiana.
Objetivo10
Analizar esquemas para la selección del vértice inicial utilizando los métodos numéricos estudiados y el diseño del algoritmo de mínimo grado.
Vértices periféricos. Relación de equivalencia definida en un grafo. Estrategia de selección del vértice inicial para los métodos introducidos en el módulo. Algoritmo de mínimo grado.
REFERENCIAS
Alsina, C. (2012) Mapas del metro y redes neuronales. La teoría de grafos. Colección El mundo es matemático. EDITEC. Disponible en https://archive.org/details/mapas-del-metro-y-redes-neuronales-la-teoria-de-grafos
Epp, S. (2012) Matemáticas discretas con aplicaciones. Cuarta edición. Cengage learning editores. Disponible en https://bibliotecavirtual8denovpinas.wordpress.com/wp-content/uploads/2020/08/matematicas-discretas-con-aplicaciones-epp-4ta-edicion-2.pdf
Liu, C. (1995) Elementos de matemáticas discretas. Segunda edición. McGraw Hill. Disponible en https://gc.scalahed.com/recursos/files/r161r/w25470w/Elementosdematematicasdiscretas.pdf
