Teoria de grafos

TEORIA DE GRAFOs

Este tema bastante importante, muy conocido y desconocido a la vez, tiene como origen histórico el problema clásico de los siete puentes de Könisberg, propuesto por LeonhardEuler. Digo desconocido, porque en realidad vivimos beneficiándonos de todas sus aplicaciones y pasa inadvertido. Por ejemplo: el circuito eléctrico de nuestra casa, el transporte masivo o metro, líneastelefónicas, líneas de televisión por cable, y una red de computadoras, pueden representarse y estudiarse mediante un grafo, entre muchas otras situaciones cotidianas. Otras aplicaciones más avanzadasson el caso de la geometría combinatoria, la investigación operativa, inteligencia artificial y la química orgánica.

Ahora, si bien el significado etimológico de la palabra “GRAFO” es trazar,podemos definir un grafo como la representación gráfica de los datos de una situación particular.

En términos Matemáticos un grafo se representa mediante una serie de puntos (vértices) conectados porlíneas (aristas), así: un grafo G es un par G= (V, A), donde V es un conjunto finito (vértices, nodos) y A es un multiconjunto de pares no ordenados de vértices, denotados por {x, y}, que se denominanlados, aristas o enlaces, los cuales pueden ser orientados o no, característica que los clasifica en dos grupos: Grafos Dirigidos y No Dirigidos. En un grafo dirigido cada par ordenado de vérticesrepresentan dos arcos diferentes, mientras que en un grafo no dirigido cada par de vértices no ordenados, (v1, v2) y (v2, v1), representan el mismo arco.

A partir de esta clasificación haré unabreve descripción de los principales tipos de grafos:

▪ Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.
▪ Grafo bipartito: Es aquelcon cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto.
▪ Grafo completo: Aquel con una arista entre cada par...