GRAFOS

1. INTRODUCCIÓN.

El origen de la palabra grafo es griego y su significado etimológico es "trazar". Aparece con gran frecuencia como respuesta a problemas de la vida cotidiana,algunos ejemplos podrían ser los siguientes:un gráfico de una serie de tareas a realizar indicando su secuenciación (un organigrama),grafos matem´ticos que representan las relaciones binarias,una red de carreteras,la red de enlaces ferroviarios o aéreos o la red eléctrica de una ciudad.(Véase la figura 1).En cada caso,es conveniente representar gráficamente el problema dibujando un grafo como un conjunto de puntos(vértices)con líneas conectándolos (arcos).

De aquí se podría deducir que un grafo es básicamente un objeto geométrico aunque en realidad sea un objeto combinatorio,es decir,un conjunto de puntos y un conjunto de líneas tomado de entre el conjunto de líneas que une cada par de vértices.Por otro lado,y debido a su generalidad y a la gran diversidad de formas que pueden usarse,resulta complejo tratar con todas las ideas relacionadas con un grafo.

Para facilitar el estudio de este tipo de dato,a continuación se realizará un estudio de la teoría de grafos desde el punto de vista de las ciencias de la computación. Considerando que dicha teoría es compleja y amplia,aquí sólo se realizará una introducción a la misma,describiéndose el grafo como un tipo de dato y mostrándose los problemas típicos y los algoritmos que permiten solucionarlos usando un ordenador.

Los grafos son estructuras de datos no lineales que tienen una naturaleza generalmente dinámica. Su estudio podría dividirse en dos grandes bloques:

• Grafos Dirigidos.
• Grafos no Dirigidos(pueden ser considerados un caso particular de los anteriores).

Un ejemplo de grafo dirigido lo constituye la red de aguas de una ciudad ya que cada tubería sólo admite que el agua la recorra en un único sentido.Por el contrario,la red de carreteras de un país representa en general un grafo no dirigido,puesto que una misma carretera puede ser recorrida en ambos sentidos.No obstante,podemos dar unas definiciones generales para ambos tipos.

A continuación daremos definiciones de los dos tipos de grafos y de los conceptos que llevan asociados.

2. DEFINICIONES Y TERMINOLOGÍA FUNDAMENTAL.

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.
  Ejemplo.
  • En el grafo dirigido de la figura 2,un camino que une los vértices 1 y 4 es C= {(1,3),(3,2),(2,1)},su longitud es 3.
  • En el grafo no dirigido de la figura 2,un camino que une los vértices 1 y 4 es C^'= {(1,2),(2,4)}.Su longitud es 2.



• 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.
.

3. TDA GRAFO.

A la hora de diseñar el TDA grafo hay que tener en cuenta que hay que manejar datos correspondientes a sus vértices y aristas,pudiendo cada uno de ellos estar o no etiquetados.Además hay que proporcionar operaciones primitivas que permitan manejar el tipo de dato sin necesidad de conocer la implementación.Así,los tipos de datos que se usarán y las operaciones primitivas consideradas son las siguientes:

NUEVOS TIPOS APORTADOS.

Los nuevos tipos aportados por el TDA grafo son los siguientes:

• grafo.
• vertice.
• arista.

4. REPRESENTACIONES PARA EL TDA GRAFO.

Existen diversas representaciones de naturaleza muy diferente que resultan adecuadas para manejar un grafo,y en la mayoría de los casos no se puede decir que una sea mejor que otra siempre ya que cada una puede resultar más adecuada dependiendo del problema concreto al que se desea aplicar.Así,si existe una representación que es peor que otra para todas las operaciones excepto una es posible que aún así nos decantemos por la primera porque precisamente esa operación es la única en la que tenemos especial interés en que se realice de forma eficiente.A continuación veremos dos de las representaciones más usuales:Matriz de adyacencia(o booleana) y Lista de adyacencia.

MATRIZ DE ADYACENCIA.

Grafos dirigidos.

G=(V,A) un grafo dirigido con |V|=n .Se define la matriz de adyacencia o booleana asociada a G como B_nxn con

Como se ve,se asocia cada fila y cada columna a un vértice y los elementos b_i,j de la matriz son 1 si existe el arco (i,j) y 0 en caso contrario.

Grafos no dirigidos.

G=(V,A) un grafo no dirigido con |V|=n .Se define la matriz de adyacencia o booleana asociada a G como B_nxn con:

La matriz B es simetrica con 1 en las posiciones ij y ji si existe la arista (i,j).

EJEMPLO:

Si el grafo es etiquetado,entonces tanto b_i,j como b_i,j representan al coste o valor asociado al arco (i,j) y se suelen denominar matrices de coste. Si el arco (i,j) no pertenece a A entonces se asigna b_i,j o b_i,j un valor que no puede ser utilizado como una etiqueta valida.

La principal ventaja de la matriz de adyacencia es que el orden de eficiencia de las operaciones de obtencion de etiqueta de un arco o ver si dos vertices estan conectados son independientes del número de vértices y de arcos. Por el contrario, existen dos grandes inconvenientes:

• Es una representación orientada hacia grafos que no modifica el número de sus vertices ya que una matriz no permite que se le o supriman filas o columnas.
• Se puede producir un gran derroche de memoria en grafos poco densos (con gran número de vértices y escaso número de arcos).

Para evitar estos inconvenientes se introduce otra representación: las listas de adyacencia.

LISTAS DE ADYACENCIA.

En esta estructura de datos la idea es asociar a cada vertice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sóllo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i. El grafo, por tanto, se representa por medio de un vector de n componentes (si |V|=n) donde cada componente va a ser una lista de adyacencia correspondiente a cada uno de los vertices del grafo. Cada elemento de la lista consta de un campo indicando el vértice adyacente. En caso de que el grafo sea etiquetado, habrá que añadir un segundo campo para mostrar el valor de la etiqueta.

Esta representacion requiere un espacio proporcional a la suma del número de vértices, más el nùmero de arcos, y se suele usar cuando el número de arcos es mucho menor que el número de arcos de un grafo completo. Una desventaja es que puede llevar un tiempo O(n) determinar si existe un arco del vértice i al vértice j, ya que puede haber n vertices en la lista de adyacencia asociada al vértice i.

Mediante el uso del vector de listas de adyacencias sólo se reserva memoria para los arcos existentes en el grafo con el consiguiente ahorro de la misma. Sin embargo, no permite que haya vértices que puedan ser añadidos o suprimidos del grafo, debido a que la dimension del grafo debe ser predeterminadoa y fija. Para solucionar esto se puede usar una lista de listas de adyacencia. Sólo los vértices del grafo que sean origen de algun arco aparecerán en la lista. De esta forma se pueden añadir y suprimir arcos sin desperdicio de memoria ya que simplemente habrá que modificar la lista de listas para reflejar los cambios.

Como puede verse en el ejemplo de las figuras anteriores tanto el vector de listas de adyacencias como en la lista de listas se ha razonado en función de los vértices que actúan como origenes de los arcos. Análogamente se podía haber hecho con lod vertices destino, y combinando ambas representaciones podría pensarse en utilizar dos vectores de listas de adyacencia o dos listas de listas de adyacencia.

REPRESENTACION PROPUESTA.

La elección de una estructura idónea para representar el TDA grafo no es una tarea fácil ya que existen dos representaciones totalmente contrapuestas: por un lado tenemos la matriz de adyacencias que es muy eficiente para comprobar si existe una arista uniendo dos vertices peero que sin embargo desperdicia una gran cantidad de espacio si el grafo no es completo o esta lejos de serlo, además no tiene la posibilidad de añadir nuevos vértices; y por otra parte está la lista de adyacencias que no tiene el problema de la anterior respecto al espacio pero que sin embargo no es tan eficiente a la hora de ver si existe una arista entre dos nodos determinados.

Teniendo en cuenta estas consideraciones se ha optado por realizar una mezcla de ambas representaciones intentando aprovechar de alguna forma las ventajas que ambas poseen. Por otra parte siguiendo con la idea de tratar tanto los grafos dirigidos como los no dirigidos bajo una misma estructura, la estructura elegida posee dos apariencias ligeramente diferentes para tratar de forma adecuada cada uno de estos dos tipos de grafos.

La estructura consiste (en el caso de que tengamos un grafo dirigido en una lista de vértices donde cada uno de estos posee dos listas, una de aristas incidentes a él y otra de adyacentes. Cada vez que se añade una arista al grafo se inserta en la lista de aristas adyacentes del vertice origen y en la de incidentes del vértice destino. De esta forma la estructura desplegada se asemejaría a una matriz de adyacencia en la cual hay una arista por cada 1 y el índice de la matriz es la posición dentro de la lista de vertices.

Graficamente la estructura para un grafo dirigido queda como se puede apreciar en la siguiente figura.El puntero que de la estructura arco que apunta al destino se ha sustituido por la etiqueta del nodo destino en el grafico para simplificarlo y hacerlo mas claro.

Esta estructura no seria la mas idonea si trabajamos con solo con grafos no dirigidos ya que por cada arista no dirigida tendriamos que insertar en la estructura una misma arista dirigida repetida dos veces (una con un vértice como origen y el otro como destino y al contrario). En muchos problemas si asumimos el desperdicio de espacio podria , de todas formas, resultar interesante representar un grafo no dirigido como un grafo dirigido simetrico, el problema se preesenta cuando al tener dos aristas dirigidas esto supone la presencia de un ciclo en el grafo que realmente no existe.

Teniendo en cuenta el razonamiento anterior, en el caso de que queramos manejar grafos no dirigido la estructura consistiria en tener una lista de adyacencia para cada uno de los vertices pero tratando aquellas aristas que aparecen en la lista de adyacencia de dos vertices distintos y que unen ambos vértices como una única arista lógica (a estas dos aristas que forman una misma arista lógica las llamaremos aristas gemelas).

Estructuras Internas.

Esta representacion tiene tres estructuras diferenciadas:

• Estructura correspondiente a un vértice.
  
  
  • nodo: Codigo interno que permite numerar los nodos de 1 a n.
  • etiq: Puntero a caracter en el que se encuentra la información que posee ese vértice, es decir su etiqueta.
  • ady: Es un puntero a una lista que contiene las aristas que tienen como origen ese vértice.
  • inc: Es un puntero a una lista que contiene las aristas que tienen como destino ese vértice (solo para grafos dirigidos).
  • sig: Es un puntero que apunta al vértice que ocupa la posicion siguiente dentro de la lista de vertices.
  
  
  
• Estructura básica del grafo.
  
  En realidad se usa la misma estructura que para los nodos pero poniendo los campos etiq, ady y sig a NULL. Los dos campos restantes contienen:
  • nodo: Contien el número de nodos del grafo.
  • sig: Es un puntero que apunta al vértice que ocupa la primera posicion dentro de la lista de vertices.
  
  
  
• Estructura correspondiente a una arista (grafo dirigido).
  
  
  • origen: Es un puntero al vértice que es el origen de esa arista.
  • destino: Es un puntero al vértice que es el destino de esa arista.(Nosotros hemos sustituido el puntero por la etiqueta del nodo destino para mayor claridad del dibujo).
  • valor: Este campo contiene el peso de la arista que sera un numero entero.
  • sig: Puntero que apunta a la siguente arista dentro de la lista de aristas adyacentes o incidentes.

Estructuras Internas del TDA grafo.

/* Implementacion basada en una lista de nodos de los que cuelga */
/* la lista de arcos de salida.                                  */

#include 
#include 
#include 

#define TE 5
#define Nulo NULL

typedef char  *tetq;
typedef float tvalor;

typedef struct arco {
	struct nodo *origen;
	struct nodo *destino;
	tvalor valor;
	struct arco *sig;
} *tarco;

typedef struct nodo {
	int nodo;
	tetq etiq;
	tarco ady;
	tarco inc;
	struct nodo *sig;
} *tnodo;

typedef tnodo tgrafo;

5. IMPLEMENTACIÓN DE EL TDA GRAFO.

LISTA DE PRIMITIVAS.

Lista de primitivas para los grafos dirigidos:

• Crear: Función que se encarga de crear un grafo vacio.
• Etiqueta: Funcion que devuelve la etiqueta asociada a un nodo en un grafo.
• Label: Funcion que devuelve la Label de un nodo en el grafo.
• LocalizaLabel: Esta función recibe el entero l (el label asociado a un nodo que se supone pertenece al grafo y nos devuelve el nodo asociado con esa label.
• ExisteArco: Función que devuelve 1 si existe un arco entre el nodo o y el nodo d en el grafo g, si no existe dicho arco devuelve 0.
• PrimerArco: Devuelve el primer arco que sale del nodo n en el grafo g, si no existe dicho primer arco devuelve Nulo.
• SiguienteArco: Función que devuelve el arco siguiente al arco a en el nodo n si no existe dicho arco devuelve Nulo.
• PrimerArcoInv: Devuelve el primer arco que entra en el nodo n en el grafo g. Si no existe dicho arco devuelve Nulo.
• SiguienteArcoInv: Devuelve el siguiente arco tras a que entra en el nodo n, si no existe dicho arco devuelve Nulo.
• PrimerNodo: Devuelve el primer nodo del grafo G, si no existe devuelve nulo.
• SiguienteNodo: Devuelve el nodo siguiente en orden al nodo n en el grafo g. Si no existe devuelve nulo.
• NodoOrigen: Devuelve el nodo origen del arco a.
• NodoDestino: Devuelve el nodo destino del arco a.
• presentarGrafo: Escribe el grafo g en pantalla.
• NumeroNodos: Devuelve el numero de nodos de un grafo g.
• grafoVacio: Devuelve Nulo si el grafo esta vacio.
• EtiqArco: Funcion que devuelve la etiqueta asociada a un arco, es decir el peso del arco.
• InsertarNodo: Funcion que inserta un nodo nuevo en un grafo.
• InsertarArco: Funcion que se encarga de insertar un arco entre el nodo org y el dest en el grafo g, asociado al arco le podemos dar un valor.
• BorrarArco: Funcion que borra el arco existente entre los nodos org y dest.
• DesconectarNodo: Función que devuelve el grafo que se obtiene al eliminar un nodo de un grafo G.Todos los arcos que entran o salen del nodo a eliminar tambien desaparecen.
• Destruir: Funcion que destruye el grafo g liberando la memoria que ocupa.
• CopiarGrafo: Funcion que hace una copia del grafo g.

IMPLEMENTACIÓN DE LAS PRIMITIVAS.

tgrafo Crear(void)
    
    

{
   tnodo aux;
   
   aux = (tnodo)malloc(sizeof(struct nodo));
   if (aux == NULL) {
      error(\"Error en Crear.\");
   } else {
      aux->nodo = 0;
	  aux->etiq = NULL;
	  aux->ady  = NULL;
	  aux->inc  = NULL;
	  aux->sig  = NULL;
	  return aux;
   }
}

tetiq Etiqueta(tnodo n, tgrafo g)
    
    

{
   return(n->etiq);
}

int Label(tnodo n, tgrafo g)
    
    

{
   return(n->nodo);
}

tnodo LocalizaLabel(int l, tgrafo g)
    
    

{
   tnodo  n;
   int enc=0;

   for (n=g->sig; n!=NULL && !enc; ) {
      if (n->nodo == l)
         enc = 1;
      else
         n = n->sig;
   }
   return n;
}

int ExisteArco(tnodo o, tnodo  d, tgrafo g)
    
    

{
   tarco  a;

   a=o->ady;
   while (a!=NULL) {
      if ((a->origen==o) && (a->destino==d))
         return 1;
      else
         a = a->sig;
   }
   return 0;
}

tarco PrimerArco(tnodo n, tgrafo g)
    
    

{
   return(n->ady);
}

tarco SiguienteArco(tnodo n, tarco a, tgrafo g)
    
    

{
   return(a->sig);
}

tarco PrimerArcoInv(tnodo n, tgrafo g)
    
    

{
   return(n->inc);
}

tarco SiguienteArcoInv(tnodo n, tarco a, tgrafo g)
    
    

{
   return(a->sig);
}

tnodo PrimerNodo(tgrafo g)
    
    

{
   return(g->sig);
}

tnodo SiguienteNodo(tnodo n, tgrafo g)
    
    

{
   return(n->sig);
}

tnodo NodoOrigen(tarco a, tgrafo g)
    
    

{
   return(a->origen);
}

tnodo NodoDestino(tarco a, tgrafo g)
    
    

{
   return(a->destino);
}

void PresentarGrafo(tgrafo g)
    
    

{
   tnodo n;
   tarco a;

   n=PrimerNodo(g);
   while (n!=Nulo) {
      a=PrimerArco(n,g);
      while (a!=Nulo) {
         printf(\"%s -> %s \",a->origen->etiq,a->destino->etiq);
         printf(\" (%f)\\n\",a->valor);
         a=SiguienteArco(n,a,g);
      }
      n=SiguienteNodo(n,g);
   }
}

int NumeroNodos(tgrafo g)
    
    

{
   return(g->nodo);
}

int GrafoVacio(tgrafo g)
    
    

{
   return(g->sig == NULL);
}

float EtiqArco(tnodo o, tnodo d, tgrafo g)
    
    

{
   tarco a;

   a=o->ady;
   while (a!=NULL) {
      if ((a->origen == o) && (a->destino == d))
         return (a->valor);
      else
         a = a->sig;
   }
   return 0;
}

void InsertarNodo(tetq dato, tgrafo g)
    
    

{
   tnodo aux,p;

   aux = (tnodo)malloc(sizeof(struct nodo));
   if (aux == NULL)
      error(\"Error Memoria Insuficiente.\");
   else {
      p=g;
      while(p->sig != NULL) 
         p = p->sig;
      aux->etiq = (char *)malloc(sizeof (char)*TE);"+
      if (aux->etiq == NULL)
         error(\"Error Memoria Insuficiente.\");
      aux->nodo = p->nodo+1;
      strcpy(aux->etiq,dato);+
      aux->ady = NULL;
      aux->inc = NULL;
      aux->sig = NULL;
      p->sig = aux;
      g->nodo++;
   }
}

void InsertarArco (tnodo org,tnodo dest,tvalor valor,tgrafo g)
{
   tarco aux;
   tarco aux_inv;

   aux = (tarco)malloc(sizeof(struct arco));
   aux_inv=	(tarco)malloc(sizeof(struct arco));
   if ((aux==NULL) || (aux_inv==NULL))
	  error("Memoria Insuficiente.");
   else {
	  aux->origen = org;
	  aux->destino = dest;
	  aux->valor = valor;
	  aux-> sig= org->ady;
	  org->ady = aux;

	  aux_inv->origen = org;
	  aux_inv->destino = dest;
	  aux_inv-> valor= valor;
	  aux_inv-> sig= dest->inc;
	  des_inc-> = aux_inv;
   }
}

void BorrarArco(tnodo org, tnodo dest, tgrafo g) 
{
   tarco a,ant;
   int enc=0;
   
   if (org->ady==NULL) return;
   else if (org->ady->destino==dest) {
	  a = org->ady;
	  org->ady = a->sig;
	  free(a);
   } 
   else {
      ant = org->ady;
      a = ant->sig;
      while (!enc && (a!=NULL)) {
	     if (a->destino==dest) enc=1;
         else {
            a = a->sig;
			ant = ant->sig;
         }
      }
      if (a==NULL) return;
      else {
         ant->sig = a->sig;
         free(a);
      }		
   }

   enc=0;
   if (dest->inc==NULL) return;
   else if (dest->inc->origen==org) {
     a = dest->inc;
	 dest->inc = a->sig;
     free(a);	
   }
   else {
     ant = dest->inc;
     a = ant->sig;
     while (!enc && (a!=NULL)) {
       if (a->origen == org) enc=1;
	   else {
         a = a->sig;
		 ant = ant->sig;
       }	
     }
     if (a==NULL) return;
     else {
       ant->sig = a->sig;
       free(a);
	 }
   }
}

void Destruir(tgrafo G) 
{
   tnodo n;
   tarco a_aux;

   while (g->sig != NULL) {
      n = g->sig;
	  while (n->ady	!= NULL) {
		a_aux = n->ady;
		n->ady = a_aux->sig;
        free(a_aux);
      }
	  while (n->inc != NULL) {
         a_aux = n->inc;
		 n->inc = a_aux->sig;
         free(a_aux);   
	  }		
	  g->sig = n->sig;
      free(n->etiq);
      free(n);
   }	
   free(g);
}

tgrafo DesconectarNodo(tnodo a_eliminar,tgeafo g)
{
   tgrafo g_nd;
   tnodo n;
   tnodo org;dst;
   tnodo o,d;
   tarco a;

   g_nd = Crear();
   for (n=PrimerNodo(g); n!=NULL; n=SiguienteNodo(n,g))
	  InsertarNodo(Etiqueta(n,g),g_nd);

   for (n=PrimerNodo(g); n!=NULL; n=SiguienteNodo(n,g))
	 for (a=PrimerArco(n,g); a!=NULL; a=SiguienteArco(n,a,g)) {
		org = NodoOrigen(a,g);
		dst = NodoDestino(a,g);
        if ((org!=a_eliminar) && dst!=a_eliminar)) {
     	   o = LocalizaLabel(Label(org,g), g_nd);
		   d = LocalizaLabel(Label(dst,g), g_nd);
		   InsertarArco(o,d,g_nd);		
        }
     }
	 return g_nd;
}

tgrafo CopiarGrafo(tgrafo g) 
{
   tgrafo g_nd;
   tnodo n;
   tnodo org;dst;
   tnodo o,d;
   tarco a;
   int lb;

   g_nd = Crear();
   for (n=PrimerNodo(g); n!=NULL; n=SiguienteNodo(n,g))
	  InsertarNodo(Etiqueta(n,g),g_nd);
   	
   for (n=PrimerNodo(g); n!=NULL; n=SiguienteNodo(n,g))
	 for (a=PrimerArco(n,g); a!=NULL; a=SiguienteArco(n,a,g)) {
		org = NodoOrigen(a,g);
		dst = NodoDestino(a,g);
            o = LocalizaLabel(Label(org,g), g_nd);
		d = LocalizaLabel(Label(dst,g), g_nd);
		InsertarArco(o,d,g_nd);		
     }
   }
   return g_nd;	
   	
}