GRAFOS
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.
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.
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).
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 ax.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={(v1,v2),(v2,v3),...,(vn-1,vn), para todo vi perteneciente a V}
C={(v1,v2),(v2,v3),...,(vn-1,vn), para todo vi 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 ,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.
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.
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 Bnxn
Como se ve,se asocia cada fila y cada columna a un vértice y los
elementos bi,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 Bnxn
La matriz B es simetrica con 1 en las posiciones ij y ji si
existe la arista (i,j).
Si el grafo es etiquetado,entonces tanto bi,j como bi,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 bi,j o
bi,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:
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;
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;
}
