Jogo das Bolinhas - Teoria dos Grafos

Trabalho de Teoria dos Grafos

Jogo das Bolinhas

Centro Universitário de Belo Horizonte, Belo Horizonte, MG

Descrição do Problema
Considere que temos três potes com capacidades de 8, 5 e 3 bolinhas, respectivamente, os quais não possuem qualquer marcação. O maior deles esta completamente cheio enquanto que os outros dois estão vazios. Estamos interessados em dividir as bolinhas em duas porções iguais com 4, tarefa esta que pode ser realizada por transvasos sucessivos de um pote no outro. Qual o menor número de transvasos necessários para completar a divisão?
Proposta de solução A solução proposta pelo grupo foi implementar uma aplicação, utilizando a linguagem java juntamente com a biblioteca jung , com intuito de demonstrar o problema descrito.

Explicação da teoria dos grafos proposta para a solução do problema Com base na teoria dos grafos utilizamos o conceito de busca e profundidade com caminhos mínimos.

Modelagem do grafo proposto

Algoritmo proposto para a solução

package jung; import java.awt.Color; import java.util.ArrayList; import java.util.List; import java.util.Scanner;

import javax.swing.JFrame;

import edu.uci.ics.jung.algorithms.layout.AbstractLayout; import edu.uci.ics.jung.algorithms.layout.ISOMLayout; import edu.uci.ics.jung.graph.Graph; import edu.uci.ics.jung.graph.SparseMultigraph; import edu.uci.ics.jung.graph.util.EdgeType; import edu.uci.ics.jung.visualization.BasicVisualizationServer; import edu.uci.ics.jung.visualization.RenderContext; import edu.uci.ics.jung.visualization.VisualizationViewer; import edu.uci.ics.jung.visualization.renderers.Renderer; import edu.uci.ics.jung.visualization.renderers.Renderer.VertexLabel;

public class Algoritmo {

// Atributos usados na funcao encontrarMenorCaminho static int melhorCaminho; int caminho; // Lista que guarda os vertices pertencentes ao menor caminho encontrado List menorCaminho = new