grafos

GRAFOS
HISTORIA
El origen de la teoría de grafos se remonta al siglo XVIII con el problema de los puentes de Königsberg, el cual consistía en encontrar un caminoque recorriera los siete puentes del río Pregel. El problema consistía en comenzar en un punto, pasar por los siete puentes sin repetir ninguno y volver al punto departida.





APLICACIONES
Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales,contadores o sistemas de apertura. Se utiliza para diferentes áreas por ejemplo, Dibujo computacional, en toda las áreas de Ingeniería.

TIPOS DE GRAFOS
Grafo simple osimplemente grafo es aquel que acepta una sola una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única queune dos vértices específicos.
Multigrafo. o pseudografo son grafos que aceptan más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos.Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos no-dirigido.
Grafo dirigido. Son grafos en los cuales se ha añadidouna orientación a las aristas, representada gráficamente por una flecha
Grafo etiquetado. Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente)o un etiquetado a los vértices.
Grafo aleatorio. Grafo cuyas aristas están asociadas a una probabilidad.
Hipergrafo. Grafos en los cuales las aristas tienen másde dos extremos, es decir, las aristas son incidentes a 3 o más vértices.
Grafo infinito. Grafos con conjunto de vértices y aristas de cardinal infinito.