A orientação em grafos - Grafos

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Já estudamos anteriormente que é possível mapear diversas situações do mundo real em grafos (clique aqui para ler a nossa primeira postagem sobre grafos). Trajetos, labirintos, linhas de transmissão de energia, linhas férreas, jogos e até uma viagem em família são grandes exemplos da presença desse ramo da matemática no nosso dia-a-dia. Contudo, em todos esses exemplos uma característica ainda não foi analisada, a direção. Até agora não nos preocupamos com este ponto especificamente porque todos os nossos exemplos cabiam em grafos não orientados.

Porque a direção seria importante em um grafo ? A resposta é simples. Imagine que você está mapeando em um grafo o trajeto de carro que parte de um ponto A e vai para um ponto B. Como você sabe as ruas têm direções e muitas vezes quando se está dirigindo só é permitido seguir um tipo de sentido. Logo, tal característica também deve ser refletida em um grafo, pois a orientação mostra quais os trajetos são possíveis de um ponto origem para um ponto destino.

Quando estávamos estudando grafos não orientados podíamos simples sair de um nó A passar em vários outros até chegar ao nó Z, por exemplo. Bastava somente que existisse arestas que fizessem essa conexão, direta ou indiretamente. Contudo, com grafos orientados a história é outra. Se existir um único caminho que leve de A à Z, é esse que deve ser seguido e não há a possibilidade de fazer esse trajeto sem ser por esse caminho. Se houver mais de um caminho, sem problemas, os dois podem ser percorridos. Mas, se não houver caminho que ligue A à Z, ele se torna inalcançável a partir de sua origem.

A Figura 1 mostra dois grafos com a mesma disposição de nós e arestas, só que o grafo acima é orientado e o abaixo é não orientado.

Figura 1 - Um grafo orientado e um grafo não orientado

Conforme já comentado anteriormente, em um grafo orientado pode ser que só exista um caminho que liga um nó a outro. Na Figura 1 tal situação acontece e é representada pelo seguinte trajeto: A-B-E-F-J-H-Z.

Um outro ponto que também deve ser analisado é como a orientação de um grafo se reflete em sua matriz ou lista de adjacências, quais são os impactos disso. Antes tínhamos de nos preocupar em representar de forma bidirecional a conexão entre dois nós, ou seja, se A fosse conectado à B tínhamos que fazer uma marcação nas células AB e BA da matriz, onde a primeira letra representa a linha e a segunda a coluna. Agora isso não é mais necessário pois a direção da aresta dita qual célula deve ser preenchida, característica a qual não existia antes em grafos não orientados. Se em A houver uma aresta que parte para B, então somente a célula AB receberá a marcação. Caso contrário, somente a célula BA recebe. No caso de uma lista de adjacências o comportamento descrito acima se repete, logo o que mudaria é que uma das posições da lista não teria a conexão oposta pois o sentido é único. Caso o assunto seja estranho para você, recomendo a leitura do nosso segundo post sobre grafos.

Figura 2 - Grafos orientado e não orientado com suas respectivas matrizes de adjacência

Com a Figura 2 a diferença entre as matrizes de adjacência se torna muito óbvia, pois o fenômeno descrito no parágrafo acima é representado. Para um grafo não orientado, metade da matriz de adjacência espelha a outra metade, portanto, a metade das células se tornam redundantes. Porém, para um grafo orientado, toda célula da matriz transmite uma informação única (LAFORE, ROBERT). Não utilizei o grafo da Figura 1 porque ele possui muitos nós e arestas, e isso concluiria em uma matriz muito extensa, atrapalhando assim o nosso exemplo.
Levar toda essa teoria para a prática resulta na criação de um simples método que faz a marcação explicada na matriz de adjacência. Como sempre, é possível obter todo o código desenvolvido até essa postagem no repositório GitHub (link no fim do post) do projeto. Faça o download, dê uma olhada e deixe aí sua opinião. A frente, estudaremos algoritmos específicos para este tipo de grafo, não perca.

Com isso chegamos ao fim de mais uma postagem. Se você gostou compartilhe com seus amigos, se inscreva no blog e curta a página no Facebook.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Árvores geradoras mínimas - Grafos 

Download do código-fonte
Link do repositório GitHub: https://github.com/PrecisoEstudarSempre/Graphs.git

Dúvidas !? Sugestões ?! Críticas ou elogios ?!

Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

LAFORE, ROBERT; Estruturas de Dados e Algoritmos em Java; 2004