Explicacion de Grafos

Un Grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.

Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.

El primer artículo científico relativo a grafos fue escrito por el matemático suizo Leonhard Euler en 1736. Euler se basó en su artículo en el problema de los puentes de Königsberg. La ciudad de Kaliningrado.

Un grafo G es un par ordenado G = (V, E), donde:

· V es un conjunto de vértices o nodos, y

· E es un conjunto de aristas o arcos, que relacionan estos nodos.}

Normalmente V suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos.

Grafo no dirigido

Un grafo no dirigido o grafo propiamente dicho es un grafo G = (V, E) donde:

{\displaystyle V\neq \emptyset }V no es igual a 0
E es un conjunto de pares no ordenados de elementos de {\displaystyle V\,}V.

Un par no ordenado es un conjunto de la forma {a,b} , de manera que {a,b} = {b,a}.

Grafo dirigido

Un grafo dirigido o digrafo es un grafo G = (V, E) donde:

{\displaystyle V\neq \emptyset }V no es igual a 0
E es un conjunto de pares ordenaos de elementos de {\displaystyle V\,}V.

Dada una arista (a,b) , a es su nodo inicial y b su nodo final.

Por definición, los grafos dirigidos no contienen bucles.

Un grafo mixto es aquel que se define con la capacidad de poder contener aristas dirigidas y no dirigidas. Tanto los grafos dirigidos como los no dirigidos son casos particulares de este.

Propiedades

Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.

Incidencia: una arista es incidente a un vértice si ésta lo une a otro.

Ponderación: corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para problemas de optimización, como el del vendedor viajero o del camino más corto.

Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.

Existen grafos que poseen propiedades destacables. Algunos ejemplos básicos son:

Grafo vacío: aquel que no tiene aristas.

Grafo trivial: aquel que tiene un vértice y ninguna arista.

Grafo simple: aquel que no posee bucles ni aristas paralelas.

Multígrafo (o pseudografo): G es multígrafo si y solo si no es simple.

Grafo completo: grafo simple en el que cada par de vértices están unidos por una arista, es decir, contiene todas las posibles aristas.

Grafo bipartito completo: sea (W, X) una partición del conjunto de vértices V, es aquel donde cada vértice en W es adyacente sólo a cada vértice en X, y viceversa.