Grafos

Grafos.
Teoría de Grafos.
La teoría de grafos (también llamada teoría de las gráficas) es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos (también llamadas gráficas, que no se debe confundir con las gráficas que tienen una acepción muy amplia) estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y elconjunto de aristas, líneas o lados (edges en inglés) que pueden ser orientados o no.
La teoría de grafos es una rama de la Matemática discreta y de las aplicadas, y es un tratado que usa diferentes conceptos de diversas áreas como Análisis combinatorio, Álgebra abstracta, probabilidad, geometría de polígonos, aritmética y topología.
Actualmente ha tenido mayor preponderancia en el campo de lainformática, las ciencias de la computación y telecomunicaciones.

Multígrafos.
Un multígrafo o pseudografo es un grafo que está facultado para tener aristas múltiples; es decir, aristas que relacionan los mismos nodos. De esta forma, dos nodos pueden estar conectados por más de una arista. Formalmente, un multígrafo G es un par G:=(V, E) donde:
V es un conjunto de vértices o nodos
E es unmulticonjunto de pares no ordenados de nodos, llamados aristas o líneas.
Ejemplo. Los multígrafos podrían usarse, por ejemplo, para modelar las posibles conexiones de vuelo ofrecidas por una aerolínea. Para este caso tendríamos un grafo dirigido, donde cada nodo es una localidad y donde pares de aristas paralelas conectan estas localidades, según un vuelo es hacia o desde una localidad a la otra.
Algunosautores permiten que los multígrafos tengan bucles, es decir, que una arista conecte a un nodo consigo mismo.1


Grafo Dirigido
Un grafo dirigido o dígrafo es un tipo de grafo en el cual las aristas tienen una dirección definida, a diferencia del grafo generalizado, en el cual la dirección puede estar especificada o no.
Al igual que en el grafo generalizado, el grafo dirigido está definido por un parde conjuntos G= (V, E), donde:
V\neq\emptyset, un conjunto no vacío de objetos simples llamados vértices o nodos.
E \subseteq \{(a,b) \in V \times V: a \neq b \}\, es un conjunto de pares ordenados de elementos de V\, denominados aristas o arcos, donde por definición un arco va del primer nodo (a) al segundo nodo (b) dentro del par.
A veces un dígrafo es denominado dígrafo simple para distinguirlodel caso general del multígrafo dirigido, donde los arcos constituyen un multiconjunto, en lugar de un conjunto. En este caso, puede haber más de un arco que una dos vértices en la misma dirección, distinguiéndose entre sí por su identidad, por su tipo (por ejemplo un tipo de arco representa relaciones de amistad mientras que el otro tipo representa mensajes enviados recientemente entre losnodos), o por un atributo como por ejemplo su importancia o peso.
A menudo también se considera que un dígrafo simple es aquél en el que no están permitidos los bucles. Un bucle es un arco que une un vértice consigo mismo.

Primera definición.
Muy importante es determinar, antes del análisis del término grafos, el origen etimológico del mismo pues nos permitirá conocer de primera mano el porqué de susignificado actual. De esta manera podemos dejar patente que aquel emana de la palabra griega grafo, graphein, que puede traducirse como “grabar o escribir”.
En las ciencias de la computación y la matemática, un grafo es una representación gráfica de diversos puntos que se conocen como nodos o vértices, los cuales se encuentran unidos a través de líneas que reciben el nombre de aristas. Al analizarlos grafos, los expertos logran conocer cómo se desarrollan las relaciones recíprocas entre aquellas unidades que mantienen algún tipo de interacción.

Representación de Grafos.
Hay 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...