Aplicación del álgebra lineal en la teoría de grafos

Introducción.

En esta investigación se pretende aplicar algunos temas de algebra lineal a la teoría de grafos, iniciaremos con conceptos básicos de álgebra lineal hasta llegar a los conceptos de la teoría de grafos, es importante mencionar que esta teoría ayuda resolver bastantes problemas cotidianos, como encontrar la ruta más rápida de una punto A a un punto B, hasta temas más complejos como la quimica. Es por ello que se darán ejemplos aplicados a algunos problemas los cuales aplicando ambas teoría se pueden resolver.

Además se mostrará como poder crear Grafos en el software MATLAB a partir de matrices, esperando que pueda ser un incentivo a aprender a usar estas nuevas hermmaientas.

Objetivos

General

Explicar y demostrar como se aplica el algebra lineal a la teoría de grafos y como se pueden utilizar en la vida real.

Particulares

Demostrar como se representan los grafos en matrices, adyacentes y de acceso

Indexar la página web de la UAM Xochimilco, representándola gráfica y matricialmente.

Mostrar en MATLAB ejemplos de como hacer grafos con matrices

Capitulo 1: Línea del tiempo sobre la Teoría de Grafos

Capitulo 2: Temas necesarios de algebra lineal

Vectores

Vector renglón de n componentes

Un vector de n componentes se define como un conjunto ordenado de n números escritos de la siguiente manera: (x1, x2, . . . , xn).

Vector columna de n componentes

Un vector columna de n componentes es un conjunto ordenado de n números escritos de la siguiente manera:

Matriz

Una matriz A de m x n es un arreglo rectangular de mn numero dispuestos en m renglones y n columnas

3.Teoría de Grafos

¿Para que nos sirve la teoría de grafos?

Conceptos básicos

¿Qué es un grafo?

Los grafos son una estructura de datos no lineal, la cual se puede usar para modelar diversas aplicaciones. Es muy importante mencionar que los grafos se presentan con frecuencia en la vida real, un ejemplo es: una red de carreteras que enlacen a un grupo de ciudades, donde las ciudades representan los vértices del grafo y las carreteras representan las aristas o arcos, cada arco asocia una información como distancia entre ciudades, consumo de gasolina etc.

Los arcos o aristas que unen a los vertices se representan por medio de un par de elementos

(vi, vj), estos elementos representan los vértices que une la arista.

En un grafo orientado cada arco se representa por medio de un par ordenado (vi, vj) donde el primer elemento es el nodo origen o fuente y el segundo es el nodo destino de ese arco, por lo tanto, se puede decir que el arco va desde vi hasta vj y que vj es adyacente a vi. Un grafo orientado también se llama un dígrafo. Si los arcos del grafo no indican una dirección, el grafo es no dirigido y en él cada arco se puede representar nombrando los nodos que lo forman sin importar el orden, es decir: (vi, vj) = (vj, vi)

En otras palabras una grafica dirigida es una colección de n puntos y estos son denominados vértices (estos son denotados por V1, V2 … Vn) junto con un numero finito de aristas y unen distintos pares de vértices. Cualquier grafica se puede representar mediante una matriz n x n

Grafo 1 Grafo 2

En el grafo 1 podemos observar un grafo

...