Material de Estudo - Teoria dos Grafos - Grafos Orientados - PVC

Prévia do material em texto

INTRODUÇÃO À TEORIA DOSINTRODUÇÃO À TEORIA DOS
GRAFOSGRAFOS
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
Circuito deCircuito de
HamiltonHamilton
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.
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.
Figura 3.1 - Jogo “Viagem pelo mundo” 
Fonte: GeoGebra.
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:
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
Figura 3.2 - Exemplo de grafo de Hamilton 
Fonte: Elaborada pelo autor.
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
Figura 3.3 - Segundo exemplo de grafo de Hamilton 
Fonte: Elaborada pelo autor.
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:
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.
Feedback: alternativa incorreta , pois é possível fazer o circuito de Hamilton, já
que o número de vértices não é maior do que o 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.
Figura 3.4 - Circuito de Hamilton 
Fonte: Leshabirukov /Wikipedia.
Feedback: alternativa incorreta , pois é possível fazer o circuito de Hamilton.
c) É possível fazer um circuito de Hamilton, pois o número de vértices é maior
do que de arestas.
Feedback: alternativa incorreta , pois o número de vértices não é maior do
que o 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.
Feedback: alternativa correta , pois o grafo possibilita caminhos em que se
passe apenas uma vez em cada vértice e ainda �nalize onde se iniciou.
e) O grafo não possui arestas que ligam todos os vértices.
Feedback: alternativa incorreta , pois o grafo de Hamilton não necessita que
todos os vértices estejam ligados entre si, pois não permite passar por todas as
arestas sem repeti-las.
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
Problema doProblema do
Caixeiro ViajanteCaixeiro Viajante
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 caixeiro
viajante 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. 
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).
Figura 3.5 - Exemplo de Custo entre Vértices 
Fonte: Elaborada pelo autor.
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.
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.
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 *
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.
Feedback: alternativa incorreta , pois no PVC não são utilizadas cores nos
vértices, mas custo entre os vértices.
b) Utiliza cores nas arestas, para adicionar mais dados.
Feedback: alternativa incorreta , pois no PVC não são utilizadas cores nos
vértices, mas custo entre os vértices.
c) Utiliza formatos nos vértices, para adicionar mais informações.
Feedback: alternativa incorreta , pois no PVC não são utilizadas cores nos
vértices, mas custo entre os vértices.
d) Utiliza formatos nas arestas para adicionar dados.
Feedback: alternativa incorreta , pois no PVC não são utilizadas cores nos
vértices, mas custo entre os vértices.
e) Utiliza valores numéricos entre os vértices (na aresta) para adicionar o
custo.
Feedback: alternativa correta , pois a intenção do PVC é calcular o menor custo
de trajeto.
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.
Grafos Planares /Grafos Planares /
Problema deProblema de
ColoraçãoColoração
Para te auxiliar na compreensão desse conceito, observe a Figura 3.6. 
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 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 resolvertal problema.
Figura 3.6 - 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.7 - Redesenho de um grafo planar 
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.
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
Figura 3.8 - Grafo bipartido 
Fonte: Elaborada pelo autor.
K2,3
reflita
Re�ita
Quanto mais conhecimentos e
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?
cruzem. Um exemplo de aplicação de um grafo não planar pode ser
observado na Figura 3.9.
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
Figura 3.9 - Grafo não planar 
Fonte: Elaborada pelo autor.
K3,3
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.
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.
Figura 3.10 - Exemplo de grafo colorido 
Fonte: Elaborada pelo autor.
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.
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   .
Figura 3.11 - Conjunto residencial 
Fonte: Elaborada pelo autor.
K3
Feedback: alternativa incorreta , pois o grafo é não planar e .
b) O grafo é não planar .
Feedback: alternativa incorreta , pois o grafo é .
c) O grafo é não planar .
Feedback: alternativa correta , pois o grafo é não planar, porque sempre
haverá cruzamento das arestas. Trata-se de um grafo bipartido, em que parte é
representada pelas casas e a outra pelos serviços de água, luz e telefone, dessa
forma, sendo representada por .
d) O grafo é planar .
Feedback: alternativa incorreta , pois o grafo é não planar.
e) Não é um grafo.
Feedback: alternativa incorreta , pois se trata de um grafo em que os vértices
são representados pelas casas e serviços, e as arestas pelos dutos de acesso.
K3,3
K3
K3,3
K3,3
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.
Algoritmos deAlgoritmos de
Percurso em ÁrvorePercurso em Árvore
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.
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
saibamais
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 ).
Figura 3.12 - Exemplo de grafo em árvore 
Fonte: Elaborada pelo autor.
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.
Esse algoritmo faz com que a primeira visita se inicie pela raiz e, após isso,
ocorra avisita 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
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
que existe uma pré-ordenação de visitas, que garante que todos os nós sejam
visitados.
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.
Feedback: alternativa incorreta , uma vez que no enunciado foi descrito que o
trajeto se inicia no vértice 1.
b) 1 - 2 - 4 - 5 - 8 - 9 - 6 - 7.
Feedback: alternativa incorreta , pois, após a visita do vértice 5, deve-se ser
direcionado ao vértice �lho do nível acima (vértice 3).
c) 7 - 9 - 8 - 6 - 3 - 5 - 4 - 2 - 1.
Feedback: alternativa incorreta , pois o trajeto foi feito na ordem inversa, ou
seja, do último vértice (7) para o inicial (1).
d) 1 - 2 - 4 - 5 - 3 - 6 - 8 - 9 - 7.
Feedback: alternativa correta , pois a ordem de visita ocorre da raiz ao �lho e a
sua respectiva subárvore e, após, ocorre toda a visita, passa para o próximo
�lho, até que todos os vértices tenham sido visitados.
e) 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9.
Feedback: alternativa incorreta , pois o trajeto seguiu uma ordem sequencial
numérica, e não uma busca em árvore binária.
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