ATENCION!

AQUI NUEVO BLOG

Bienvenidos

Vinculos:

• Grafos. Teoría e Implementación Sin vueltas
• Caminos mas cortos con un solo origen - Dijkstra
• Todos los caminos de un Grafo Floyd - Warshall
• Tutorial de GraphThing (Version 1.3.1)
• Arbol de expansión mínima - Kruskal
• Tutorial de GrapgTea 
• Intercalación por MERGE 
• Camino/Circuito de Euler, Grafos

 

Todos los caminos de un grafo Floid – Warshall

Algoritmo de Floyd – Warshall

Este algoritmo se usa para hallar el recorrido mas eficiente entre 2 vértices pasando por las aristas  cuya suma es la menor, obteniendo como resultado el camino mínimo en grafos dirigidos ponderados, cuyos nodos no son autodirigidos.

Este algoritmo es otra forma de resolver el camino mas eficiente entre 2 vértices junto con el de dijkstra, excepto que en este se halla mediante permutaciones en la matriz de adyacensia.

  INICIO

 

 

Caminos mas corto con un solo origen – Dijkstra

Vinculo en construccion...

INICIO

Arbol de expansión mínima - Kruskal

Algoritmo de kruskal:

Este algoritmo se usa para hallar el árbol minimal de un grafo ponderado(con peso). El árbol minimal es la forma mas eficiente de conectar todos los vértices del grafo, mediante las aristas con menor peso posible…

Metodología:

1°: Hallar y marcar la arista de menor peso del grafo, si hay mas de una se marca cualquiera de ellas.

2°: Hallar y marcar la arista de menor peso sin contar la anterior, controlando que no generemos ciclos en el grafo, y controlando también que vértices nos falta recorrer. Esto quiere decir que en el árbol resultante tendremos n-1 aristas, siendo n el numero de vértices del grafo.

3°: Repetir el paso 2.

Cuando ya recorrimos todos los vértices, el árbol resultante es el árbol minimal.

Conclusión:

Como podemos ver, el algoritmo es un proceso recursivo. Ya que, excepto en el primer paso que solamente se halla y marca la arista de menor peso, se debe realizar la misma acción de hallar y marcar, pero con el adicional de controlar que no formen siclos, y que queden vértices que recorrer, que seria el caso base de la recursividad.

Aquí un link con un video explicando gráficamente el funcionamiento del algoritmo de kruskal:

https://www.youtube.com/watch?v=SilS8f8icWY

 

Aquí tenemos el Ejercicio 11 de la Guia Nº:8, el cual nos dio la consigna de hacerlo hoy en clases de Práctica la profesora Mariela Vanesa Burghardt para realizarlo en grupos.

 Archivo .pas codificado en Geany (Free Pascal).

//CONSGINA EJERCICIO 11, GUIA Nº:8
//En un plano con varias nodos de coordenadas (x, y). Tu trabajo es como conectar todos los nodos de forma que utilice la menor cantidad de tinta posible (Alg. Kruskal).

program grafoKruskal;

// Grafo conexo (esta todo conectado), denso (faltan pocas aristas para ser completo), no dirigido (bidireccional) y ponderado (con peso)

uses crt;
const n = 5;

type
{
 tVector = array [1..n] of string;
 tVertice = 1..n;
 tArco = record
  origen: tVertice;
  destino: tVertice;
 end;
}
 conjuntoVertices = array [1..n] of integer;
 conjuntoArcos = array [1..n, 1..n] of integer;
 tGrafo = record
  vertices: conjuntoVertices;
  arcos: conjuntoArcos;
 end;

var
 vGrafo: tGrafo;
{
 vector: tVector;
}


procedure crearGrafo(var pGrafo: tGrafo);
var
 i, j: integer;
begin
 for i := 1 to n do
 begin
  pGrafo.vertices[i]:= i;
  for j := 1 to n do
  begin
   pGrafo.arcos[i,j] := 0;
  end;
 end;
end;


function peso(i: integer; j: integer): integer;
begin
 writeln('Que peso tiene el vertice ', i, ' con el ', j, ': ');
 readln(peso);
end;


procedure cargarGrafo(var pGrafo: tGrafo);
var
 i, j: integer;
begin
 for i := 1 to n do
 begin
  for j := 1 to n do
  begin
   pGrafo.arcos[i,j] := peso(i, j);
  end;
 end;
end;


procedure mostrarGrafo(pGrafo: tGrafo);
var
 i, j: integer;
begin
 for i := 1 to n do
 begin
  for j := 1 to n do
  begin
   write(pGrafo.arcos[i,j], ',')
  end;
  writeln();
 end;
end;


begin
 crearGrafo(vGrafo);
 cargarGrafo(vGrafo);
 mostrarGrafo(vGrafo);
end.
//El ejercicio continua en construccion, lo iremos modificando.

 

INICIO

Camino / Circuito de Euler, Grafos

En clase de Lógica estuvimos poniendo en práctica trabajar con Euler, en lo cual lo aplicamos a Grafos para buscar un Camino y/o Circuito. 

Camino: es una sucesión de lados que van de un vértice U a otro V, dicha sucesión puede incluir lados repetidos.

Circuito: es un camino que comienza y termina en el mismo vértice.

Para buscar el Camino y/o Circuito Euleriano, debemos comprender lo siguiente:

Grafo conexo: si para dos vértices distintos, U y V, existe un trayecto para ir de U a V. Lado puente es aquel que si se lo elimina, el grafo al que pertenece deja de ser conexo.

Camino de Euler:

·         Si un Grafo G es conexo y tiene exactamente dos vértices de grado impar, entonces existe camino de Euler.

·         Si un grafo G tiene más de dos vértices de grado impar, entonces no existe camino de Euler.

Circuito de Euler:

·         Un Grafo G tiene circuito de Euler si y solo si es conexo y todos sus vértices tienen grado par.

·         Si un Grafo G tiene un vértice de grado impar, entonces no existe circuito de Euler.

A partir de esto al ponernos a practicar, nos dimos cuenta que: por ejemplo vamos un museo en el cual deseamos visitar cada una de sus salas, sin importar que se hará en cada una de ellas, pero con el fin de pasar por cada sala sin tener que volver a pasar por la misma nuevamente y poder concretar el recorrido completo sin faltarnos una sala por visitar. Entonces nos pusimos a debatir entre nosotros (Integrantes del grupo del Blog) que sería bueno poder implementar una APP para que al designar el lugar donde estamos, dándole las especificaciones de cantidad de salas (Vértices) y caminos o puertas para ingresar a ella, contando con o no con un pasillo y/o camino exterior, (Aristas). En fin esta APP debería trabajar sobre esos datos implementándolo como un Grafo y también utilizar Euler y obtener el Circuito euleriano.

Nos surgió la imaginación y nos salió pensar en esta idea, ya que creeríamos que todavía en estas instancias esta fuera de nuestro alcance.

 INICIO