domingo, 17 de mayo de 2009

Grafos



GRAFO






Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
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 terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).
Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las
ciencias exactas y las ciencias sociales.


Historia y problema de los puentes de Königsberg


El primer artículo científico relativo a grafos fue escrito por el matemático suizo Leonhard Euler en 1736. Euler se basó en su artículo en el problema de los puentes de Königsberg. La ciudad de Kaliningrado, originalmente Königsberg, es famosa por sus siete puentes que unen ambas márgenes del río Pregel con dos de sus islas. Dos de los puentes unen la isla mayor con la margen oriental y otros dos con la margen occidental. La isla menor está conectada a cada margen por un puente y el séptimo puente une ambas islas. El problema planteaba lo siguiente: ¿es posible, partiendo de un lugar arbitrario, regresar al lugar de partida cruzando cada puente una sola vez?
Abstrayendo este problema y planteándolo con la (entonces aún básica) teoría de grafos, Euler consigue demostrar que el grafo asociado al esquema de puentes de Königsberg no tiene solución, es decir, no es posible regresar al vértice de partida sin pasar por alguna arista dos veces.
De hecho, Euler resuelve el problema más general: ¿qué condiciones debe satisfacer un grafo para garantizar que se puede regresar al vértice de partida sin pasar por la misma arista más de una vez?


Definiciones
Un grafo G es un
par ordenado G = (V,E), donde:
V es un
conjunto de vértices o nodos, y
E es un conjunto de arcos o aristas, que
relacionan estos nodos.
Normalmente V suele ser
finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos. Se llama orden de G a su número de vértices, V .

Lazos o bucles
Un lazo o bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.


Grafo no dirigido

Un grafo no dirigido o grafo propiamente dicho es un grafo G = (V,E) donde:

es un conjunto de pares no ordenados de elementos.
Un par no ordenado es un conjunto de la forma {a,b}, de manera que {a,b} = {b,a}. Para los grafos, estos conjuntos pertenecen al
conjunto potencia de V de cardinalidad 2.


Grafo dirigido

Un grafo dirigido o digrafo es un grafo G = (V,E) donde:

es un conjunto de
pares ordenados de elementos-.
Dada una arista (a,b), a es su nodo inicial y b su nodo final.
Por definición, los grafos dirigidos no contienen bucles.

Pseudografo
Un pseudografo es un grafo G = (V,E) donde:

es un conjunto de pares no ordenados de elementos.
Es decir, un pseudografo es un grafo no dirigido que acepta bucles

Pseudografo dirigido
Un pseudografo dirigido es un grafo G = (V,E) donde:

es un conjunto de pares ordenados y etiquetados de elementos de
Es decir, un pseudografo dirigido es un grafo dirigido que acepta bucles.

Variantes sobre las definiciones principales
Algunas aplicaciones requieren extensiones más generales a las dos propuestas clásicas de grafos. Aunque la definición original los permite, según la aplicación concreta pueden ser válidos o no. A veces V o E pueden ser un
multiconjunto, pudiendo haber más de una arista entre cada par de vértices. La palabra grafo (a secas) puede permitir o no múltiples aristas entre cada par de vértices, dependiendo del autor de la referencia consultada. Si se quiere remarcar la inexistencia de múltiples aristas entre cada par de vértices (y en el caso no dirigido, excluir bucles) el grafo puede llamarse simple. Por otra parte, si se quiere asegurar la posibilidad de permitir múltiples aristas, el grafo puede llamarse multigrafo (a veces se utiliza el término pseudografo para indicar que se permiten tanto bucles como múltiples aristas entre cada par de vértices).

Propiedades
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 (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para problemas de optimización, como el del
vendedor viajero o del camino más corto.
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 importantes
Existen grafos que poseen propiedades destacables. Algunos ejemplos básicos son:
Grafo nulo o vacío: aquel que no tiene vértices ni aristas. Nótese que algunas personas exijen que el conjunto de vértices no sea vacío en la definición de grafo.
Grafo trivial: aquel que tiene un vértice y ninguna arista.
Grafo simple: aquel que no posee
bucles.
Grafo completo: grafo simple en el que cada par de vértices están unidos por una arista, es decir, contiene todas las posibles aristas.
Grafo bipartito completo: sea (W,X) una partición del conjunto de vértices V, es aquel donde cada vértice en W es adyacente sólo a cada vértice en X, y viceversa.
Grafo bipartito: sea (W,X) una partición del conjunto de vértices V, es aquel donde cada arista tiene un vértice en W y otro en X.
Grafo planar o plano: aquel que puede ser dibujado en el plano cartesiano sin cruce de aristas.
Árbol: grafo conexo sin ciclos.
Algunos ejemplos más avanzados son:
Los
grafos de Petersen y sus generalizaciones.
Los
grafos perfectos.
Los
cografos.
Los
grafos de Cayley.
Los
grafos fuertemente regulares y su generalización en grafos de distancia regular.
Una generalización de los grafos son los llamados
hipergrafos.
EJEMPLO:

import adts.*;
import java.util.*;
/**
* Clase que contiene algoritmos de caminos minimos en grafos
*/
public class Caminos
{

/**
* Algoritmo del calculo del camino minimo sin pesos
*/
public static CaminoSinPesos caminoMinimoSinPesos
(Grafo g, int origen, int destino) throws NoExiste,IdIncorrecto
{
// inicializaciones
LinkedList procesar= new LinkedList();
int[] anterior= new int[g.numVertices()];
boolean[] visitado= new boolean[g.numVertices()];
// todas las casillas valen vale false por omision en Java
procesar.addLast(new Integer(origen));
visitado[origen]=true;
anterior[origen]=-1; // para indicar que no tiene
while (!procesar.isEmpty()) {
int v=procesar.removeFirst().intValue();
List> adj=g.listaAristas(v);
for (Arista a:adj) {
int dest=a.destino();
if (!visitado[dest]) {
anterior[dest]=v;
if (dest==destino) {
// hemos encontrado el camino minimo
return caminoDe(origen,destino,anterior,g);
}
visitado[dest]=true;
procesar.addLast(dest);
}
}
}
// el destino no ha sido hallado)
throw new adts.NoExiste();
}
/**
* Metodo para formar el camino sin pesos
*/
private static CaminoSinPesos caminoDe(int origen, int destino,
int[] anterior, Grafo g)
{
CaminoSinPesos cam= new CaminoSinPesos(g);
int v=destino;
while (anterior[v]!=-1) {
cam.inserta(v);
v=anterior[v];
}
cam.inserta(origen);
return cam;
}
/**
* Clase interna para los objetos a almacenar en la cola de
* prioridad en el algoritmo del camino minimo con pesos
*/
static class SubCamino implements Comparable {
int dest;
double peso;
SubCamino (int dest, double peso) {
this.dest=dest;
this.peso=peso;
}
public int compareTo(SubCamino otro) {
if (this.pesoreturn -1;
} else if (this.peso>otro.peso) {
return 1;
} else {
return 0;
}
}
}
/**
* Algoritmo del calculo del camino minimo con pesos
*/
public static CaminoConPesos caminoMinimoConPesos
(Grafo g, int origen, int destino) throws NoExiste, IdIncorrecto
{
// inicializaciones
PriorityQueue procesar= new PriorityQueue();
int[] anterior= new int[g.numVertices()];
double[] peso= new double[g.numVertices()];
boolean[] procesado= new boolean[g.numVertices()];
// valor por omision es false para todas sus casillas
// dar valor infinito a todas las casillas de peso
for (int i=0; ipeso[i]=Double.POSITIVE_INFINITY;
}
procesar.add(new SubCamino(origen,0.0));
peso[origen]=0.0; // para no hacer ciclos
anterior[origen]=-1; // para indicar que no tiene
// bucle para procesar vertices
while (! procesar.isEmpty()) {
int v=procesar.remove().dest;
if (! procesado[v]) {
procesado[v]=true;
List> adj=g.listaAristas(v);
for (Arista a: adj) {
int dest=a.destino();
double p=a.contenido().doubleValue();
if (peso[dest]>peso[v]+p) {
anterior[dest]=v;
peso[dest]=peso[v]+p;
procesar.add(new SubCamino(dest,peso[dest]));
}
} // for
} // if
} // while
if (Double.isInfinite(peso[destino])) {
throw new NoExiste();
} else {
return caminoDe(origen,destino,anterior,peso[destino],g);
}
}
/**
* Metodo para formar el camino con pesos
*/
private static CaminoConPesos caminoDe(int origen, int destino,
int[] anterior, double peso, Grafo g)
{
CaminoConPesos cam= new CaminoConPesos(g,peso);
int v=destino;
while (anterior[v]!=-1) {
cam.inserta(v);
v=anterior[v];
}
cam.inserta(origen);
return cam;
}
/**
* Algoritmo del calculo del camino minimo con pesos negativos
*/
public static CaminoConPesos caminoMinimoConPesosNegativos
(Grafo g, int origen, int destino)
throws NoExiste, IdIncorrecto, CicloNegativo
{
// inicializaciones
LinkedList procesar= new LinkedList();
int numVertices=g.numVertices();
int[] anterior= new int[numVertices];
double[] peso= new double[numVertices];
int[] visitado= new int[numVertices];
// valor por omision es 0 para todas sus casillas
boolean[] estaEnLaCola= new boolean[numVertices];
// valor por omision es false para todas sus casillas
// dar valor infinito a todas las casillas de peso
for (int i=0; ipeso[i]=Double.POSITIVE_INFINITY;
}
procesar.addLast(new Integer(origen));
peso[origen]=0.0; // para no hacer ciclos
anterior[origen]=-1; // para indicar que no tiene
visitado[origen]++;
// bucle para procesar vertices
while (! procesar.isEmpty()) {
int v=procesar.removeFirst().intValue();
estaEnLaCola[v]=false;
List> adj=g.listaAristas(v);
for (Arista a: adj) {
int dest=a.destino();
double p=a.contenido().doubleValue();
if (peso[dest]>peso[v]+p) {
visitado[dest]++;
if (visitado[dest]>numVertices) {
throw new CicloNegativo();
}
anterior[dest]=v;
peso[dest]=peso[v]+p;
if (!estaEnLaCola[dest]) {
estaEnLaCola[dest]=true;
procesar.addLast(new Integer(dest));
}
}
} // for
} // while
if (Double.isInfinite(peso[destino])) {
throw new NoExiste();
} else {
return caminoDe(origen,destino,anterior,peso[destino],g);
}
}
/**
* Calcular el grado de entrada, para el orden topologico
*/
private static int[] calculaGradoEntrada(Grafo g) {
try {
int[] grado= new int[g.numVertices()];
// en Java, todas las casillas valen 0 por omision
for (int v=0; vList> ady=g.listaAristas(v);
for (Arista a: ady) {
grado[a.destino()]++;
}
}
return grado;
} catch (IdIncorrecto e) {
System.out.println("Error inesperado "+e);
return null;
}
}
/**
* Mostrar los vertices del grafo en un orden topologico
*/
public static void ordenTopologico(Grafo g) throws HayCiclos
{
try {
int[] grado= calculaGradoEntrada(g);
LinkedList procesar = new LinkedList();
int procesados=0;
// insertar en la cola vertices de grado cero
for (int v=0; vif (grado[v]==0) {
procesar.addLast(new Integer(v));
}
}
// bucle principal
while (!procesar.isEmpty()) {
procesados++;
int v=procesar.removeFirst().intValue();
System.out.print(g.contenido(v)+" ");
// procesar las aristas de v
List> ady=g.listaAristas(v);
for (Arista
a: ady) {
int dest=a.destino();
grado[dest]--;
if (grado[dest]==0) {
procesar.addLast(new Integer(dest));
}
}
}
if (procesados!=g.numVertices()) {
throw new HayCiclos();
}
System.out.println();
} catch (IdIncorrecto e) {
System.out.println("Error inesperado "+e);
}
}
/**
* Calcular el camino minimo en un grafo aciclico
*/
public static CaminoConPesos caminoMinimoAciclico
(Grafo g, int origen, int destino)
throws NoExiste, IdIncorrecto, HayCiclos
{
// inicializaciones
int anterior[]= new int[g.numVertices()];
double[] peso= new double[g.numVertices()];
// dar valor infinito a todas las casillas de peso
for (int i=0; ipeso[i]=Double.POSITIVE_INFINITY;
}
peso[origen]=0.0; // para no hacer ciclos
anterior[origen]=-1; // para indicar que no tiene
int[] grado= calculaGradoEntrada(g);
LinkedList procesar = new LinkedList();
int procesados=0;
// insertar en la cola vertices de grado cero
for (int v=0; vif (grado[v]==0) {
procesar.addLast(new Integer(v));
}
}
// bucle principal
while (!procesar.isEmpty()) {
procesados++;
int v=procesar.removeFirst().intValue();
// procesar las aristas de v
List> ady=g.listaAristas(v);
for (Arista a: ady) {
int dest=a.destino();
grado[dest]--;
if (grado[dest]==0) {
procesar.addLast(new Integer(dest));
}
if (!Double.isInfinite(peso[v])) {
double p=a.contenido().doubleValue();
if (peso[dest]>peso[v]+p) {
anterior[dest]=v;
peso[dest]=peso[v]+p;
}
}
}
}
if (procesados!=g.numVertices()) {
throw new HayCiclos();
}
if (Double.isInfinite(peso[destino])) {
throw new NoExiste();
} else {
return caminoDe(origen,destino,anterior,peso[destino],g);
}
}
}

import adts.*;
/**
* Prueba del camino minimo con pesos
*/
public class PruebaAciclico
{
public static void main (String[] args) {
// ejemplo de la figura 14.18
Grafo g= new GrafoAdyacencia();
g.nuevaArista("V2","V0",4.0);
g.nuevaArista("V2","V5",5.0);
g.nuevaArista("V0","V1",2.0);
g.nuevaArista("V0","V3",1.0);
g.nuevaArista("V2","V3",2.0);
g.nuevaArista("V3","V5",8.0);
g.nuevaArista("V3","V6",4.0);
g.nuevaArista("V3","V4",2.0);
g.nuevaArista("V1","V3",3.0);
g.nuevaArista("V1","V4",10.0);
g.nuevaArista("V4","V6",6.0);
g.nuevaArista("V6","V5",1.0);
OpGrafos.muestra(g);

System.out.println();
try {
Caminos.ordenTopologico(g);
CaminoConPesos cam=Caminos.caminoMinimoAciclico
(g,g.idVertice("V2"), g.idVertice("V6"));
cam.muestra();
cam=Caminos.caminoMinimoAciclico
(g,g.idVertice("V2"), g.idVertice("V5"));
cam.muestra();
cam=Caminos.caminoMinimoAciclico
(g,g.idVertice("V2"), g.idVertice("V4"));
cam.muestra();
cam=Caminos.caminoMinimoAciclico
(g,g.idVertice("V5"), g.idVertice("V4"));
cam.muestra();
} catch (IdIncorrecto e) {
System.out.println("Se ha lanzado IdIncorrecto");
} catch (NoExiste e) {
System.out.println("Se ha lanzado NoExiste");
} catch (HayCiclos e) {
System.out.println("Se ha lanzado HayCiclos");
}
}
}

import adts.*;
/**
* Prueba del camino minimo con pesos negativos
*/
public class PruebaCaminosConPesosNegativos
{
public static void main (String[] args) {
// ejemplo de la figura 14.18
Grafo g= new GrafoAdyacencia();
g.nuevaArista("V2","V0",4.0);
g.nuevaArista("V2","V5",5.0);
g.nuevaArista("V0","V1",1.0);
g.nuevaArista("V0","V3",2.0);
g.nuevaArista("V3","V2",2.0);
g.nuevaArista("V3","V5",8.0);
g.nuevaArista("V3","V6",4.0);
g.nuevaArista("V3","V4",2.0);
g.nuevaArista("V1","V3",3.0);
g.nuevaArista("V1","V4",-10.0);
//g.nuevaArista("V4","V1",-10.0);
g.nuevaArista("V4","V6",6.0);
g.nuevaArista("V6","V5",1.0);
System.out.println();
try {
CaminoConPesos cam=Caminos.caminoMinimoConPesosNegativos
(g,g.idVertice("V2"), g.idVertice("V6"));
cam.muestra();
cam=Caminos.caminoMinimoConPesosNegativos
(g,g.idVertice("V2"), g.idVertice("V5"));
cam.muestra();
cam=Caminos.caminoMinimoConPesosNegativos
(g,g.idVertice("V2"), g.idVertice("V4"));
cam.muestra();
cam=Caminos.caminoMinimoConPesosNegativos
(g,g.idVertice("V5"), g.idVertice("V4"));
cam.muestra();
} catch (IdIncorrecto e) {
System.out.println("Se ha lanzado IdIncorrecto");
} catch (NoExiste e) {
System.out.println("Se ha lanzado NoExiste");
} catch (CicloNegativo e) {
System.out.println("Se ha lanzado CicloNegativo");
}
}
}

import adts.*;
/**
* Write a description of class PruebaCaminos here.
*
* @author (your name)
* @version (a version number or a date)
*/
public class PruebaCaminos
{
public static void main (String[] args) {
// ejemplo de la figura 14.18
Grafo g= new GrafoAdyacencia();
g.nuevaArista("V2","V0",1.0);
g.nuevaArista("V2","V5",1.0);
g.nuevaArista("V0","V1",1.0);
g.nuevaArista("V0","V3",1.0);
g.nuevaArista("V3","V2",1.0);
g.nuevaArista("V3","V5",1.0);
g.nuevaArista("V3","V6",1.0);
g.nuevaArista("V3","V4",1.0);
g.nuevaArista("V1","V3",1.0);
g.nuevaArista("V1","V4",1.0);
g.nuevaArista("V4","V6",1.0);
g.nuevaArista("V6","V5",1.0);
System.out.println();
try {
CaminoSinPesos cam=Caminos.caminoMinimoSinPesos
(g,g.idVertice("V2"), g.idVertice("V6"));
cam.muestra();
cam=Caminos.caminoMinimoSinPesos
(g,g.idVertice("V2"), g.idVertice("V5"));
cam.muestra();
cam=Caminos.caminoMinimoSinPesos
(g,g.idVertice("V2"), g.idVertice("V4"));
cam.muestra();
cam=Caminos.caminoMinimoSinPesos
(g,g.idVertice("V5"), g.idVertice("V4"));
cam.muestra();
} catch (IdIncorrecto e) {
System.out.println("Se ha lanzado IdIncorrecto");
} catch (NoExiste e) {
System.out.println("Se ha lanzado NoExiste");
}
}
}

import java.util.*;
import adts.*;
/**
* Write a description of class PruebaGrafos here.
*
* @author (your name)
* @version (a version number or a date)
*/
public class PruebaGrafos
{
public static void main (String args[])
{
Grafo elGrafo = new GrafoAdyacencia();
System.out.println("Creamos un grafo vacio");
System.out.println("El numero de vertices es " + elGrafo.numVertices());
System.out.println("El numero de aristas es " + elGrafo.numVertices());
System.out.println("");
System.out.println("Anadimos 7 vertices y 11 aristas");
elGrafo.nuevaArista(0,1,1);
elGrafo.nuevaArista(0,3,2);
elGrafo.nuevaArista(1,3,3);
elGrafo.nuevaArista(1,4,10);
elGrafo.nuevaArista(2,0,4);
elGrafo.nuevaArista(2,5,5);
elGrafo.nuevaArista(3,2,2);
elGrafo.nuevaArista(3,4,2);
elGrafo.nuevaArista(3,5,8);
elGrafo.nuevaArista(3,6,4);
elGrafo.nuevaArista(4,6,6);
System.out.println("El numero de vertices es " + elGrafo.numVertices());
System.out.println("El numero de aristas es " + elGrafo.numAristas());
System.out.println("");
System.out.println("Recorremos todas las aristas del grafo");
for (int i=0; i<=elGrafo.numVertices()-1; i++)
{
try
{
List> lasAristas = elGrafo.listaAristas(i);
System.out.println("Aristas del vertice "+i+" cuyo contenido es "+elGrafo.contenido(i));
for (Arista a:lasAristas) {
System.out.println(" Origen: "+a.origen()+" Destino: "+a.destino()+" Peso: "+a.contenido());
}
} catch (IdIncorrecto e) {
System.out.println("El vertice no existe");
}
}
System.out.println("");
elGrafo.nuevaArista(6,5,1);
System.out.println("Anadimos una nueva arista");
System.out.println("El numero de aristas es " + elGrafo.numAristas());
System.out.println("Recorremos todas las aristas del grafo");
for (int i=0; i<=elGrafo.numVertices()-1; i++)
{
try
{
List> lasAristas = elGrafo.listaAristas(i);
System.out.println("Aristas del vertice "+i+" cuyo contenido es "+elGrafo.contenido(i));
for (Arista a:lasAristas) {
System.out.println(" Origen: "+a.origen()+" Destino: "+a.destino()+" Peso: "+a.contenido());
}
} catch (IdIncorrecto e) {
System.out.println("El vertice no existe");
}
}
try
{
System.out.println("El id del vertice con contenido 5 es :");
System.out.println(elGrafo.idVertice(new Integer(5)));
System.out.println("El id del vertice con contenido 9 es :");
System.out.println(elGrafo.idVertice(new Integer(9)));
} catch (NoExiste e) {
System.out.println("El vertice no existe");
}
System.out.println("");
try
{
System.out.println("El contenido del vertice con id 5 es :");
System.out.println(elGrafo.contenido(5));
System.out.println("El id del vertice con id 9 es :");
System.out.println(elGrafo.contenido(9));
} catch (IdIncorrecto e) {
System.out.println("El vertice no existe");
}
System.out.println("");
System.out.println("Tratamos de acceder a las aristas de un vertice inexistente");
try
{
List> lasAristas = elGrafo.listaAristas(9);
} catch (IdIncorrecto e) {
System.out.println("El vertice no existe");
}
}
}

import java.util.*;
import adts.*;
/**
* Operaciones con los grafos
*/
public class OpGrafos
{
/**
* Mostrar el grafo en pantalla
*/
public static void muestra(Grafo g) {
try {
System.out.println();
System.out.println("------------Grafo---------");
for (int i=0; iSystem.out.print(g.contenido(i)+" - ");
List> lista=g.listaAristas(i);
for (Arista
a:lista) {
System.out.print(g.contenido(a.destino())+"("+
a.contenido()+") ");
}
System.out.println();
}
} catch (IdIncorrecto e) {
System.out.println("Error inesperado: "+e);
}
}
/**
* Calcular el peso de un camino
*/
public static double calculaPeso(V[] camino, Grafo g)
throws NoExiste
{
try {
// Convertir los vértices a identificadores
int[] ruta=new int[camino.length];
for (int i=0; iruta[i]=g.idVertice(camino[i]);
}
// Calcular el peso
double pesoTotal=0;
for (int v=0; vList> ady=g.listaAristas(ruta[v]);
boolean encontrado=false;
// buscar la arista que llega a v+1
for (Arista a:ady) {
if (a.destino()==ruta[v+1]) {
encontrado=true;
pesoTotal=pesoTotal+a.contenido();
break;
}
}
if (!encontrado) {
throw new NoExiste();
}
}
return pesoTotal;
} catch (IdIncorrecto e) {
System.out.println("Error inesperado "+e);
throw new NoExiste();
}
}
}

import adts.*;
/**
* Prueba del camino minimo con pesos
*/
public class PruebaCaminosConPesos
{
public static void main (String[] args) {
// ejemplo de la figura 14.18
Grafo g= new GrafoAdyacencia();
g.nuevaArista("V2","V0",4.0);
g.nuevaArista("V2","V5",5.0);
g.nuevaArista("V0","V1",2.0);
g.nuevaArista("V0","V3",2.0);
g.nuevaArista("V3","V2",2.0);
g.nuevaArista("V3","V5",8.0);
g.nuevaArista("V3","V6",4.0);
g.nuevaArista("V3","V4",2.0);
g.nuevaArista("V1","V3",3.0);
g.nuevaArista("V1","V4",10.0);
g.nuevaArista("V4","V6",6.0);
g.nuevaArista("V6","V5",1.0);
OpGrafos.muestra(g);
System.out.println();
try {
CaminoConPesos cam=Caminos.caminoMinimoConPesos
(g,g.idVertice("V2"), g.idVertice("V6"));
cam.muestra();
cam=Caminos.caminoMinimoConPesos
(g,g.idVertice("V2"), g.idVertice("V5"));
cam.muestra();
cam=Caminos.caminoMinimoConPesos
(g,g.idVertice("V2"), g.idVertice("V4"));
cam.muestra();
cam=Caminos.caminoMinimoConPesos
(g,g.idVertice("V5"), g.idVertice("V4"));
cam.muestra();
} catch (IdIncorrecto e) {
System.out.println("Se ha lanzado IdIncorrecto");
} catch (NoExiste e) {
System.out.println("Se ha lanzado NoExiste");
}
}
}

4 comentarios:

  1. Interesante articulo del tema, esta bien explicado y es bastante conciso. Eso si heche de menos algo en la sección de "historia y problema de los puentes de Köenigsberg", que cuando Euler escribió su trabajo sobre los puentes de Königsberg, que tituló "Solutio problematis ad geometriam situs pertinentis" (el latín era la lengua de moda para escribir los trabajos científicos en esa época), trato el problema desde una perspectiva algebraica que luego sería precursora conceptualmente de la topología (de aquí que no es raro que mas de algún historiador de la matemática como el estadounidense Eric Temple Bell hable de la teoría de grafos como la madre de la topología), la mención de que ese pequeño artículo fue la chispa incendiaria que originó una nueva forma de ver la continuidad y los morfismos en matemáticas. Recuerda al caso del Frances Galois, quien en su trabajo sobre agrupaciones de soluciones para polinomios dejara las bases para toda una rama abstracta que llevaría a un nuevo nivel el análisis de las algebras: los grupos. Bueno, para no explayarme más y rallar el aburrimiento, nuevamente felicitaciones por el articulo de grafos, pues como estudiante de matemáticas y aspirante a investigador lo encuentro muy acertado (ademas es mi area de estudio actualmente). Muchos saludos y exito. Au revoir.

    ResponderEliminar
  2. por cierto, cualquier comentario, queja, acotación a las opiniones vertidas anteriormente en base a su articulo, puede manifestar su parecer o malestar al mail athal.zigma@gmail.com

    Saludos y que el conjunto denso de los reales os acompañe.

    ResponderEliminar
  3. hola me parece muy interesante el tema.. pero estoy tratando de correr el codigo para entenderlo menos y mi netbeans me da error en el import adts dice que el package no se encuentra a caso es un tipo de plug in o jar que tengo que bajar a parte para poder quitarle este error? necesito respuesta urgente mi mail es dodo_48@hotmail.com en caso de que alguien tenga la respuesta y de antemano muchas gracias saludos

    ResponderEliminar
  4. hola excelente ejercicio paro al implementarlo en mi netbeans salen muchos errores me pueden ayudar por favor mi correo es juank_milo123@hotmail.com

    ResponderEliminar