¿Qué es un Grafo?

Un grafo es la representación simbólica de los elementos constituidos de un sistema o conjunto, mediante esquemas gráficos. se puede decir también, que un grafo consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre nodos.

Es importante resaltar, que informalmente un grafo se define como G = (V, E), siendo los elementos de V los vértices o nodos, y los elementos de E, las aristas. formalmente, un grafo G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V.

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 los terminales y las aristas representan las conexiones inalámbricas). En fin, prácticamente cualquier problema puede representarse mediante un grafo.

Partes de un Grafo

Aristas: Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos. Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une.

Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.

• Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.
• Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
• Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
• Cruce: Son dos aristas que cruzan en un punto.

Vértices: Son los puntos o nodos con los que está conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

• Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.
• Vértice Aislado: Es un vértice de grado cero.
• Vértice Terminal: Es un vértice de grado 1.

Caminos: Se llama camino a una secuencia de vértices de un grafo tal que exista una arista, cada vértice y el siguiente. Se dice que dos vértices están conectados si existe un camino que vaya de uno a otro, de lo contrario estarán desconectados.

Los Vértices, son los objetos representados por un punto dentro del grafo. 

Las Aristas, son las líneas que unen dos vértices.

Las Arista Adyacentes, se dice que dos aristas son adyacentes si convergen sobre el mismo vértice. 

Las Aristas Múltiples o Paralelas, dos aristas son múltiples o paralelas si tienen los mismos vértices en común o incidente sobre los mismos vértices. 

Lazo, es una arista cuyos extremos inciden sobre el mismo vértice.

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 par de conjuntos , donde:

• , un conjunto no vacío de objetos simples llamados vértices o nodos.

•  es un conjunto de pares ordenados de elementos de  denominados aristas o arcos, donde por definición un arco va del primer nodo (a) al segundo nodo (b) dentro del par.

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

Dígrafos (Grafos dirigidos).

Cada arista del grafo dirigido incluye una flecha para indicar la dirección. La punta de cada flecha representa el segundo nodo del par ordenado de nodos que constituye un arco y la cola de la flecha representa el primer nodo del par.

Grafos No Dirigidos.

Un grafo no dirigido o grafo propiamente dicho es un grafo  donde:

• 
•  es un conjunto de pares no ordenados de elementos de .

Un par no ordenado es un conjunto de la forma , de manera que . Para los grafos, estos conjuntos pertenecen al conjunto de potencia de , denotado , y son de cardinalidad 2.

Grafos Mixtos

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.

Multigrafo o Pseudografo.

 Un multigrafo 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 multigrafo G es un par G:=(V, E) donde:

• V es un conjunto de vértices o nodos

• E es un multiconjunto de pares no ordenados de nodos, llamados aristas o líneas.

• V es un conjunto de vértices o nodos

• A es un multiconjunto de pares ordenados de nodos, llamados aristas dirigidas, arcos o flechas.

Ejemplo:

Los multigrafos podrían usarse, 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.

Multidigrafo 

Es un grafo dirigido que está facultado para tener aristas múltiples, es decir, aristas con los mismos nodos iniciales y finales. Formalmente, un multidigrafo G es un par G:=(V,A) donde:

• V es un conjunto de vértices o nodos

• A es un multiconjunto de pares ordenados de nodos, llamados aristas dirigidas, arcos o flechas.

Multidigrafo Mixto

G:=(V,E,A) puede definirse de la misma manera que un grafo mixto, es decir, con la capacidad de poseer al mismo tiempo aristas dirigidas (A) y no dirigidas (E).

Propiedades de los Grafos.

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, para aumentar la expresividad del modelo.

Etiquetado

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

Grafos Particulares

Grafo Nulo

En este grafo los vértices que lo componen so estás conectados, esto es, que son vértices aislados, se puede decir también, que es un grafo trivial que no tiene vértices ni aristas.

Grafo Vacío

Es aquel grafo que no tienen aristas.

Grafo Trivial 

Es un grafo trivial es un grafo con 0 aristas, y 0 ó 1 vértices. Los grafo triviales son grafos completos: a aquel que no posee vértices se le llama grafo nulo, mientras que al que posee un vértice, se le conoce como grafo singleton.

Grafo Simple

Es aquel grafo que no posee bucles o lazos. Se puede decir también, que un grafo es simple si a lo más existe una arista uniendo dos vértices cualesquiera. 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 multigrafo.

Grafo Completo

Un grafo completo es un grafo simple en el que cada par de vértices están unidos por una arista, es decir, contiene todas las posibles aristas. Se puede hacer referencia que un grafo completo de n vértices tiene  aristas, y se nota . Es un grafo regular con todos sus vértices de grado . La única forma de hacer que un grafo completo se torne disconexo a través de la eliminación de vértices, sería eliminándolos todos.

Ejemplos

Los grafos completos de 1 a 12 nodos son los siguientes:

Grafos Bipartito o Completo

 Es aquel grafo bipartito en el que todos los vértices de la partición  están conectados a todos los vértices de la partición  y viceversa.

  

En otras palabras, Un grafo bipartito completo  es un grafo bipartito tal que  Es decir, un grafo bipartito completo está formado por dos conjuntos dis-conjuntos de vértices y todas las posibles aristas que unen esos vértices.

El grafo completo bipartito con particiones de tamaño  y  es denotado como .

Ejemplos

Grafo Plano

Es aquel que puede ser dibujado en el plano cartesiano sin cruce de aristas. Todo grafo plano puede ser dibujado sobre la esfera, y viceversa.

Grafo Rueda

 Es un grafo con n vértices que se forma conectando un único vértice a todos los vértices de un ciclo-(n-1).

Se puede decir también, que un grafo rueda (W_n), o simplemente rueda, es un grafo con n vértices que se forma conectando un único vértice a todos los vértices de un ciclo-(n-1).

Los grafos rueda son grafos planos, y como tales pueden ser "incrustado" en un plano. Más específicamente, todo gráfico rueda es un grafo de Halin. Son auto-duales: el dual de cualquier grafo rueda es un grafo isomórfico.

Grafo Perfecto

Es aquel que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo.