Grafos.

Grafo.
Los grafos son representaciones de redes y por medio de ellos se pude expresar en forma visual y sencilla la relación entre elementos.
En computación los grafos se utilizan para mostrar las relaciones entre archivos en una base de datos, entre registros en una estructura de datos, entre computadoras en una red.

Partes de un grafo.
Un grafo (G) es un diagrama que consta de un conjunto de nodos (Vértices) y un conjunto de aristas (lados).

Nodos. Se indican por medio de un pequeño circulo y se le asigna un numero o una letra.

Aristas. Son las lineas que unen un nodo con otro y se les asigna una letra un numero o una combinación de ambos.

Aristas paralelas. Son las aristas que tienen relación con un mismo par de nodos.

Lazo. Es aquella arista que sale de un nodo y regresa al mismo nodo.

Valencia de un nodo. Es el numero de aristas que salen o entran a un nodo.

Tipos de grafos.

Grafos simples. Son aquellos grafos que no tienen lazos ni aristas paralelas.

Grafo completo de orden N. Es el grafo en donde cada nodo esta relacionado con todos los demas, sin lazos ni lados paralelos. Se indica Kn en donde n es el numero de nodos. La valencia de cada uno de los nodos de los grafos completos esta dada por la expresión:
numero de aristas= n(n-1)/2
en donde n es el numero de nodos.

Grafo bipartito completo. Es el grafo que esta compuesto por dos conjuntos de nodos, uno de ellos A={a1, a2, a3, ....., an} y otro B={b1, b2, .....,bm} y en el que cada nodo de A esta unido con todos los nodos de B, pero entre los nodos del mismo conjunto no existe ninguna arista que los una. Se indica como Kn,m en donde n y m es el numero de nodos de cada uno de los conjuntos.

Grafo dirigido. Es el grafo en donde las aristas tienen asociadas una dirección.


Complemento de un grafo. Es el grafo que le falta al grafo G, de forma que entre ambos forman un grafo completo de n vertices. Este grafo no tiene lazos ni ramas paralelas.