Os Grafos e o Orkut

Vou neste e nos próximos artigos falar-lhes sobre a Teoria dos Grafos. É uma coisa que poderia ser complicada, então pra facilitar o entendimento eu fiz duas coisas:

  • Eu baixei um programa brasileiro chamado Rox, que foi feito em Java e é disponibilizado sob a GNU/GPL. Ele serve para facilitar o ensino da “Teoria dos Grafos” ajudando-nos a representar grafos e até executando algoritmos conhecidos de grafos no grafo que criamos.
  • Resolvi que trabalharemos sempre com exemplos da “vida real”. Neste artigo, vamos trabalhar com o Orkut como base, partindo do princípio que todo mundo sabe o que é o Orkut.

Neste primeiro artigo, só falarei sobre a definição do grafo e sua utilidade. Apresentarei as definições de: vértice, aresta, grau, grafo orientado, grau de entrada e grau de saída. Então, vamos lá!

A definição de grafo é muito simples. Segundo o Professor Cid Carvalho de Souza: Uma forma de representar uma relação binária entre elementos de um conjunto. Bom… É simplesmente uma representação de relações (que chamamos de arestas) entre objetos, que chamamos de vértices. Vamos logo ao exemplo: a amizade no Orkut.

Exemplo - Representação de um Grafo

Estão vendo esta árvore? Esta é a representação que chamamos de grafo. Vamos supor que este é o grafo das amizades do Orkut e as bolinhas nele são as seguintes pessoas:

  1. Eu
  2. João
  3. Maria
  4. José
  5. Pedro

Eu (número 1) tenho dois amigos: o João (número 2) e a Maria (número 3), porque estou ligado a eles. O João (número 2) tem três amigos: eu (número 1), a Maria (número 3) e o José (número 4). E assim podemos fazer com os outros contando as linhas que saem de cada pessoa.

Cada pessoa é um vértice e cada linha (relação entre duas pessoas) é uma aresta. Dizemos que é uma relação binária lá em cima, porque a relação é sempre entre dois vértices.

Os números de amigos que cada pessoa tem (o número de relações que cada vértice tem) é o que chamamos de “grau” de um vértice. Grau dos vértices do exemplo acima:

  1. 2
  2. 3
  3. 2
  4. 2
  5. 1

Pra quê serve o grafo?

Ora, se você consegue contar as arestas que saem de cada vértice na programação (se você sabe fazer algo básico como calcular o grau de um vértice), você pode oferecer seus serviços ao Google e ganhar milhões, pois, como todos sabem, o Orkut não sabe fazer isso direito!

Brincadeiras a parte… Grafos são extremamente úteis porque são representações bastante simples (você teve dificuldade para entender minha árvore ali em cima?) e essa estrutura deles aparece em muitos problemas computacionais. Além disso, existem muitos algoritmos eficientes para problemas complexos que utilizam estas representações.

Definições até agora

Traduzindo os conceitos do Orkut para os grafos:

  • Vértice: Pessoa.
  • Aresta: Amizade entre uma pessoa e outra.
  • Grau de um vértice: Número de amigos de uma pessoa.

Grafos Orientados

Um grafo é orientado quando eu sou seu amigo, mas você não é meu amigo. Você sabe que um grafo é orientado através da representação quando ele tem “setinhas”, como o grafo abaixo.

Grafo orientado

Vamos supor que isso aí é um mapa do Brasil. Ele despreza as cidades que não são importantes para o país, levando apenas em consideração portanto: São Paulo, Florianópolis e Itajaí.

  • São Paulo é a bolinha vermelha.
  • Florianópolis é a bolinha amarela.
  • Itajaí é a bolinha azul.

As arestas indicam que há uma estrada para você ir de uma cidade para a outra, mas só dá pra ir no sentido da estrada, que as setas representam. Portanto, você pode ir de São Paulo, de São Paulo a Itajaí e Florianópolis a Itajaí, mas não de Itajaí para qualquer outro lugar.

Grau dos Vértices

Os graus dos vértices neste segundo grafo seriam os seguintes, certo?

  • São Paulo: 2
  • Florianópolis: 2
  • Itajaí: 2

Quase… Porém, nos grafos orientados nós temos dois tipos de grau diferentes. Dizemos que:

  • grau de entrada é o número de arestas que apontam para o vértice; e
  • grau de saída é o número de arestas que saem do vértice.

Portanto, os graus de entrada do nosso grafo são:

  • São Paulo: 0
  • Florianópolis: 1
  • Itajaí: 2

E os graus de saída:

  • São Paulo: 2
  • Florianópolis: 1
  • Itajaí: 0

Onde mais posso utilizar grafos?

Existem vários casos onde você vai querer usar grafos:

  • Mapas
  • Sua árvore genealógica
  • Hierarquia de uma empresa
  • Sistema de amizades do seu sistema de comunidades virtuais
  • … e muito mais. Na OBI já apareceu até um jogo de dominó como problema de grafos!

Como veremos nos próximos artigos, tem algoritmo pra fazer “tudo” em grafos… Então representar alguma coisa em grafos é muito útil pra poder descobrir uma série de coisas.

A maioria das páginas que eu conheço sobre grafos são muito malignas porque apresentam uns 50 conceitos diferentes de grafos juntos (ex.: grafo conexo, grafo desconexo, caminho, ciclo, etc.). Nos meus artigos, devo tratar um assunto de cada vez para facilitar o entendimento. Então, vou parar por aqui hoje.

No próximo artigo: Como representar um grafo na programação? Você já pode ir pensando nisso…

1,365 thoughts on “Os Grafos e o Orkut

  1. Vicki, I heard about this–or a similar study–years ago when I worked at Time-Life Books. Those series, which covered subjects ranging from the Civil War to Mysteries of the Unknown, were great reads. I believe some Time-Life volumes may even have been used in such a study. It was a great selling point, and of course a source of pride to those of us creating the books. Thanks for bringing this up!

  2. I wanted to send you that little bit of word so as to say thank you again with the unique views you have shared above. It has been so surprisingly open-handed with you to provide freely exactly what numerous people might have offered for sale as an ebook to generate some cash for themselves, specifically considering that you might well have done it in the event you decided. These thoughts likewise served to be the great way to realize that other people have a similar desire just like my very own to know whole lot more pertaining to this matter. I believe there are numerous more pleasurable occasions up front for those who go through your site.

  3. A lot of thanks for your whole effort on this blog. My mom takes pleasure in doing internet research and it is simple to grasp why. We hear all relating to the lively means you render informative guidance on your website and therefore cause response from other individuals on that point and our favorite girl is really discovering a lot. Enjoy the remaining portion of the year. You are always doing a first class job.

  4. Do attorneys utilize investigators as much as they could?Portland, Oregon Private Investigator Dawn R. Krantz-Watts asks if attorney utilize private investigators as much as they should. Her opinion in a nutshell, is that they don’t. That if they did, the attorneys clients would benefit. Read more at her

  5. My husband and i have been very lucky when Michael could finish up his basic research out of the precious recommendations he came across through the web pages. It is now and again perplexing just to continually be giving away techniques which people today have been making money from. Therefore we see we’ve got you to thank because of that. Those illustrations you made, the simple web site menu, the relationships your site aid to promote – it’s got mostly spectacular, and it’s making our son and our family consider that this content is entertaining, and that’s extraordinarily vital. Thanks for the whole lot!

  6. Thank you a lot for providing individuals with an extremely breathtaking opportunity to discover important secrets from this website. It’s usually very enjoyable and as well , full of a lot of fun for me and my office mates to search your blog no less than thrice per week to read through the fresh things you will have. And of course, we’re always impressed considering the gorgeous techniques served by you. Some 2 areas in this post are unequivocally the most efficient we have ever had.

  7. Hello, I`m really happy that we could create and share with you such information about pigeons. We like to share my passion – the pigeons – with others. Soon we will some new stuff and hope you will find that interesting. Thank you for your appreciation.

  8. Jag väntar fortfarande på att Hoppas ska komma med posten.:) Beställde för en eeeeevighet sedan. Om den lever det minsta upp till hennes tidigare böcker så förtjänar Strollo alla pris hon kan få, dock!

  9. I have to voice my admiration for your generosity supporting folks who really need help with this important niche. Your real commitment to getting the message all around ended up being remarkably helpful and have consistently encouraged some individuals just like me to arrive at their objectives. Your amazing invaluable publication denotes so much to me and somewhat more to my office workers. Thanks a lot; from everyone of us.

  10. A1528 : Cassandre, Hercule, Sig, Hector, m’aiderez-vous à reprendre pied dans le siècle ?Oui, bien sûr, avec plaisir, dans la limite de mes moyens. Mais à la condition expresse que vous cessiez de vous livrer à ce genre de plaisanterie : « Il est probable que le temps tranche, comme toujours, et qu’un jour, lassé de ce dilemme, je tire pour de bon ma révérence, en vous laissant libre un champ que vous me reprochez de vouloir régenter. C’est probable, mais je ne m’y résous pas encore. Â»Ce n’était pas drôle du tout.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>