Implementação_Fleury_Python

Prévia do material em texto

UNIVERSIDADE ESTADUAL DO MARANHÃO – UEMA 
CENTRO DE CIÊNCIAS TECNOLÓGICAS – CCT 
ENGENHARIA DA COMPUTAÇÃO 
 
 
 
 
 
 
JONAS CARVALHO DE SOUSA NETO 
GABRIEL CANCIO COSTA 
LUIS GUSTAVO DINIZ PEREIRA 
 
 
 
 
 
 
 
 
TEORIA DOS GRAFOS: ALGORITMO DE FLEURY 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
SÃO LUIS - MA 
2021 
 
 
 
 
 
 
 
JONAS CARVALHO DE SOUSA NETO 
GABRIEL CANCIO COSTA 
LUIS GUSTAVO DINIZ PEREIRA 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
TEORIA DOS GRAFOS: ALGORITMO DE FLEURY 
 
 
 
 
 
 
 
 
 
Trabalho apresentado a disciplina de 
Matemática Discreta Avançada, como 
requisito parcial para a obtenção de nota, 
referente ao segundo período, na 
Universidade Estadual do Maranhão. 
 
Orientador(a): Cicero Costa Quarto 
 
 
 
 
 
SÃO LUÍS – MA 
2021 
 
SUMÁRIO 
1. TEORIA DOS GRAFOS .................................................................................. 4 
2. ORIGEM E IMPORTÂNCIA .......................................................................... 4 
2.1 ETAPAS DO ALGORITMO .......................................................................... 4 
2.2 IMPLEMENTAÇÃO DO ALGORITMO ....................................................... 5 
● PASSOS DO ALGORITMO (EXECUÇÃO) ..................................................... 5 
●TESTE E EXECUÇÃO: CAMINHO EULERIANO E CICLO EULERIANO .... 6 
3 CONCLUSÃO .................................................................................................. 7 
REFERÊNCIAS .................................................................................................. 8 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1. TEORIA DOS GRAFOS 
A Matemática Discreta é uma área da matemática geral que corresponde a 
resolução de problemas do cotidiano através de estruturas discretas, ou seja, 
diferentemente do usual as funções algébricas possuem valores distintos, a caracterização 
dos problemas em símbolos ou conjuntos numéricos naturais é uma das principais 
características desta área. A procura por soluções cada vez mais simples (diferentes) e 
racionais chegou com intensidade em meados do século XX com o término da Segunda 
Guerra Mundial e o advento da Era dos Computadores, neste período, crescia a procura 
por profissionais (matemáticos, cientistas, físicos, engenheiros e etc.) que interpretassem 
sinais lógicos com maestria para comunicar-se com as máquinas afim de auxiliar na 
realização de cálculos extensos e complexos. Logo após, o principal destaque foi para 
outra área especializada na resolução de problemas discretos, A Teoria dos Grafos. 
 Os Grafos são estruturas discretas que permitem através de gráficos formados por 
vértices e arestas ilustrar diversas resoluções de problemas com símbolos matemáticos. 
Na definição propriamente dita, um modelo de grafo é um conjunto não vazio de 
vértices/nós(V) e arestas (E) que são direcionados ou não, podendo ser classificados de 
vários tipos e, considerados infinitos ou finitos dependendo do domínio do grafo. Por 
exemplo, o mapeamento das ruas de uma cidade para a análise de qual o caminho mais 
curto de um lugar A até um lugar B pode ser feito através da construção de um grafo ‘G’ 
e arbitrariamente exige a associação de pontos e linha, então, o domínio é uma situação 
real e é finita. 
 
2. ORIGEM E IMPORTÂNCIA 
 O algoritmo de Fleury é utilizado para a construção ou identificação de um ciclo 
euleriano em um grafo euleriano. Um caminho ou um circuito é dito euleriano se ele 
possui todas as arestas de um grafo. Um grafo que possui um circuito euleriano é um 
grafo euleriano. Um grafo que possui um caminho, mas não um circuito euleriano, é 
chamado de grafo semi-euleriano. 
 Tal algoritmo é muito importante para identificar se um grafo possui circuito e 
caminho de Euler, através dele, por exemplo, é possível provar o caso impossível das 
pontes de Konigsberg, em que não pode existir um circuito, mas sim, um caminho 
euleriano. 
 Além disso, vale destacar que o algoritmo contribuiu muito para o 
desenvolvimento do estudo dos grafos, conhecimentos como relação entre os graus, por 
exemplo, existe um teorema em que quando todos os graus são pares significa que existe 
um circuito euleriano, ademais, outro teorema que afirma que quando dois dos vértices 
possuem grau ímpar, então existe um caminho euleriano. 
 
2.1 ETAPAS DO ALGORITMO 
 Iniciando um trajeto por determinado grafo, cabe ao pesquisador aplicar as 
seguintes regras: 
 1. Escolher um vértice para iniciar o caminho 
 2. Escolher sempre um vértice não ponte como próximo. 
 - Fazer a pergunta: “É aresta ponte?” 
 - Caso não possua, percorrer uma aresta ponte. 
 3. Não percorrer a mesma aresta, pois conforme elas são apagadas, não 
podem mais ser percorridas. 
 - Se isso não for possível, o grafo tem apenas caminho e não um circuito. 
 
2.2 IMPLEMENTAÇÃO DO ALGORITMO 
 A implementação do algoritmo foi realizada na linguagem de programação Python 
por ser uma ferramenta de alto nível, possuir diversas funções especiais e possibilitar a 
recursividade no código. 
 
● PASSOS DO ALGORITMO (EXECUÇÃO) 
 Inicialmente, se insere os valores e as possíveis ligações de um grafo “G” no final 
do algoritmo, após isso chama-se a função “print_fleury”, nessa função temos o 
caminho(‘trail’) recebendo a função “fleury(G)”, passando então, aquele grafo ao 
algoritmo que vai definir se ele é um grafo euleriano, ou então caminho ou ciclo euleriano. 
 Dentro da função “fleury”, temos uma variável chamada “odn”, esta variável, 
acaba por receber uma função a qual foi passada como argumento o grafo G, a 
“odd_degree_nodes(G)”, que tem como objetivo descobrir quantos vértices de grau ímpar 
existem nesse grafo G. Caso a contagem de graus ímpares seja igual a 1 ou maior que 
dois, então este grafo não será euleriano. Senão o grafo terá seus valores passados para a 
variável “g”, e o caminhos (trail) serão definidos para receber novos valores. Caso todos 
vértices tiverem grau dois, então uma variável “u”, receberá o primeiro valor do grafo. 
Senão, “u” receberá o primeiro elemento do grafo copiado. 
 Enquanto, as ligações do grafo copiado forem maiores que 0, então o vértice atual 
(current_vertex) recebe o valor de “u”. Para o vértice “u” no grafo copiado com índice 
[current_vertex], haverá a remoção de “u” deste grafo e a remoção do vértice atual do 
grafo “g”. Se houver ponte, “u” será adicionado ao grafo com índice vértice atual e “u” 
irá adicionar o vértice atual. Senão houver ponte, finalizar o for. 
 Se houver ponte novamente, remover “u” do vértice atual, remover u do grafo 
com índice u, adicionar o vértice atual, e adicionar o caminho do vértice atual e u. Esse 
processo se repetirá até todos os caminhos serem preenchidos, por fim retorna o caminho. 
 Com o caminho retornado, basta fazer a análise, se o caminho retornado 
inicialmente voltou com ‘Não é um grafo Euleriano’, então, sairá isso no output. Caso o 
caminho retornado tenha o elemento final igual ao inicial, saíra Ciclo Euleriano, e o 
caminho que o programa escolheu para percorrer. Por fim, caso o vértice final seja 
diferente do inicial, imprimirá o “Caminho Euleriano” e o percurso feito no grafo. 
 
 
Clique na imagem ou aqui 
para fazer o download do algoritmo. 
 
 
 
 
 
 
https://drive.google.com/file/d/117LmzGPubRgPCbLvdad3C1p9iJNDrRKa/view?usp=sharing
https://drive.google.com/file/d/117LmzGPubRgPCbLvdad3C1p9iJNDrRKa/view?usp=sharing
 
●TESTE E EXECUÇÃO: CAMINHO EULERIANO E CICLO EULERIANO 
 
Grafo 1 - Aplicado no fim do algoritmo 
 
 
 
Existe um teorema que afirma que quando o grafo possui apenas 2 vértices de grau 
ímpar, ele será um caminho euleriano. Com isso, fizemos a aplicação de modo que 
houvesse uma função chamada “odd_degree_nodes” que faz essa verificação da 
quantidade de vértices de grauímpar que o grafo possui. 
 Caso houvesse menos que dois vértices ou mais que dois vértices de grau ímpar, 
então aquele grafo não poderia ser nem Ciclo e nem Caminho Euleriano. Logo ele não 
seria impresso. 
 
Grafo 2 - Aplicado no fim do algoritmo 
 
Usando o mesmo princípio do primeiro exemplo, chama-se a função 
“odd_degree_nodes” na função principal (“fleury”) para obter a quantidade de vértices 
com grau ímpar que integram o grafo. e determinar se o grafo é euleriano ou não. 
Após este procedimento, caso o grafo seja euleriano, é feita a lógica para 
determinação de pontes e em seguida a iteração sobre as arestas determinado o caminho 
adequado. 
O último passo é feito na função “print_fleury”, que recebe ao receber a instância 
da função “fleury”, recebe o caminho e faz a validação para determinar se é um ciclo ou 
circuito euleriano, imprimindo os resultados. 
 Além desses dois grafos citados acima, fizemos a implementação de um não 
euleriano, por isso que na saída ele mostra por último que aquele grafo não é euleriano. 
 
 
3 CONCLUSÃO 
Logo, foi concluído com exatidão a aplicação do algoritmo de Fleury para a 
descoberta de caminho ou ciclo eulerianos. Para isso, a pesquisa pelo uso de grafos na 
linguagem escolhida foi imprescindível, pois os pesquisadores não tinham conhecimento 
adequado para a elaboração de grafos nessa linguagem. 
Uma das limitações são a escolha do primeiro vértice do grafo, o qual deve ser 
dito pelo usuário do algoritmo, além disso, devem ser inseridos todos os vértices os quais 
determinado ponto faz conexão, com isso, o algoritmo vai escolher o melhor caminho a 
ser percorrido. 
Além disso, poderia ser adicionado um framework para a criação de grafos, isso 
possibilitaria uma visão melhor do caminho de cada grafo inserido, bem como ajudaria o 
usuário a entender cada passo que se daria para a execução do algoritmo. 
Com isso, o trabalho foi bem proveitoso no sentido de entendimento do algoritmo 
em si, possibilitando aos pesquisadores a compreensão de cada passo do algoritmo, bem 
como os teoremas e definições que cercam um caminho ou ciclo em um grafo euleriano. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
REFERÊNCIAS 
Algoritmos em Python. Representação de Grafos. 
Disponível em: https://algoritmosempython.com.br/cursos/algoritmos-
python/algoritmos-grafos/representacao-grafos/ 
Acesso: 24/01/2021 
 
Matemática para gente grande. Matemática Discreta II. 
Disponível em: 
https://www.youtube.com/playlist?list=PL8aWdrmfXHiJU_V_c2vM1dCFDh_Z93BeZ 
Acesso: 22/01/2021