Guia de Estudos de Grafos

O que são Grafos?

Um grafo consiste de um conjunto de nós e um conjunto de arestas e é comumente utilizado para representar relações. Cada aresta em um grafo é especificado como um par de nós. A Figura 1 ilustra um grafo. O conjunto de nós é {A,B,C,D,E,F,G,H} e o conjunto de arcos é {(A,B), (A,D), (A,C), (C,D), (C,F), (E,G), (A,A)}.

Ele consiste em duas partes principais:

• Vértices (ou Nós): Representam os objetos ou entidades. Pense neles como cidades em um mapa, pessoas em uma rede social ou páginas na web.
• Arestas (ou Arcos): Representam as conexões ou relações entre os vértices. Uma aresta conecta um par de vértices, como uma estrada entre duas cidades ou um link entre duas páginas.

Tipos de Grafos

Grafos podem ser classificados de várias maneiras, dependendo de suas propriedades:

• Grafo Não-Direcionado: As arestas não têm uma direção. Se existe uma aresta entre A e B, a conexão é mútua (A está conectado a B e B está conectado a A). Ex: amizades no Facebook.

• Grafo Direcionado (Dígrafo): As arestas têm uma direção, indicadas por setas.

• Grafo Ponderado: Cada aresta tem um valor numérico associado, chamado de peso. Esse peso pode representar distância, custo, tempo, etc.

• Grafo Não-Ponderado: As arestas não têm pesos. Assume-se que todas as conexões têm o mesmo "custo" (geralmente 1).
• Grafo simples: um tipo de grafo que não possui laços (arestas que conectam um vértice a si mesmo) nem arestas múltiplas (mais de uma aresta ligando o mesmo par de vértices).
• Grafo rotulado: é um grafo onde vértices ou arestas possuem rótulos associados, que podem ser números, letras ou outros símbolos, para representar informações adicionais ou funções.
• Grafo conexo/desconexo: Um grafo é considerado conexo se existe um caminho entre qualquer par de vértices no grafo. Caso contrário, o grafo é chamado de desconexo.
• Grafo completo: é um tipo de grafo em que todos os pares de vértices distintos são conectados por uma aresta.
• Grafo bipartido completo: é um tipo especial de grafo bipartido onde cada vértice de um conjunto é conectado a todos os vértices do outro conjunto.
• Grafo planar: um grafo que pode ser representado no plano sem que suas arestas se cruzem.
• Grafo cíclico: Um caminho de um nó n até ele mesmo é chamado um ciclo. Um grafo que possui ciclos é chamado cíclico.
• Grafo acíclico: um grafo que não possui ciclos.
• Grafo isomorfo: Dois grafos podem ser considerados isomorfos se eles têm os mesmos vértices, as mesmas arestas e a mesma função de associação de arestas e seus extremos. Olhando uma figura podemos perceber se são isomorfos ou não também se:
• Um grafo tem mais vértices que o outro.
• Um grafo tem mais arestas que o outro.
Um grafo tem arestas paralelas e o outro não. Um grafo tem um laço e o outro não. Um grafo tem um vértice de grau kc o outro não. Um grafo é conexo e o outro não. Um grafo tem um ciclo e o outro não.

Conceitos

• Vértices adjacentes: vértices que estão conectados por uma aresta.
• Laço: é uma aresta que conecta um vértice a ele mesmo.
• Arestas paralelas: duas ou mais arestas que conectam o mesmo par de vértices em um grafo.
• Caminho: um caminho em um grafo é uma sequência finita ou infinita de vértices conectados por uma sequência de arestas que, na maioria das definições, são todos diferentes uns dos outros. O primeiro vértice é chamado de vértice inicial e o último é chamado de vértice final.
• Comprimento/tamanho do caminho: é o número de arestas que ele contém.
• Ciclo: um conjunto de vértices conectados em uma sequência fechada.
• Subgrafo: um subgrafo de um grafo G é um grafo cujo conjunto de vértices é um subconjunto do conjunto de vértices G e o conjunto de arestas é um subconjunto do conjunto de arestas de G,[1] ou seja, cuja relação de adjacência é um subconjunto de G restrita a esse subconjunto. Dizemos que um grafo G contém um outro grafo H se algum subgrafo de G é H ou é isomorfo a H.
• Grau de um vértice: quantidade de arestas ligadas a ele.
• Grau de entrada de um vértice: é o número de arestas que chegam a ele.
• Grau de saída de um vértice: número de arestas que partem dele.
• Vértice isolado: vértice de grau zero.
• Componente de um grafo: Em um grafo vazio , cada vértice forma um componente com um vértice e zero arestas. De forma mais geral, um componente desse tipo é formado para cada vértice isolado em qualquer grafo.

Representações de Grafos

Matriz de Adjacência

Se um grafo possui o número de nós constante (nós não podem ser criados e removidos), por exemplo 6 e não possui pesos nos arcos ele pode ser representado como uma matriz m booleana quadrada de tamanho 6. Quando a posição m[i][j] é true então existe um arco que sai de i e chega em j, ou seja, j é adjacente a i. A Figura 4 ilustra a representação de um grafo e sua matriz de adjacência correspondente.

Matriz de Alcançabilidade ou Fechamento Transitivo

Serve para determinar se um nó é alcançável a partir de outro.

Como encontrá-la?

• Multiplicação Sucessiva de Matrizes (Potências da Matriz de Adjacência): Se M é a matriz de adjacência, então M² (M x M) mostra os caminhos de tamanho 2, M³ mostra os caminhos de tamanho 3, e assim por diante.
• Algoritmo de Warshall: Ele constrói a matriz de alcançabilidade iterativamente. A ideia central é: para cada par de nós (i, j), o algoritmo verifica se existe um caminho de i para j usando um nó intermediário k.

A Figura 5 ilustra o processo pelo qual se pode encontrar todos os caminhos de tamanho 2 dentro de um determinado grafo.

Portanto se for necessário encontrar todos os caminhos de tamanho tam dentro de um grafo, basta encontrar a matriz mtam. Para verificar se há um caminho de tamanho tam entre dois nós i e j, basta verficar se mtam[i][j] = true. A soma (ou disjunção) dentre duas matrizes mi + mj (mi | | mj) retorna, portanto, todos os caminhos de tamanho i ou j dentro do grafo. Pode-se concluir que se é necessário encontrar todos os caminhos no grafo de quaisquer tamanhos, basta realizar o seguinte somatório (disjunção):

o que é equivalente a:

A matriz obtida pelo somatório (disjunção) anterior é chamada de fechamento transitivo da matriz m e representa todos os caminhos existentes dentro do grafo independente de tamanho.

Exercícios

A partir dos grafos a seguir, encontre as respectivas matrizes de alcançabilidade.

Algoritmos Fundamentais

Algoritmo de Warshall

Existe um algoritmo chamado Algoritmo de Warshall que é capaz de encontrar o fechamento transitivo de um grafo representado como matriz de adjacência sem precisar fazer a multiplicação e soma de matrizes. O algoritmo de Warshall está colocado a seguir.

Algoritmo de Dijkstra

Conhecido popularmente por ser o algoritmo para encontrar o menor caminho em um grafo, mas na verdade, ele encontra o caminho de menor custo (menor soma dos pesos das arestas).

O método a seguir implementa o algoritmo do menor caminho. O método utiliza um conjunto adicional caminho tal que caminho[i] é o nó que precede o nó i no caminho mais curto encontrado. O procedimento retorna a menor distância entre dois nós s e t e armazena em precede os nós que formam o menor caminho.

A partir do vetor caminho pode-se mostrar o menor caminho encontrado pelo algoritmo com o procedimento imprimeCaminho.

Exercícios

1) A partir dos grafos a seguir, encontre o melhor caminho entre os vértices 1 e 8 com o algoritmo de Dijkstra, mostrando os valores das estruturas internas Permitidos, Distância e Caminho.

a) 1 a 8

b) x (0) a y (4)

c) 1 a 4

d) 1 a 3

Exercícios

1. A partir do grafo representado na Figura 1:

• a) encontre sua representação como matriz de adjacência;
• b) encontre o fechamento transitivo do grafo utilizando multiplicação de matrizes;
• c) encontre o fechamento transitivo do grafo utilizando o algoritmo de Warshall.
• 2. Ilustre graficamente um dígrafo correspondente a cada uma das seguintes relações sobre inteiros de 1 a 12:
• a) x está relacionado a y se x – y é divisível por 3;
• b) x está relacionado a y se (x + 10 * y) < (x * y);
• c) x está relacionado a y se o resto da divisão de x por y é 2.

Travessia em Grafos

Quando tratamos de travessia em grafos não existe uma ordenação natural entre os vértices, diferentemente de árvores ou listas. Portanto algumas questões tornam a travessia em grafo mais complexa:

• Não existe um nó que naturalmente seja o inicial. Em uma lista encadeada sempre inicia-se com o primeiro da lista e árvore sempre com a raiz. Além disso, quando um nó inicial é pré- determinado, nem sempre todos os vértices do grafo poderão ser visitados, pois podem existir vértices que não são alcançáveis a partir do nó inicial. Em lista ou árvore, todos os nós eram visitados, desta forma, um novo nó inicial deve ser determinado para que o grafo seja completamente percorrido;
• Não há uma ordem natural entre os sucessores de um determinado vértice. Desta forma, a partir de um determinado vértice, não há uma ordem obrigatória na qual os sucessores são visitados;
• Um determinado vértice pode ter mais de um predecessor, desta forma, se um determinado vértice v possui mais de um predecessor, é possível que v seja visitado antes de algum predecessor.

Existem duas formas tradicionais de travessia em grafos: busca em largura e profundidade. A busca em largura utiliza uma lista para armazenar os vértices visitados. A busca em profundidade utiliza uma pilha que não precisa ser explicitamente implementada quando se utiliza recursão.

Busca em Profundidade (DFS)

A Busca em Profundidade usa uma pilha para guardar os nós que foram descobertos mas cujos vizinhos ainda não foram totalmente explorados.

• Explora os vizinhos do nó atual, sempre que possível, seguindo um caminho até que não haja mais nós não visitados neste caminho.
• Quando um nó não tem mais vizinhos não visitados, o algoritmo retrocede para o nó anterior e continua a explorar outros ramos.

Será considerado que a tarefa do procedimento de travessia consiste em a partir de um determinado vértice (neste exemplo “0”) visitar (processar) todos os outros vértices. Considere a Figura 1.

A partir do grafo anterior o primeiro nó a ser processado é o nó inicial 0. O grafo da Figura 1 é ilustrado na Figura 2. A partir do nó inicial há duas alternativas: continuar o processo no nó 1 ou no nó 4. Considere que o nó escolhido é o nó 1. O processo é ilustrado na Figura 3. A partir do nó 1 seu único vizinho ainda não visitado é escolhido para que o processo continue. Essa situação é ilustrada na Figura 4.

Seguindo a estratégia de escolher o nó com menor conteúdo (ou menor nó) para prosseguir o processo de travessia, a partir do nó 3 o nó 0 seria o escolhido. Essa é uma situação interessante. Se o nó 0 for o escolhido, o processo de travessia entrará em loop infinito, pois o caminho 0-1-3- 0 forma um ciclo, uma vez que a origem e o destino do caminho são os mesmos. Portanto é necessário uma estratégia para evitar tal problema. Geralmente um nó marcado como visitado nunca será escolhido novamente, uma vez que ele já foi processado. Portanto restam os vértices 5 e 6 (adjacentes a 3). Considerando que o vértice 5 seja o escolhido, o grafo seria representado mostra a Figura 5.

Como o vértice 5 não possui nós adjacentes, a busca não pode continuar seguindo adiante. Neste caso o processo retorna para o vértice visitado anteriormente (vértice 3) e verifica se existe mais algum nó adjacente que ainda não foi visitado. Neste exemplo o vértice 3 possui o vértice 6 adjacente e não visitado, portanto o vértice 6 será o próximo vértice escolhido, como ilustrado na Figura 6. Como o vértice 6 não possui mais vértices adjacentes ainda não visitados, o processo retorna para o vértice 3. Neste ponto, o vértice 3 também não possui nenhum outro nó adjacente ainda não visitado, portanto, o processo retorna para o nó anterior ao 3 (vértice 1) e tenta encontrar outro nó adjacente não visitado. Como o vértice 1 não possui nenhum nó adjacente ainda não visitado, o processo retorna ao vértice 0 que possui o adjacente 4 ainda não visitado. Logo o vértice 4 é escolhido como ilustrado na Figura 7. Como não há mais nenhum vértice adjacente a 0 e ele é o vértice inicial, o processo é encerrado.

É possível perceber que esse processo pode ser implementado de maneira muito simples utilizando um algoritmo recursivo. A pilha de chamadas recursivas é ilustrada na Figura 8.

Exemplo

Busca em profundidade no grafo da imagem acima: ABEFCGHDIJ

Algoritmo

Busca em Largura (BFS)

A busca em largura utiliza internamente uma estrutura de fila para armazenar os nós já visitados.

Exemplo

Busca em largura no grafo da imagem acima: ABCDEFGHIJ

Algoritmo

1. Se a fila de vértices não está vazia então

• 1.1. Remover o vértice i que está na fila // note-se que uma fila sempre remove o primeiro elemento
• 1.2. Processar o vértice i
• 1.3. Adicionar os vértices adjacentes a i na fila // um nó só é adicionado se ele já não foi visitado
• 1.4. Executar o procedimento 1 sobre a fila atualizada

É importante ressaltar que na primeira chamada do algoritmo a fila contém um único vértice que é o vértice inicial.

Vantagens e desvantagens de Busca em Profundidade e Largura

As duas metodologias de travessia em grafos possuem vantagens e desvantagens. Ambas podem ser utilizadas para se encontrar um determinado elemento dentro de um grafo. Considere-se, por exemplo as Figuras 15 e 16

Os grafos das Figuras 15 e 16 são os mesmos. A partir do vértice 0 tenta-se encontrar o vértice o vértice 6. Pode-se verificar que se a busca em profundidade é utilizada muito mais vértices precisam ser visitados para que a solução seja encontrada. No exemplo, os vértices [0, 1, 2, 3, 4, 8, 9, 5, 10, 11, 12, 2 e 6] precisam ser visitados. Por outro lado, com busca em largura muito menos vértices precisam ser visitados [0, 1, 2, 3, 4, 5, 6]. Geralmente a busca em largura tende a encontrar a solução de um problema de busca necessitando menos comparações. Além disso a busca em largura trata naturalmente o problema de ciclos em grafos. Porém sua implementação tende a ser mais complexa, pois necessita de uma fila para armazenar os vértices. A busca em profundidade possui uma implementação mais simples, porém necessita de um mecanismo auxiliar para tratamento de ciclos, geralmente implementado marcando os vértices como visitados.

Exercício

1) A partir do Grafo a seguir mostrar a seqüência com que os vértices são visitados executando tanto busca em largura quanto busca em profundidade a partir do vértice A:

Profundidade: A → C → G → B → E → F → H → D

Largura: A → C → D → G → B → F → E → H

2) As formas de busca Profundidade e Largura permitem navegação em um grafo de maneira não informada, ou seja, ignorando o custo que pode estar associado às arestas ou mesmo em grafos não ponderados. Escreva um parágrafo descrevendo o funcionamento de cada uma dessas estratégias de busca, quais estruturas de dados elas necessitam e como elas são utilizadas durante o processo de busca.

A Busca em Largura (BFS) explora o grafo nível por nível, garantindo que todos os vizinhos de um nó sejam visitados antes de se mover para os vizinhos dos vizinhos. Para gerenciar essa ordem, a BFS utiliza uma estrutura de dados Fila, onde os nós são adicionados à parte traseira e removidos da frente, assegurando que o nó visitado há mais tempo, e, portanto, mais próximo da origem, seja o próximo a ser expandido. Por outro lado, a Busca em Profundidade (DFS) explora o grafo o mais profundamente possível em cada ramificação antes de retroceder. Ela prioriza ir o mais longe possível a partir do nó atual, e para gerenciar os nós a serem visitados, a DFS utiliza uma estrutura de dados Pilha. O nó é adicionado e removido do topo da pilha, o que faz com que o nó visitado mais recentemente seja o próximo a ser expandido, impulsionando a busca para uma profundidade maior. Ambas as estratégias utilizam um conjunto ou array de nós visitados para evitar o processamento de um nó múltiplas vezes e a formação de loops infinitos.

3) Escreva um Pseudo-Código ou código em JAVA para cada uma dessas estratégias.

4) A partir dos Grafos abaixo, mostre a sequência gerada pelos caminhamentos de Profundidade e Largura considerando a ordem lexicográfica como escolha dos vértices adjacentes e iniciando as travessias no vértice 1.

Profundidade: 1,2,3,4,8,7,5,6

Largura: 1,2,5,3,4,7,8,6

Profundidade: 1,2,3,5,4,6

Largura: 1,2,3,4,5,6 (coincidência estar ordenado)

Profundidade: 1,2,3,6,5,4,7

Largura: 1,2,4,5,3,6,7

Profundidade: 1,4,2,5,3,6

Largura: 1,4,5,2,3,6

Coloracão em Grafos

1) O que é o problema da coloração?

O problema da coloração de grafos é um conceito que consiste em atribuir "cores" a elementos de um grafo, geralmente os vértices, de forma a satisfazer certas condições. A regra fundamental é que dois vértices conectados por uma aresta não podem ter a mesma cor.

2) Qual a relação do problema da coloração com a propriedade de Planaridade de um grafo?

Teorema das Quatro Cores. Um grafo planar é um grafo que pode ser desenhado em um plano (como um pedaço de papel) sem que nenhuma de suas arestas se cruze. As arestas podem se tocar apenas nos vértices. Em outras palavras, para colorir um mapa (que pode ser modelado como um grafo planar), bastam no máximo quatro cores para garantir que países vizinhos tenham cores diferentes. O problema da coloração só pode ser aplicado a grafos planares.

3) O que é o número cromático de um grafo?

O número cromático do grafo é o menor número de cores necessárias para se para colorir o grafo de acordo com uma certa regra.

4) O que é um grafo dual?

Qualquer grafo simples, conexo e planar pode ser entendido como o grafo dual de um mapa.

5) O que diz o teorema das 4 cores?

O teorema das quatro cores estabelece que o número cromático de qualquer grafo simples, conexo e planar é no máximo 4.

6)Como um mapa pode ser representado na forma de um Grafo e quais características esse grafo possui?

R: Representando cada região como se fosse um nó, e uma aresta interligando elas caso façam fronteira.

7) Desenhe o grafo dual do mapa abaixo e encontre o seu número cromático.

R: Número cromático = 4

Aplicações de Grafos

1) Qual teoria da Teoria dos Grafos permite identificar que 2 grafos representam a mesma estrutura?

R: A teoria do isomorfismo. Para saber se dois grafos são isomorfos:

• Ambos devem possuir o mesmo número de vértices
• Ambos devem possuir o mesmo número de arestas
• Ambos devem possuir o mesmo número de vértices com mesmo grau

Mas só isso não é suficiente. O isomorfismo entre dois grafos G e H é uma bijeção entre os conjuntos de vértices de G e H

f: V(G) -> V(H)

De tal forma que dois vértices u e v de G são adjacentes em G se e somente se f(u) e f(v) são adjacentes em H. Esse tipo de bijeção é comumente chamada de “bijeção com preservação de arestas”.

2) Se os planejamentos das estradas forem os apresentados abaixo, é possível dizer que elas representam a mesma estrutura? Como provar isso?

• Ambas as estruturas possuem 8 arestas
• Ambas as estruturas possuem 5 nós
• Ambas possuem o mesmo número de vértices com o mesmo grau.

Porém é preciso fazer uma equivalência entre os nós para conferir se são realmente isomorfos, para isso, precisamos achar pelo menos uma das equivalências possíveis entre ambas as estruturas, ou duas funções bijetivas.

Portanto os grafos apresentados são isomorfos.

3) Idem para os planejamentos abaixo:

4) O que há de diferente entre a resolução dos itens 2 e 3?

Não há necessidade de representar a f2 porque são grafos simples, então só é preciso encontrar f1.

5) Há algoritmo de tempo polinomial para determinar que 2 grafos são a mesma estrutura?

Não tem algoritmo determinístico, que não seja por força bruta.

---

1) Qual teoria da Teoria dos Grafos permite verificar a propriedade de existência ou não de cruzamentos entre arestas de um grafo?

R: Teoria dos Grafos Planos. Um grafo plano é um grafo que pode ser desenhado em um plano sem que nenhuma de suas arestas se cruze. Se um grafo não pode ser desenhado dessa forma, ele é chamado de grafo não-plano.

2) Há algoritmo para determinar a inexistência ou existência de cruzamentos entre as arestas de um grafo?

R: O Teorema de Kuratowski fornece uma condição necessária e suficiente para que um grafo seja plano. O teorema afirma que um grafo finito é plano se, e somente se, ele não contém um subgrafo que seja um homeomorfo de K5 (o grafo completo com 5 vértices) ou de K3,3 (o grafo bipartido completo com 3 vértices em cada conjunto).

Enquanto o Teorema de Kuratowski fornece a base teórica para a planaridade (identificando os subgrafos proibidos K5 e K3,3), sua aplicação direta para grafos grandes é computacionalmente complexa. Por isso, foram desenvolvidos algoritmos mais eficientes.

Principais Algoritmos para Teste de Planaridade:

• Algoritmo de Hopcroft e Tarjan (1974): Considerado um marco, foi o primeiro a atingir complexidade de tempo linear. Ele funciona com base em uma busca em profundidade (DFS) e utiliza uma estrutura de dados conhecida como "árvore de palm", que permite testar incrementalmente a planaridade do grafo. A implementação é complexa, mas é extremamente eficiente para grafos grandes.
• Algoritmo de Lempel, Even e Cederbaum (LEC, 1967), aprimorado por Booth e Lueker: Essa abordagem é do tipo "adição de vértices" e se baseia na ideia de construir o grafo passo a passo, adicionando um vértice de cada vez e verificando se a sub-representação planar ainda é possível.
• Algoritmo de Boyer e Myrvold (2004): Considerado um dos mais modernos e eficientes, este algoritmo também possui complexidade de tempo linear. Ele é baseado na adição de arestas e, em caso de não planaridade, ele pode até mesmo encontrar um subgrafo homeomorfo a K5 ou K3,3

3) Qual a relação entre cruzamento de arestas e grafos completos?

• R: A relação entre o cruzamento de arestas e grafos completos é direta e fundamental, e pode ser entendida a partir da propriedade de planaridade.
• Um grafo completo, denotado por Kn , é aquele em que cada vértice está conectado a todos os outros vértices. A questão do cruzamento de arestas surge quando tentamos desenhar esses grafos no plano.
• A relação é a seguinte: Grafos completos com 4 ou menos vértices (K1 , K2 , K3 e K4) são planares. Isso significa que eles podem ser desenhados no plano sem que nenhuma de suas arestas se cruzem.
• Qualquer grafo completo com 5 ou mais vértices (Kn , com n≥5) é não-planar. Isso significa que é impossível desenhá-lo no plano sem que pelo menos uma aresta cruze com outra.

4) Qual a relação entre cruzamento de arestas e grafos homeomorfos?

O termo "homeomorfo a" significa que um grafo pode ser obtido a partir de outro através de uma sequência de operações de subdivisão de arestas. A subdivisão de uma aresta é o processo de adicionar um novo vértice no meio de uma aresta, dividindo-a em duas. Se o grafo que os originou era planar, ele continuará sendo planar, e vice versa.

5) Há como provar que um grafo sempre possuirá arestas que se cruzam, independente da forma com a qual ele é desenhado?

R: Sim com o Teorema de Kuratowski. Para provar que um grafo é não-planar (ou seja, que ele sempre terá cruzamentos de arestas, não importa como seja desenhado), o método consiste em encontrar um subgrafo que seja estruturalmente "idêntico" ou homeomorfo a um dos dois grafos proibidos: K5 e K3,3.

6) Prove que o grafo a seguir sempre possuirá arestas que se cruzam:

R: Usando o grafo homeomorfo K3,3.

---

Sobre esse problema, responda os itens a seguir.

1) A empresa é especializada em passar fibra, mas não em instalar tubulação. Dessa forma, pergunta-se: a empresa deverá contratar outra empresa para construção de nova tubulação entre algumas cidades ou a tubulação existente é suficiente?

• O grafo em questão é conectado? Sim.
• O grafo em questão tem no máximo dois vértices com grau ímpar? Não. Então a empresa precisará contratar uma segunda empresa para construir mais tubulações.

2) Qual teoria da Teoria dos Grafos poderia ser utilizada para responder essa questão?

R: Caminho euleriano/ carteiro chinês. Circuito Euleriano: Se o caminho euleriano começa e termina no mesmo vértice, ele é chamado de circuito euleriano.

Para ter um circuito euleriano: O grafo deve ser conectado e todos os seus vértices devem ter grau par.

3) Como poderia ser classificado um Grafo que não necessita de nova tubulação para o problema em questão?

Grafo euleriano: Se o grafo possui um circuito euleriano (ou seja, um caminho que começa e termina no mesmo vértice e passa por todas as arestas), ele é chamado de grafo euleriano.

4) Há algoritmo determinístico de tempo polinomial que responde o item 1?

Do livro:

---

Sobre esse problema, responda os itens a seguir.

1) Qual teoria da Teoria dos Grafos poderia ser utilizada para auxiliar na determinação dessa rota?

R: Problema do Ciclo Hamiltoniano.

2) Como poderia ser classificado um Grafo que possibilita que todas as cidades sejam visitadas uma única vez, sendo que a rota inicia e finaliza em uma dada cidade?

R: Grafo hamiltoniano.

3) Como pode ser denominado o caminho que inicia e termina na mesma cidade e passa por todas as cidades uma única vez?

R: Ciclo hamiltoniano.

4) Há algoritmo determinístico de tempo polinomial que permite encontrar essa rota?

R: Não.

5) Qual problema da teoria dos Grafos possui aderência à rota que responde o item 3 e ainda minimiza a distância percorrida?

R: Problema do Caixeiro-Viajante.

Algoritmo de Huffman

Exercícios

1) Crie um diagrama de blocos, atividades ou fluxograma que ilustre as etapas de execução necessárias para o desenvolvimento do programa compactador.

R: Será demonstrado um compactador de texto.

2) Em quais situações espera-se que os códigos de Huffman funcionem bem e em quais situações se espera que ele não funcione bem?

R: Espera-se que ele tenha bons resultados quando a frequência de caracteres (usando o exemplo da última questão) varie bastante de um para o outro. Se a frequência fosse igual ou muito próxima, o algoritmo de Huffman não surtiria efeito na compactação dos arquivos.

3) Qual a relação entre o tamanho de um código e a frequência de um caracter correspondente?

R: quanto mais frequente o caractere, menor o código, e vice versa.

4) Descreva sucintamente a execução do Algoritmo de Huffman.

• R: Primeiro, o algoritmo analisa todo o conteúdo do arquivo para contar quantas vezes cada caractere (ou símbolo) aparece.
• Para cada caractere, é criado um "nó" de árvore contendo o próprio caractere e sua frequência. Utilizando uma fila de prioridade, o algoritmo repetidamente executa o seguinte processo:
• Pega os dois nós (ou sub-árvores) com as menores frequências.
• Junta os dois, criando um novo nó pai cuja frequência é a soma das frequências de seus filhos.
• Insere este novo nó de volta na fila.
• Isso continua até que reste apenas um único nó, que é a raiz da Árvore de Huffman completa.
• Com a árvore montada, os códigos binários são definidos pelo caminho da raiz até cada caractere (folha). Convencionalmente, descer para a esquerda adiciona um '0' ao código, e descer para a direita adiciona um '1'.

5) Assumindo que o algoritmo foi executado e a árvore gerada, descreva os processos de codificação de uma string e decodificação de uma sequência de bits

• Codificar (Texto → Bits):
  Troca-se cada letra do texto pelo seu código binário (ex: A vira 01, B vira 110) e junta em uma única sequência de bits.
• Decodificar (Bits → Texto):
  Utiliza-se os bits como um mapa para caminhar na árvore, começando do topo. Cada 0 significa "vá para a esquerda" e cada 1 "vá para a direita". Quando você chega em uma folha, encontra uma letra.

6) A partir da tabela a seguir, encontre os códigos de Huffman correspondentes, a árvore de Huffman e faça a codificação da string “grafo” e a decodificação da sequência de bits gerada a partir dessa string

Números em azul preenchidos após o procedimento.