Teoria dos Grafos

Prévia do material em texto

INTRODUÇÃO À TEORIA DOS GRAFOSINTRODUÇÃO À TEORIA DOS GRAFOS
GRAFOS ORIENTADOSGRAFOS ORIENTADOS
Autor: Me. Sergio Eduardo Nunes
Revisor : Emerson dos Santos Paduan
IN IC IAR
introdução
Introdução
Caro(a) aluno(a), a sua bagagem de conhecimento acerca da teoria dos grafos já te permite se
aprofundar nos conhecimentos, de forma a conhecer as teorias clássicas, e isso vai permitir que
você tenha maior recursos na busca de resolução de problemas. Esta unidade vai possibilitar que
você compreenda a técnica discutida no circuito de Hamilton, de forma que permita a compreensão
do planejamento para passar por todos vértices somente uma vez e �nalizar no ponto inicial. Após
isso, as discussões a respeito do problema do caixeiro viajante permitirão que se tenha um circuito
circular que passe apenas uma vez por todos os vértices.
Ainda será possível compreender os grafos planares e o problema da coloração que vai fornecer
conhecimentos para adicionar rotulagens a �m de se ter mais informações a respeito dos elementos
que compõem o grafo. Para �nalizar, serão discutidos assuntos referentes aos algoritmos de
percurso de árvore, para entender como se pode visitar todos os nós em que o grafo forme um T.
Ao estudar tais técnicas, você estará apto(a) a propor soluções mais e�cientes, com ferramentas
matemáticas que proporcionam um maior número de recursos. As aplicações em problemas
cotidianos são altamente adaptáveis com as técnicas discutidas nesta unidade. Vamos ampliar o
nosso conhecimento de teoria dos grafos?
Em razão do tempo escasso e muitas atividades, você já deve ter planejado um circuito para que
conseguisse realizar todas as atividades, por exemplo: tirar dinheiro no caixa eletrônico, pegar o
bolo, pagar o boleto na casa lotérica, passar no supermercado, comprar os presentes etc. Sem um
planejamento de rota, isto é, a ordem em que as atividades devem ser realizadas, pode-se perder
um tempo que talvez comprometa a execução de todas as atividades.
Os grafos discutidos em unidades anteriores possuíam uma característica Eulleriana, caracterizada
por permitir a passagem mais de uma vez pelo mesmo vértice. A �m de se evoluir nos estudos
acerca dos grafos, inicialmente, vamos conhecer a respeito do circuito de Hamilton, no qual o
objetivo é passar por todos os pontos (somente uma vez) e retornar ao ponto inicial. Mas como e
onde surgiram tais indagações?
Os grafos hamitonianos surgiram em menção ao famoso matemático e astrónomo Willian Rowan
Hamilton (1805 - 1865), em Dublin (Irlanda). O seu pai (Willian) era advogado, e a mãe (Sarah)
pertencia a uma família conhecida pela inteligência. Hamilton era incrivelmente acima da média,
pois aos 14 anos já havia aprendido a falar 13 idiomas, entre eles: francês, italiano, árabe, grego e
algumas línguas orientais.
Ao completar 18 anos, Hamilton entrou na faculdade Trinity College de Dublin, sem antes ter
frequentado nenhum ambiente escolar. Ele era conhecido como “Hamilton Prodígio”, pois possuía
uma mente brilhante e criativa. As suas contribuições na matemática foram diversas, sendo o objeto
de estudo nesse momento os grafos de Hamilton.
Um evento muito famoso foi um jogo de viagem pelo mundo, sendo um sucesso de vendas nos anos
de 1859. O jogo consistia em fazer com que o jogador viajasse ao redor do mundo por uma rota
circular e contínua, pelas arestas de um dodecaedro, em que o ponto de chegada tinha que ser o
mesmo de saída. O registro desse jogo pode ser observado na Figura 3.1.
Circuito de HamiltonCircuito de Hamilton
Com base nesses conceitos sobre as indagações propostas por Hamilton é que surgiu a ideia de
planejar um trajeto fechado (circular) que passe apenas uma vez por cada vértice e �nalize o circuito
onde foi o início. Um exemplo desse tipo de grafo pode ser observado na Figura 3.2.
Com base no exposto, podemos perceber que:
o trajeto inicia no vértice “D” e se encaminha para o vértice “C”;
do vértice “C” se encaminha para o vértice “E”;
do vértice “E” se encaminha para o vértice “F”;
do vértice “F” se encaminha para o vértice “B”;
do vértice “B” se encaminha para o vértice “A”;
do vértice “A” se encaminha para o vértice “G”;
do vértice “G” se encaminha para o vértice “H”;
e, �nalmente, do vértice “H” para o vértice “D”, que foi a origem do trajeto.
Com isso, Toscani e Veloso (2012, p. 211) de�niram que:
Figura 3.1 - Jogo “Viagem pelo mundo”
Fonte: GeoGebra.
Figura 3.2 - Exemplo de grafo de Hamilton
Fonte: Elaborada pelo autor.
A existência de circuito hamiltoriano só é garantida quando o número satisfaz a condição para
qualquer vértice v e w não adjacentes, a soma de seus graus seja maior que o número de vértices.
Tratando-se de um problema de decisão, quando as arestas têm o mesmo custo.
Então, podemos concluir que:
Se um grafo G de ordem x >=  3 e tem um grau(G) >=  2 para cada vértice (V), então,
podemos dizer que o grafo é hamiltoriano. Para que permita uma melhor compreensão
acerca do formato desse tipo de grafo, observe o comparativo demonstrado na Figura
3.3.
O grafo x pode ser considerado um circuito de Hamilton, uma vez que é possível passar pelos
vértices na ordem a seguir:
A para D; D para E; E para C; C para B e, �nalmente, B para A.
Já no grafo y, para passar em todos os pontos, obrigatoriamente, é necessário passar mais de
uma vez nos vértices, por exemplo:
A para D; D para E; E para C; C para B; B para E (aqui está o problema!); �nalizando
em E para A.
Ainda é possível perceber que o grafo hamiltoriano não é necessário percorrer todas as arestas.
praticar
Vamos Praticar
O grafo cúbico é um grafo regular em que todos os vértices possuem grau = 3. Esse tipo de grafo possui
características que muito se assemelham ao jogo desenvolvido por Hamilton, chamado “viagem pelo
mundo”. O seu formato pode ser observado na �gura a seguir:
Figura 3.3 - Segundo exemplo de grafo de Hamilton
Fonte: Elaborada pelo autor.
Com base no circuito de Hamilton, analise as a�rmativas a seguir e assinale a correta.
a) Não é possível fazer um circuito de Hamilton, pois o número de vértices é maior do que de
arestas.
b) Não é possível fazer um circuito de Hamilton, pois o número de vértices não é maior do que de
arestas.
c) É possível fazer um circuito de Hamilton, pois o número de vértices é maior do que de arestas.
d) É possível fazer um circuito de Hamilton, pois o número de vértices não é maior do que de arestas
e possui um circuito.
e) O grafo não possui arestas que ligam todos os vértices.
Figura 3.4 - Circuito de Hamilton
Fonte: Leshabirukov /Wikipedia.
A matemática é uma área que permite suposições, induções, modelagens, testes, entre diversos
outros tipos de comprovações. Isso permite que na teoria dos grafos se aproprie de tais técnicas e
conhecimentos, para que, assim, se possa planejar a solução de problemas.
Um dos problemas envolvidos na teoria dos grafos é conhecido como “Problema do Caixeiro
Viajante”, que se trata de uma técnica hamiltoriana que permite passar por diversos pontos somente
uma vez, descobrindo uma rota mínima. Isso permite que se tenha uma ferramenta de otimização
de trajetos.
Formulando o Problema do Caixeiro Viajante
Os trajetos possuem um custo, sejam eles distância entre os pontos, praças de pedágio, estado de
conservação da rodovia etc. Certamente, essas variáveis in�uenciam na decisão de qual o melhor
trajeto a se tomar para que sejam minimizados os custos e consumo de recursos.
Apesar do problema do caixeiro viajante (PCV) ter uma proximidade com o que propôs Hamilton, a
primeira abordagem ao tema se deu em 1934, por Hassler Witney, na apresentação de um
seminário na Universidade de Princeton (Nova Jérsei, Estados Unidos da América).
O PCV gera grafos hamiltonianos em que se deve passar em cada um dos vértices uma única vez,
sendo que o último vértice deve ser o mesmo que o primeiro vértice. Porém, a ordem na qual os
vértices serão “visitados” importa, uma vez que existe um custo. Ou seja, o problema do caixeiroviajante visa resolver o deslocamento entre os vértices, buscando o menor custo.
Algo interessante em se observar nesse conceito é que existem três possibilidades na determinação
do trajeto, em que o PCV pode ser:
Simétrico: quando é possível caminhar nas duas direções com o mesmo custo.
Assimétrico: os custos podem ser diferentes, conforme a direção do trajeto.
Assimétrico com direção proibida: embora as direções possuam custos diferentes,
uma delas pode não ser permitida no problema analisado.
Matematicamente, a formulação utiliza basicamente duas variáveis para análise do problema do
caixeiro viajante. São elas:
Para determinar se existe relacionamento entre dois vértices: é utilizado xij, que
determina se existe uma aresta que liga um ponto “i” ao ponto “j”.
Para determinar o custo entre os vértices: é utilizada a variável xij, que representa o
custo do ponto “i” até o ponto “j”.
A �m de contextualizar uma situação que permita a compreensão do termo “custo entre dois
vértices”, observe a Figura 3.5.
Problema do CaixeiroProblema do Caixeiro
ViajanteViajante
Supondo que os vértices sejam cidades, e os valores ao lado das arestas sejam distâncias em
quilômetros, a pergunta é: Partindo da cidade A, passando por todas as cidades apenas uma vez e
retornando à cidade A, qual é o trajeto com o menor custo? Pois bem, é essa questão que o
problema do caixeiro viajante se preocupa em solucionar.
Caro(a) aluno(a), nesse momento, você deve estar se perguntando: “Mas como obter uma solução
para esse problema?”. Vejamos a seguir.
Método Combinatório
Uma das formas de se resolver o problema do caixeiro viajante seria testar todas as combinações
possíveis e ordená-las, a �m de se obter a melhor solução, por exemplo:
1º Trajeto: Iniciar da cidade A e se deslocar até a cidade C (Custo 60).
2º Trajeto: Da cidade C até a cidade E (Custo 10).
3º Trajeto: Da cidade E até a cidade D (Custo 30).
4º Trajeto: Da cidade D até a cidade B (Custo 30).
5º Trajeto: Da cidade B até a cidade A (Custo 70).
Com isso, o custo total do trajeto foi de 200, passando por todos os vértices, não repetindo nenhum
dos vértices e retornando para o ponto inicial. Porém, essa solução não é a única possível e se torna
impraticável à medida que mais vértices são adicionados ao problema proposto.
Dessa forma, esse tipo de técnica é um subconjunto de um conjunto com soluções �nitas, e estas
devem ser testadas exaustivamente para que, então, se possa encontrar uma solução ótima.
Método do Vértice Adjacente mais Próximo
Existem outras formas de se resolver o problema do caixeiro viajante. Dentre as diversas técnicas e
algoritmos, vamos discutir o método do vértice adjacente mais próximo. Para tal, dois passos devem
ser seguidos:
Primeiramente, escolha o vértice inicial, que vamos chamar de vi, em que o trajeto
deverá ser iniciado e �nalizado nesse ponto ao �nal do circuito.
Figura 3.5 - Exemplo de Custo entre Vértices
Fonte: Elaborada pelo autor.
Os vértices que ainda não foram visitados no trajeto devem ser selecionados, para
isso, chamaremos de vx, �cando uma cadeia composta por vi e vx. Esse
procedimento deve ser repetido até que todos os vértices se esgotem.
Para facilitar a visualização das rotas possíveis, observe a matriz a seguir:
Para �ns de informação, sempre quando houver o cruzamento de linhas e colunas da mesma letra
(A com A, B com B etc.), será utilizado “*”, que simboliza que não existe valor. Essa ideia remete que,
no caso analisado, não existe uma estrada que liga na própria cidade (laço).
Com isso, podemos perceber que:
Supondo que o ponto de partida seja a cidade “A”, na segunda linha da matriz o
menor custo está em “C”.
Já em “C”, quarta linha da matriz, o menor custo está em “E”.
Em “E”, que está na sexta linha, o menor custo é “A”, porém, não podemos passar por
um vértice que já foi utilizado, dessa forma, o vértice escolhido foi a primeira opção
“B”, uma vez que “B”, “C” e “D” possuem o mesmo custo.
Quando em “B”, terceira linha da matriz, o único vértice não visitado é o “D”.
Finalmente em “D”, deve ser retornado ao ponto inicial “A”.
Com isso, podemos concluir que a rota utilizada foi A - C - E - B - D, gerando os respectivos custos: 12
+ 16 + 12 + 20 + 14, portanto o custo total da rota foi de 74. Pode-se concluir que a rota otimizada,
utilizando o método do vértice adjacente mais próximo, é de 74.
praticar
Vamos Praticar
Adicionar mais variáveis em análises torna o trabalho mais complexo, de difícil validação, porém, com maior
nível de con�abilidade e assertividade. O problema do caixeiro viajante é um desses exemplos, pois, por
meio dos cenários propostos, permite utilizar os tratamentos matemáticos em busca de uma solução
otimizada.
Com base no exposto, assinale a alternativa que descreve corretamente qual variável o PVC adiciona na
análise encontrada na teoria dos grafos.
a) Utiliza cores nos vértices, para adicionar mais informações.
b) Utiliza cores nas arestas, para adicionar mais dados.
c) Utiliza formatos nos vértices, para adicionar mais informações.
d) Utiliza formatos nas arestas para adicionar dados.
A B C D E
A * 16 12 18 16
B 10 * 18 20 20
C 18 20 * 18 16
D 14 18 10 * 8
E 8 12 12 12 *
e) Utiliza valores numéricos entre os vértices (na aresta) para adicionar o custo.
Você já deve ter percebido que estamos avançando nos estudos acerca da teoria dos grafos, e os
conceitos vistos até o momento irão alicerçar para que seja possível agregar mais conhecimentos,
para que você adquira mais habilidades técnicas na busca de soluções por meio dos grafos.
Dessa forma, nesse momento, serão discutidas as técnicas contidas nos grafos planares, que visa
buscar soluções com a intenção de não cruzar as arestas. Posteriormente, serão discutidos os
conceitos e aplicações encontrados no problema da coloração nos grafos, sendo uma forma de
numerar os vértices, adicionar mais variáveis e obter mais informações.
Grafos Planares
Nos grafos apresentados até o momento, não havia a preocupação no cruzamento das arestas, pois
os exemplos não possuíam tal restrição. Com isso, Cardoso (2011) de�ne que o grafo planar é
aquele em que é possível (re)desenhar de forma que as arestas não se cruzem.
Para te auxiliar na compreensão desse conceito, observe a Figura 3.6.
Figura 3.6 - Grafo planar
Fonte: Elaborada pelo autor.
Com base na Figura 3.6, pode-se perceber que a aresta que parte do vértice A para C cruza a aresta
que parte do vértice B para D. O questionamento é o seguinte: de que forma esse grafo poderia ser
Grafos Planares /Grafos Planares /
Problema de ColoraçãoProblema de Coloração
refeito, de forma que essas arestas não se cruzem?
Para �ns de exemplo e compreensão, observe a Figura 3.7, na qual é demonstrada uma das formas
de resolver tal problema.
Figura 3.7 - Redesenho de um grafo planar
Fonte: Elaborada pelo autor.
Dessa forma, como podemos perceber, a aresta que partia do vértice A para C foi projetada para
fazer um caminho externo do grafo, evitando, assim, que as arestas se cruzem. Esse tipo de grafo
apresentado nas Figuras 3.5 e 3.6 é conhecido como K4, ou seja, possui 4 vértices. Os grafos Kn são
grafos completos, em que cada vértice é adjacente a todos os demais.
Para que se possa compreender mais aplicações e exemplo de grafos planares, vamos compreender
as características encontradas em grafos bipartidos. Segundo Boaventura Netto e Jurkiewicz (2017),
os grafos bipartidos são denotados por Knm, com partição nos eixos [x, y], em que se pode de�nir
|x| = n e |y| = m, sendo que cada vértice de x deve ser adjacente a todos os vértices encontrados
em y. Para melhor compreensão do formato dos grafos bipartidos, observe o exemplo demonstrado
na Figura 3.8.
Figura 3.8 - Grafo bipartido
Fonte: Elaborada pelo autor.
Dessa forma, podemos perceber que o grafo bipartido apresentado é do tipo , uma vez que
existem duas partições, uma com dois vértices, e outra com três vértices.
reflita
Re�ita
Quanto mais conhecimentose habilidades
possuímos, maior serão as ferramentas utilizadas
para a resolução de problemas. Seria possível
utilizarmos em uma mesma análise as técnicas de
coloração, algoritmo pré-ordenado, levando em
consideração os custos?
Com isso exposto, nem todos os grafos podem ser considerados planares, uma vez que não
permitem fazer os ajustes das arestas de forma que não se cruzem. Um exemplo de aplicação de um
grafo não planar pode ser observado na Figura 3.9.
K2,3
Como podemos observar, o grafo bipartido não possibilita articular as arestas de forma que
não se cruzem, e esse tipo é considerado um grafo não planar, pois, mesmo se as arestas forem
passadas externamente, haverá cruzamentos.
Problema de Coloração
Uma das técnicas de teoria dos grafos com larga aplicação está no problema da coloração. Trata-se
de uma forma de numerar tanto os vértices quanto as arestas, a �m de se obter uma partição
separada por cores. Isso permite que tenhamos um estudo do relacionamento entre os vértices, em
que a orientação dos relacionamentos está nas cores.
Para tal, Boaventura Netto e Jurkiewicz (2017) de�nem que, se for pensado o caso mais simples e
elementar para se utilizar as cores, certamente utilizamos uma cor para cada vértice. Dessa forma,
teríamos uma solução para determinar os relacionamentos, de forma muito simplista. Porém, no
problema de coloração, só passa a fazer sentido se for utilizado quando o objetivo é fazer a ligação
por meio de arestas, somente em vértices que apresentam cores diferentes. Para melhor
entendimento, observe o grafo apresentado na Figura 3.10.
Figura 3.9 - Grafo não planar
Fonte: Elaborada pelo autor.
K3,3
Repare que nenhum dos vértices de mesma cor está diretamente ligado, sendo esse o objeto de
estudos do problema da coloração. Em suma, é dado como uma coloração válida se e somente se as
duas pontas que as arestas ligam possuírem cores diferentes.
Ainda é possível representar o grafo com bicoloração, ou com K cores, dizemos que o grafo é
colorível, quando possui uma coloração válida com k cores, em que o objetivo é se ter o menor
número de cores no grafo G. Em grafos com um número maior de vértices, esse trabalho se torna
mais complexo e desa�ador, uma vez que a premissa é não relacionar dois vértices de mesma cor.
Atingido tal objetivo, a coloração do grafo é dita como ótima.
Com isso, podemos perceber que o método de coloração dos vértices necessita de k cores para n
vértices, desejando-se que k seja menor que n. Essa teoria indica que existe um subconjunto A que
está contido em n, e esses elementos são as quantidades de cores dos vértices G, sendo desejável o
conjunto A expresso com mínimo de cores.
praticar
Vamos Praticar
Os grafos planares são recursos utilizados que possibilitam que se possa planejar o desenvolvimento do
grafo, de forma a permitir que as arestas não se cruzem. A �gura a seguir demonstra um cenário de um
conjunto de residências.
Figura 3.10 - Exemplo de grafo colorido
Fonte: Elaborada pelo autor.
Pode ser observado que existem três casas e três serviços, sendo: água, luz e telefone. O acesso entre os
serviços e as residências se cruzam, e isso deve ser evitado.
Com base no problema apresentado, assinale a alternativa com a a�rmativa correta.
a) O grafo é planar   .
b) O grafo é não planar .
c) O grafo é não planar .
d) O grafo é planar .
e) Não é um grafo.
Figura 3.11 - Conjunto residencial
Fonte: Elaborada pelo autor.
K3
K3
K3,3
K3,3
Sem dúvidas, ao longo dos assuntos discutidos, pudemos conhecer diversas técnicas relacionadas
aos estudos dos grafos. Você já pensou se juntarmos tais conhecimentos com as técnicas
relacionadas aos algoritmos? Com isso, será possível aplicar a análise de percurso em árvore binária.
Mas por que é utilizado o termo “árvore”? Esse termo justi�ca um grafo que não possui ciclos,
conforme pode ser observado na Figura 3.12.
Algoritmos de PercursoAlgoritmos de Percurso
em Árvoreem Árvore
saiba mais
Saiba mais
O trabalho intitulado “Árvores: Algoritmos e Aplicações”
possui um texto de fácil compreensão, em que é possível ter
uma noção básica acerca dos grafos em árvores e suas
derivações, sendo um bom material para quem despertou o
interesse nesse tipo de grafo.
Fonte: Almeida (2018, on-line ).
Com isso, pode-se perceber que o grafo somente será considerado uma árvore se existir um único
caminho entre dois vértices. No grafo, os vértices possuem cores diferentes em sua estrutura, a �m
de se demonstrar alguns termos importantes. No grafo em árvore, a sua disposição é hierárquica, o
que signi�ca que a distância entre a raiz (vértice preto ao centro do grafo) e os demais vértices são
rotulados por pais, �lhos e ancestrais, assim como acontece em uma árvore genealógica.
Nos grafos em árvore:
os vértices que não possuem �lhos são chamados de folha;
a representação de um grafo em árvore é denominada pela letra “T”;
T não contém ciclos;
um grafo T possui n-1 arestas.
Agora que foi possível compreender do que se trata um algoritmo e como é apresentado um grafo
em árvore, a dúvida é: como pode ser feito um trajeto em um grafo em árvore?
Pois bem, o trajeto a ser percorrido em um grafo T é um modo sistemático, que deve garantir que
todos os vértices sejam visitados.
Para �ns de compreensão do algoritmo utilizado na explicação, será demonstrado em
pseudocódigo, uma vez que os conhecimentos da implementação em ferramentas de
desenvolvimento computacionais podem utilizar a estrutura algorítmica discutida a seguir.
Um algoritmo muito utilizado é a visita pré-ordenada em árvore binária. Trata-se de uma travessia
de um grafo T, em que deve ser visitada inicialmente a sua raiz; após isso, os �lhos e suas
respectivas subárvores, respectivamente. Se houver ordem de visita nas subárvores, então, esta
deve ser seguida. Para a compreensão dessa técnica, observe o pseudocódigo na Figura 3.13.
Figura 3.12 - Exemplo de grafo em árvore
Fonte: Elaborada pelo autor.
Esse algoritmo faz com que a primeira visita se inicie pela raiz e, após isso, ocorra a visita de um
�lho, que deve visitar as folhas da subárvore. Ao �nal das visitas da subárvore, passa para o próximo
�lho, e o processo se repete até o último vértice ser visitado. Para que você possa compreender o
funcionamento dessa técnica, observe a Figura 3.14.
Dessa forma, a compreensão do funcionamento do algoritmo se torna mais clara. Esse mecanismo
de visita em árvore se mostra muito e�ciente, uma vez que existe uma pré-ordenação de visitas, que
garante que todos os nós sejam visitados.
praticar
V P ti
Figura 3.13 - Pseudocódigo de algoritmo de busca em árvore binária
Fonte: Elaborada pelo autor.
Figura 3.14 - Grafo em árvore binária, para visita pré-ordenada
essa é a fonte
praticar
Vamos Praticar
As visitas aos vértices, se planejada erroneamente, pode reverter em prejuízos �nanceiros, conforme a sua
aplicação prática. Um exemplo disso está na área da logística, em que uma rota sem planejamento
adequado certamente fará com que o tempo de entrega e o consumo de recursos �nanceiros sejam
maiores.
O grafo representado na �gura a seguir demonstra os pontos que devem ser visitados em uma entrega.
Se aplicado o algoritmo de pré-ordenação (iniciando do vértice 1), assinale a sequência válida de visitas aos
vértices.
a) 2 - 4 - 5 - 3 - 6 - 8 - 9 - 7 - 1.
b) 1 - 2 - 4 - 5 - 8 - 9 - 6 - 7.
c) 7 - 9 - 8 - 6 - 3 - 5 - 4 - 2 - 1.
d) 1 - 2 - 4 - 5 - 3 - 6 - 8 - 9 - 7.
e) 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9.
Figura 3.15 - Grafo numerado
Fonte: Elaborada pelo autor.
indicações
Material
Complementar
LIVRO
Aprendendo lógica de programação
Sergio Eduardo Nunes
Editora: Hope
ISBN: 978-85-5788-006-11
Comentário: Para melhor compreensão da estrutura dos algoritmos e
de que forma se propõem na resolução de problemas, esse livro utiliza
uma linguagem simples para explicar como os algoritmos são aplicados
em diversas áreas do conhecimento. Para isso, é utilizada a
pseudolinguagem do português,estruturada ao longo de 64 exercícios
resolvidos.
WEB
A árvore genealógica da humanidade
Ano: 2011
Comentário: O documentário produzido pela National Geographic
percorreu diversos lugares a �m de se montar uma árvore genealógica
para responder alguns questionamentos como: De onde viemos?
ACESSE
conclusão
Conclusão
As técnicas discutidas nesta unidade possibilitaram adquirir habilidades para que se possa planejar
os percursos de forma mais e�ciente. Quando houve a discussão acerca dos grafos de Hamilton,
podemos perceber como é possível determinar se existe a possibilidade de se passar por todos os
nós, sem que tenhamos que passar mais de uma vez e, ao �nal, voltar ao ponto onde foi iniciado o
percurso. Após isso, o problema do caixeiro viajante adicionou uma importante variável nos
problemas, que são os custos, com isso, o planejamento de um trajeto possibilitou aplicar em
situações reais.
Também foi discutido de que forma a coloração dos vértices pode auxiliar no planejamento dos
trajetos, para que possibilite mais recursos visuais, a �m de se organizar o grafo. Por �m, foi
discutido acerca dos algoritmos de percurso em árvore, que demonstra como deve ocorrer uma
visita de forma pré-ordenada.
É possível aplicar essas técnicas a diversas áreas do conhecimento, a �m de se ter soluções ótimas,
minimizar perdas de recursos e buscar maior e�ciência do planejamento de ações.
referências
Referências
Bibliográ�cas
ALMEIDA, L. A. Árvores: algoritmos e aplicações. 2018. 57 f. Dissertação (Mestrado Pro�ssional em
Matemática) - Instituto de Matemática Pura e Aplicada, Rio de Janeiro, 2018. Disponível em:
https://impa.br/wp-content/uploads/2018/03/TCC_2018_Lauro-e-Almeida.pdf . Acesso em: 22 dez.
2019.
BOAVENTURA NETTO, P. O.; JURKIEWICZ, S. Grafos: introdução e prática. São Paulo: Blucher, 2017.
CARDOSO, D. M. Teoria dos grafos e aplicações. Lisboa: Universidade de Aveiro, 2005.
LISTE, R. L. Ombra mai fu (Nunca una sombra fue...). GeoGebra. Disponível em:
https://www.geogebra.org/m/TMGBPxcG . Acesso em: 10 fev. 2020.
TOSCANI, L.; VELOSO, P. Complexidade de Algoritmos : Análise, Projeto e Métodos. 3. ed. Porto
Alegre: Bookman, 2012.
https://impa.br/wp-content/uploads/2018/03/TCC_2018_Lauro-e-Almeida.pdf
https://www.geogebra.org/m/TMGBPxcG