Grafos

Grafos :
En matemáticas y en ciencias de la computación, la teoría de grafos o teoría de las gráficas, estudia las propiedades de los grafos, también llamadas grá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 puntosconectados por líneas.
Es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v) tal que . Para simplificar, notaremos la arista (a,b) como ab.
En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. Laposición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.
Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o la red de drenaje de una ciudad.
Origen de los grafos:
El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado el primerresultado 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.
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 solamentecuatro colores, colorear cualquier mapa de países de tal forma que dos países vecinos nunca tengan el mismo color. Este problema, que no 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.
GrafosSimples:
Un grafo es simple si hay sólo 1 arista que une dos vértices cualquiera. 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áfica o Grafo múltiple.
Grafos Dirigidos y No Dirigidos:
Grafos Dirigidos:
Un grafo en el cual toda arista es dirigida se denominará dígrafo o bien grafo dirigido.Un grafo dirigido consiste de un conjunto de vértices V y un conjunto de arcos A.
Los vértices se denominan nodos o puntos; los arcos también se conocen como aristas o líneas dirigidas que representan que entre un par de vértices existe una relación unívoca.
Grafos no Dirigidos:
Un grafo en el cual todas las aristas son no dirigidas se denominará grafo no dirigido. El grafo nodirigido es aquel que no tiene sentido su arista. Un grafo no dirigido G representa elementos, y una arista (v, w) representa una incompatibilidad entre los elementos v y w.
Si en un Grafo hay aristas dirigidas y aristas no dirigidas, entonces el grafo se denomina mixto.


Conceptos asociados a Grafos:
A) Completos: Diremos que un grafo es completo si A=VxV,o sea,si para cualquier pareja devértices existe una arista que los une (en ambos sentidos si el grafo es no dirigido).El número de aristas será:
grafos dirigidos:

grafos no dirigidos:


donde n=|V|

B) Simétricos: Un grafo dirigido es simétrico si para toda arista (x,y) perteneciente a A también aparece la arista (y,x) perteneciente a A; y es antisimétrico si dada una arista (x,y) perteneciente a A implica que (y,x) nopertenece a A.

C) Etiqueta: Tanto a las aristas como a los vértices les puede ser asociada información. A esta información se le llama etiqueta.Si la etiqueta que se asocia es un número se le llama peso, costo o longitud. Un grafo cuyas aristas o vértices tienen pesos asociados recibe el nombre de grafo etiquetado o ponderado.

D) Orden: El número de elementos de V se denomina orden del...