Teoría de los Grafos


Índice:
Unidad 6 Teoría de Grafos
6.1 Elementos y características de los grafos.
6.1.1 Componentes de un grafo (vértices aristas lazos valencia).
6.1.2 Tipos de grafos (Simples, completos, bipartidos, planos, conexos, ponderados).
6.2 Representación de los grafos.
6.2.1 Representación Matemática de los grafos.
6.2.2 Representación Computacional de los grafos.
6.3 Algoritmos derecorrido y búsqueda.
6.3.1 Algoritmos de recorrido y búsqueda El camino más corto.
6.3.2 Algoritmos de recorrido y búsqueda A lo ancho.
6.3.3 Algoritmos de recorrido y búsqueda En profundidad.
6.4 Arboles.
6.4.1 Componentes raíz hoja padre hijo descendientes ancestros.
6.4.2 Propiedades Arboles.
6.4.3 Clasificación Arboles altura numero de nodos.
6.4.4 Arboles con peso.
6.4.5Recorrido de un árbol Pre orden inorden Postorden.
6.5 Redes teorema de flujo máximo teorema de flujo mínimo pareos y redes de Petri.
6.6 Aplicaciones de grafos y arboles.


Teoría de grafos:
La Teoría de Grafos juega un papel importante en la fundamentación matemática de las Ciencias de la Computación. Los grafos constituyen una herramienta básica para modelar fenómenos discretos y sonfundamentales para la comprensión de las estructuras de datos y el análisis de algoritmos. En matemáticas y ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos, que son colecciones de objetos llamados vértices (o nodos) conectados por líneas llamadas aristas (o arcos) que pueden tener orientación (dirección asignada). Típicamente, un grafo está diseñado por una seriede puntos (los vértices) conectados por líneas (las aristas).

El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado como uno de los primeros resultados de la teoría de grafos. También se considera uno de los primeros resultados topológicos en geometría (que no depende de ninguna medida). Este ejemplo ilustra la profunda relación entre la teoría degrafos y la topología. En 1845 Gustav Kirchhoff publicó sus leyes de los circuitos para calcular el voltaje y la corriente en los circuitos eléctricos. En 1852 Francis Guthrie planteó el problema de los cuatro colores que plantea si es posible, utilizando solamente cuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, queno fue resuelto hasta un siglo después por Kenneth Appel y Wolfgang Haken, puede ser considerado como el nacimiento de la teoría de grafos. Al tratar de resolverlo, los matemáticos definieron términos y conceptos teóricos fundamentales de los grafos.


6.1 Elementos y Características de los Grafos:
Grafo:
Un conjunto de vértices V y de aristas E, tal que cada arista se asocia a un par devértices.
Una arista “e” en un grafo asociada a vértices “a” y “b”, se dice, que es incidente en “a” y “b” y viceversa, que “a” y “b” son incidentes en “e”. Y por lo tanto que “a” y “b” son vértices adyacentes en “e”.
Si “G” es un grafo con vértices “V” y aristas “E”, entonces G = (V, E).
Ejemplo de un grafo:

Lazo:
 Es una arista incidente en un sólo vértice. Ejemplo: a6 = (V5, V5).

Aristasparalelas:
Cuando dos o más aristas están asociadas con el mismo par de vértices. Ejemplo: las aristas a2 y a3 de la Figura 2 están asociadas al mismo par de vértices. Es decir: a2 = (V1, V3) y a3 = (V1, V3).
Vértice aislado:
 El vértice que no es incidente en alguna arista. Ejemplo:

Grado o valencia de un vértice “v”:
Es el número de aristas incidentes en “v”. Ejemplo:

Subgrafos: Parte de un grafo.


Ejemplo, algunos subgrafos de este grafo serían los siguientes:

6.1.1 Componentes de un grafo (vértices, aristas, lazos y valencia):
Aristas.- Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.
Aristas Adyacentes: Se dice que dos aristas son adyacentes si coinciden en el mismo vértice.
Aristas Paralelas: Se dice que...