GRAFOS

Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole. Un grafo simple está formado por dos conjuntos:

• Un conjunto V de puntos llamados vértices o nodos.
  
  
• Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados.

De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos.

En un grafo simple entre dos nodos sólo hay un arco. Si hay más de un arco hablamos de un multigrafo. Si los arcos se pueden recorrer en una en una dirección concreta pero no en la contraria lo llamamos grafo dirigido o dígrafo y los arcos son entonces aristas, si los arcos salen y llegan al mismo punto formando un bucle el grafo resultante se llama pseudografo. 

A pesar de que un grafo parece una estructura muy elemental, hay muchísimas propiedades de los grafos cuyo estudio ha dado lugar a una completa teoría matemática

Un grafo G es un conjunto en el que hay definida una relación binaria,es decir,G=(V,A) tal que V es un conjunto de objetos a los que denominaremos vértices o nodos y es una relación binaria a cuyos elementos denominaremos arcos o aristas.
Dados ,puede ocurrir que:

1. , en cuyo caso diremos que x e y están unidos mediante un arco,y
2. , en cuyo caso diremos que no lo están.

Si las aristas tienen asociada una dirección(las aristas (x,y) y (y,x) no son equivalentes) diremos que el grafo es dirigido,en otro caso ((x,y)=(y,x)) diremos que el grafo es no dirigido.

Conceptos asociados a grafos:

• Diremos que un grafo es completo si A=VxV,o sea,si para cualquier pareja de vértices existe una arista que los une(en ambos sentidos si el grafo es no dirigido).El número de aristas será:
  • grafos dirigidos:
    
    
    
  • grafos no dirigidos:
    
    
    
  donde n=|V| 
.
• Un grafo dirigido es simétrico si para toda arista (x,y)perteneciente a A también aparece la arista (y,x)perteneciente a A;y es antisimétrico si dada una arista (x,y) perteneciente a A implica que (y,x) no pertenece a A.
• Tanto a las aristas como a los vértices les puede ser asociada información.A esta información se le llama etiqueta.Si la etiqueta que se asocia es un número se le llama peso,costo o longitud.Un grafo cuyas aristas o vértices tienen pesos asociados recibe el nombre de grafo etiquetado o ponderado.
• El número de elementos de V se denomina orden del grafo.Un grafo nulo es un grafo de orden cero.
• Se dice que un vértice x es incidente a un vértice y si existe un arco que vaya de x a y ((x,y)pertenece a A),a x se le denomina origen del arco y a y extremo del mismo.De igual forma se dirá que y es adyacente a x.En el caso de que el grafo sea no dirigido si x es adyacente(resp. incidente) a y entonces y también es adyacente (resp. incidente) a x.
• Se dice que dos arcos son adyacentes cuando tienen un vértice común que es a la vez origen de uno y extremo del otro.
• Se denomina camino (algunos autores lo llaman cadena si se trata de un grafo no dirigido)en un grafo dirigido a una sucesión de arcos adyacentes:
  C={(v₁,v₂),(v₂,v₃),...,(v_n-1,v_n), para todo v_i perteneciente a V}
• La longitud del camino es el número de arcos que comprende y en el caso en el que el grafo sea ponderado se calculará como la suma de los pesos de las aristas que lo constituyen. 

• Un camino se dice simple cuando todos sus arcos son distintos y se dice elemental cuando no utiliza un mismo vértice dos veces.Por tanto todo camino elemental es simple y el recíproco no es cierto.
• Un camino se dice Euleriano si es simple y además contiene a todos los arcos del grafo.
• Un circuito(o ciclo para grafos no dirigidos)es un camino en el que coinciden los vértices inicial y final.Un circuito se dice simple cuando todos los arcos que lo forman son distintos y se dice elemental cuando todos los vértices por los que pasa son distintos.La longitud de un circuito es el número de arcos que lo componen.Un bucle es un circuito de longitud 1(están permitidos los arcos de la forma(i,i) y notemos que un grafo antisimétrico carecería de ellos).
• Un circuito elemental que incluye a todos los vértices de un grafo lo llamaremos circuito Hamiltoniano.
• Un grafo se denomina simple si no tiene bucles y no existe más que un camino para unir dos nodos.
• Diremos que un grafo no dirigido es bipartido si el conjunto de sus vértices puede ser dividido en dos subconjuntos(disjuntos) de tal forma que cualquiera de las aristas que componen el grafo tiene cada uno de sus extremos en un subconjunto distinto.Un grafo no dirigido será bipartido si y sólo si no contiene ciclos con un número de aristas par.
• Dado un grafo G=(V,A),diremos que G^'=(V,A^') con es un grafo parcial de G y un subgrafo de G es todo grafo G^'=(V^',A^') con y donde A^' será el conjunto de todas aquellas aristas que unían en el grafo G dos vértices que están en V^'. Se podrían combinar ambas definiciones dando lugar a lo que llamaremos subgrafo parcial 

• Se denomina grado de entrada de un vértice x al número de arcos incidentes en él.Se denota .
• Se denomina grado de salida de un vértice x al número de arcos adyacentes a él.Se denota .
• Para grafos no dirigidos tanto el grado de entrada como el de salida coinciden y hablamos entonces de grado y lo notamos por .
• A todo grafo no dirigido se puede asociar un grafo denominado dual construido de la siguiente forma:
  
  donde A' está construido de la siguiente forma:si e₁,e₂ pertenece a A son adyacentes --> (e₁,e₂)pertenece a A' con e₁,e₂ pertenece a V'.En definitiva,para construir un grafo dual se cambian vértices por aristas y viceversa.

Dado un grafo G,diremos que dos vértices están conectados si entre ambos existe un camino que los une.

Llamaremos componente conexa a un conjunto de vértices de un grafo tal que entre cada par de vértices hay al menos un camino y si se añade algún otro vértice esta concición deja de verificarse.Matemáticamente se puede ver como que la conexión es una relación de equivalencia que descompone a V en clases de equivalencia,cada uno de los subgrafos a los que da lugar cada una de esas clases de equivalencia constituiría una componente conexa.Un grafo diremos que es conexo si sólo existe una componente conexa que coincide con todo el grafo.

-Bibliografia
http://www.infovis.net/printMag.php?num=137&lang=1
http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/grafos.htm