Grafos Matematica Discreta

Introducción
En matemáticas y ciencias de la computación, un grafo (del griego grafos: dibujo, imagen) o gráfica es un conjunto de objetos llamados vértices(punto común entre loslados consecutivos de una figura o ángulo) o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.Grafo
Un grafo G es un par ordenado G = (V,A), donde V es un conjunto de vértices o nodos y A es un conjunto de arcos o aristas, que relacionan estos nodos.
Bucles
Es una arista que relaciona almismo nodo, o sea una arista cuyo nodo inicial es el mismo nodo final.
Grafo no Dirigido

Grafo Dirigido

Grafo Simple
No tiene lazos, aristas paralelas, ni aristas dirigidas.
Grafo no SimpleAquel que tiene lazos y lados paralelos.
Grafo Ponderado
Se presentan los pesos de cada arista
Grafo Completo
Puede contener n vértices, en la que existe una arista entre cada par de vértices.Grafo de Similitud
Son aquellos donde se derivan sub-grafos.
Grafos Regulares
Aquellos que tienen el mismo número de aristas.
Grafo Bipartido
La sumatoria de los grados de un grafo es igual aldoble de las aristas que tiene un grafo.




Estructura de Datos en la Representación de Grafos

Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos usadadepende 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 unacombinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidadesde memoria.


Estructura de Listas

Lista de Incidencia: Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las...