Atividades Sobre Grafos

[pic 1]

Estrutura de Dados II

Nome: Gabrielle Lattanzi Martins

Grafos

 “Grafos são uma das estruturas mais versáteis usadas em programação de computadores, são parecidas com Árvores (em verdade, Árvore é um tipo/subconjunto de Grafo). Grafos geralmente têm uma forma ditada por um problema físico ou abstrato. Por exemplo, nós em um grafo podem representar cidades e arestas podem representar rotas de voos de linhas aéreas entre as cidades. Outro exemplo, um grafo associado às tarefas individuais de um projeto onde nós podem representar tarefas e arestas orientadas (por setas) indicam qual tarefa tem que ser completada antes da outra.“ (LAFORE, 2004). “Logo, grafo é uma coleção de vértices (ou nós) e as conexões entre eles. Em geral, nenhuma restrição é imposta ao número de vértices ou ao número de conexões que um vértice pode ter para outros.” (DROZDEK, 2016).

Com base nas duas referências conceituais citadas acima, desenvolva o seguinte estudo dirigido:

1. Defina os seguintes conceitos básicos sobre grafos (vide LAFORE, 2004 – Cap. 13, p. 562):

Adjacência: Um nó é qualificado como adjacente a outro nó quando a distância entre eles é de apenas 1 aresta.

Caminhos: Sequência finita ou infinita de vértices conectados por uma sequência de arestas.

Grafos conectados: É chamado de conectado se a substituição de todas as suas arestas direcionadas com arestas não direcionadas produz um grafo (não-direcionado) conectado 

Grafos ponderados: Quando suas arestas possuem um peso.

1. Seguindo a ideia de definições de conceitos tratada anteriormente, vide Drozdek (2016 – Cap. 8, p. 340-341) e defina as formas de grafos:

Simples: Se ele não tem laços nem mais de uma aresta ligando dois mesmos vértices.

[pic 2][pic 3]

Multigrafo: Pode possuir arestas múltiplas (ou paralelas), ou seja, arestas com mesmos nós finais.

[pic 4]

Ponderado: Quando suas arestas possuem um peso.

[pic 5][pic 6]

Subgrafo: Um subgrafo de um grafo é uma parte do grafo.

[pic 7][pic 8]

1. Com base nas referências citadas, grafos têm arestas de conexões entre nós controlados por uma matriz, o que permite a implementação destes. Logo, explique como funcionam:

Matriz de adjacência: Identifica a relação de adjacência entre vértices.

[pic 9] [pic 10] [pic 11]

[pic 12]As colunas e as linhas representam vértices. Quando um vértice da coluna C1 é adjacente à um vértice da linha L1 identificamos com 1 na matriz. Quando não há adjacência entre eles identificamos com 0.

Matriz de incidência: Identifica a relação de cada vértice com as arestas.

[pic 13] [pic 14]

[pic 15]Nesse exemplo, as colunas representam as arestas e as linhas os vértices. Sendo assim, quando um vértice 1 é ligado à outro vértice pela aresta a, identificamos com 1 na matriz. Quando não há essa relação entre eles identificamos com 0.

1. Uma das operações mais fundamentais para executar em um grafo é localizar quais nós podem ser alcançados a partir de um nó especificado. Neste contexto, algoritmos de busca são propostos para grafos, muitos deles similares aos aplicados em árvores, como os tipos: Busca em Profundidade e Busca em Largura. Explique, por meio de um exemplo prático, ambas as técnicas de busca em um mesmo grafo. Vide Lafore (2004, Cap. 13, p. 579-586) e/ou Drozdek (2016, Cap. 8, p. 343-354).

Busca de Profundidade (DFS): ”Cada vértice V é visitado e, para cada vértice adjacente à esse vértice V que ainda não foram visitados, é visitado.” -Drozdek, Adam

Para cada vértice, é atrelado um número. Se o vértice V não tem adjacentes e os todos os seus adjacentes já tiverem sido visitados, voltamos para o vértice anterior à V. A travessia acaba quando as visitas e o processo de volta ao antecessor volta para vértice V (que iniciou). Caso ainda tenham vértices não visitados no grafo, a Busca continua reiniciando para os vértices não visitados.

Complexidade: O(|V|+|E|)

[pic 16]

Nesse exemplo, iniciamos a partir do vértice a e atrelamos à ele o número 1. Verificamos que a possui 4 vértices adjacentes (e, i, f e g). O vértice e é escolhido para a próxima chamada da Busca de Profundidade e atrelamos à ele o número 2. Esse vértice tem 2 adjacentes que ainda não foram visitados (i e f), então escolhemos um deles (f) para chamar novamente a Busca de Profundidade. Atrelamos à ele o número 3 e verificamos que ele possui apenas 1 vértice adjacente não visitado (i), logo, chamamos a Busca de Profundidade também para ele. O vértice i é atrelado ao número 4 e só possui vértices que já foram visitados, por isso, sua função é completada e assim será recursivamente para as funções que estavam em aberto dos vértices f, e e a, nessa ordem.

Busca em Largura (BFS): Primeiro localizamos todos os vértices adjacentes ao vértice V, antes de ir para os outros vértices, enquanto a Busca de Profundidade escolhe um vértice adjacente à V e vai visitando o adjacente do adjacente antes de visitar os vértices vizinhos de V.

[pic 17][pic 18]

[pic 19]

Pseudocódigo do livro do Adam Drozdek.

1. Percorrendo um caminho mais curto: suponha que um grafo foi usado para representar caminhos e distâncias entre cidades para um determinado Caixeiro Viajante (exemplo clássico da Teoria de Grafos). Explique como o algoritmo de Dijkstra poderia ser aplicado para escolha de uma rota ótima entre cidades? Vide exemplo e teoria em Drozdek (2016 – Cap. 8, p. 346-350).

No algoritmo de Dijkstra, um número de caminhos p1, …, pn partindo de um vértice V são testados e o caminho mais curto entre eles é escolhido. Depois que um vértice é visitado, ele não é mais usado. O algoritmo termina quando todos os vértices forem visitados.