Grafos

Instituto Tecnológico de Zacatepec

Tema de investigación: Teoría de Grafos

Materia: Matemáticas Discretas

Maestro: Miguel Delgado Reyes

Grupo: XD No. De Control: 11090936

Teoría de Grafos
¿Qué es un Grafo?
En matemáticas y en ciencias de la computación, la teoría de grafos o también llamada teoría de las gráficas, estudia las propiedades de los grafos ográficas. Un grafo es un conjunto, no vacío, de objetos llamados vértices o nodos y una selección de pares de vértices, llamados aristas que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos que son los vértices conectados por líneas que son las aristas.

Caracterización de grafos
Grafos simples
Un grafo es simple si a lo más existe una arista uniendo dosvértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Un grafo que no es simple se denomina multigráfo.

Grafos conexos
Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde “a” hacia “b”.
Un grafo es doblementeconexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.
Es posible determinar si un grafo es conexo usando un algoritmo; Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS).
En términos matemáticos la propiedad de un grafo de ser conexo permite establecer con base en éluna relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes conexas", es decir, porciones del grafo, que son conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

.

¿Para qué sirven o como se implementan en el área del informático?
Existen diferentes formas de almacenargrafos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveenacceso rápido, pero pueden consumir grandes cantidades de memoria.
Ha y tres maneras de representar un grafo en un programa: mediante matrices, mediante listas y mediante matrices dispersas.
* Representación mediante matrices:   La forma más fácil de guardar la información de los nodos es mediante la utilización de un vector que indexe los nodos, de manera que los arcos entre los nodos sepueden ver como relaciones entre los índices. Esta relación entre índices se puede guardar en una matriz, que llamaremos de adyacencia.
* Representación mediante listas:    En las listas de adyacencia lo que haremos será guardar por cada nodo, además de la información que pueda contener el propio nodo, una lista dinámica con los nodos a los que se puede acceder desde él. La información de losnodos se puede guardar en un vector, al igual que antes, o en otra lista dinámica.
* Representación mediante matrices dispersas:    Para evitar uno de los problemas que teníamos con las listas de adyacencia, que era la dificultad de obtener las relaciones inversas, podemos utilizar las matrices dispersas, que contienen tanta información como las matrices de adyacencia, pero, en principio, noocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el grafo.

Aplicaciones de los gráfos
Una de las aplicaciones mas importantes es de hallar el camino mas corto hacia un destino, ya sea de una ciudad a otra, de unos departamentos a otros, para el recorrido de árboles, sirve para la representación de...