Algoritmos Computacionais

Os Grafos e o Orkut

January 22, 2006

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.

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?

Oras, 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! Hehehe...

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 quando ele tem "setinhas", como o grafo abaixo.

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... hehehe
• ... 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...

Espero que vocês tenham gostado. Qualquer coisa, comentem ou me enviem um e-mail.

Compare Preços de: notebooks, acer aspire, hp pavilion, computadores, pentium 4, nintendo wii, ps3, celulares, câmeras digitais

Categoria(s): Grafos

19 comentários

Escreva um comentário

Dados pessoais

Seu e-mail não será publicado, mas você deve informá-lo para o autor poder responder seu comentário.

• Nome
• E-mail
• Website

HTML 4.01 Strict: Você pode usar as seguintes tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Artigos relacionados:

• Representando Grafos na Programação
• Escada perfeita (OBI2006)
• Grafos Ponderados
• O que é um algoritmo?
• Recursão

53 assinantes

Mais artigos

• Crivo de Eratóstenes
• Escada perfeita (OBI2006)
• Grafos Ponderados
• Representando Grafos na Programação
• Os Grafos e o Orkut
• Conclusão sobre Ordenação
• Mini-Poker
• Ordenação por Seleção
• Ordenação por Inserção
• Introdução à Ordenação
• Recursão
• Análise de Algoritmos
• Qual a utilidade do algoritmo?
• Como representar um algoritmo?
• O que é um algoritmo?

Comentários recentes

• Matheus Eduardo Maura: Faço engenharia eletrica-eletronica( UNIRP SÃO JOSE DO RIO PRETO), e...
• rafael: muito legal o artigo mas teria como resolver esse algoritmo nao consegui de jeito nenhum,...
• Roger: Bom artigo. Podia atualizar esse site
• Aline Celestrino Bento: o que É ALGORITMO=exemplo:35 :7 porque eu ñ sei ALINE
• Claudio: eu gostaria de saber este algoritmo: faça um algoritmo que determine, para um digrafo,...
• ingrid morgana gomes paes: que bacana que legau isso e emtesamte e legau para apremder mais a...
• Filipe Névola: filipe.bico@hotmail. com
• Filipe Névola: Boa noite, gostaria de saber se você tem alguma implementação de menor caminho...
• Carlos Luiz Silva Meirelles: estou fazendo curso de informática gratuito patrocindo pelo estado....
• Maria Regina de Queiroz: Olá Tiago, li os seus artigos e gostei muito, gostaria se possivel que...

Categorias

• Algoritmos gulosos
• Básico
• Curiosidades
• Grafos
• Ordenação

Escrevo também...

• Tiago Madeira
  Site pessoal e blog do autor destes artigos
• Mal Vicioso
  Blog sobre filosofia e sobre a hipocrisia da sociedade

Links

• USACO Training Gateway
• Universidad de Valladolid
• Programming Challenges
• Olimpíada Brasileira de Informática
• International Olympiad in Informatics

Sobre o design

Este design foi copiado do CSS Zen Garden e modificado com autorização de seu autor, Gunta Klavina.

Licença

Todo o conteúdo deste site (incluindo textos, imagens, arquivos de áudio e quaisquer outros trabalhos), exceto quando especificado o contrário, está licenciado por Tiago Madeira sob uma Licença Creative Commons.