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…

794 thoughts on “Os Grafos e o Orkut

  1. Amat mengaibkan dalam pilihanraya negara demokrasi bila banyak halangan dan syarat di knekan pada phak pembangkang. Lebih dasyat bila pihak polis bertndak saperti sayap parti pemerentah untuk gempur pembangkang..

  2. WHY would he disqualified if he gave his 10000 plus,that is a fix against him or what?any way he can win just the same, if they want to play that dirty game on him.CURT, MERRY CHRISTMAS TO YOUReply

  3. . Your favourite justification seemed to be on the internet the easiest thing to understand of. I say to you, I definitely get irked while other folks consider worries that they plainly do not know about. You managed to hit the nail upon the highest and defined out the whole thing with no need side effect , people can take a signal. Will probably be again to get far more. Thank you!

  4. bayan eskort servisi web tasarımı, internet sitesi google optimizasyonu eskort kızlar escort bayan escort girls. türkiyenin özel kızları burada türkiyenin eskort kızları bayan erkek eskort servisi istanbul ankara izmir köpek eğitimi ve bakımı Sohbet siteleri chat islami evlilik siteleri bayan partner siteleri arıyorum en güzel kızlar bu sitede ücretsiz üyelik sistemi ytrg

  5. I add my voice to those who strongly suspect that the explanation for the data is your choice #4: Autistics self-report with more honesty. They may also be more honest with themselves about such issues. My data: heterosexual and polyamorous, vocal supporter of LGBT rights.

  6. Jaloers makend, die prachtige foto’s. Wat een geweldige tocht. Jammer dat jullie niet een wat groter “bereik” hebben om de nuances in het denken over anderen aan te kunnen boren.Goede reis, verder en blijf genieten!Warme groet,Loes Versteeg

  7. Hi Darren,Thanks for the comment. It definitely was hard for us to get rid of our house, car and possessions. However, I have found it incredibly liberating to be free of attachments. It opens up so much time. Don’t worry about being the only weird old guy, there are many of them around.

  8. I in addition to my friends came checking out the great advice on your web blog and immediately got an awful suspicion I had not expressed respect to you for those strategies. My boys became certainly very interested to study all of them and already have sincerely been taking pleasure in those things. Thank you for turning out to be well considerate and for picking this kind of brilliant resources most people are really desperate to be aware of. My sincere regret for not expressing gratitude to sooner.

  9. Hola! Quería preguntarles si alguno conoce algún juego bueno para pc, así como el Metal Gear Substance 2, o el Resident Evil 4, Doom 3, etc. que me diga el nombre así me lo descargo, por favor. Los de mi preferencia son los de acción. Desde ya muchas gracias gente!

  10. Thank you a lot for sharing this with all folks you really realize what you’re speaking approximately! Bookmarked. Kindly additionally consult with my web site =). We could have a link change agreement among us!

  11. Except PSD tuts all are new to me. Learning Photoshop is very essential for a blogger. Atleast we need to able to make small changes to logo or design if needed.Thanks mate for adding some worthy things here.~@Khajamoin1

  12. Wonderful story, reckoned we could combine a few unrelated data, nonetheless genuinely worth taking a search, whoa did one study about Mid East has got additional problerms at the same time

  13. => Ge’ez“There are some simple rules to follow when attempting to produce scholarly history.”Such as “Have Communist files declassified and open to the public as soon as possible”? In one-time act of all-encompassing lustration? That other Soviet-bloc countries could have? And that Mr Donald Tusk said to support, only to change his mind when come into power”? But who is going to scholars, pray?=> Pawel,You used the word “reportedly”, and alongside we have Ge’ez to discredit Secret Police stuff. Why? Horseshit for rumor-mongerers. Reported by Ge’ez Guesses Inc.

  14. hmmmmmmmmm byłem na koncercie "Niczym Grzegorz Markowski wraz ze Zbigniewem Hołdysem w roku 1987 na warszawskim Stadionie Dziesięciolecia rozpoczynając największy koncert muzyczny w Polsce" i dobrze ze projekt bedzie rozwijany ?a co do publikacji : kwintesencja profesjonalizmu wypada glosno powiedziec DZIEKUJE :)

  15. The owners better be prepared to face some opposition if any rezoning (or any other action from the city) is required. The historic district types might fight it. They fought a bar going on the west site of College Ave. between Maple and Lafayette streets and a cell tower going up behind the two-way radio place on College.

  16. schedule on her blog of all the cool wedding-related things going on in Dallas every weekend. This week is especially exciting because there will be a Monique Lhuillier showing at Neiman Marcus downtown!

  17. “Think they should’ve blown up Brody in the finale and not have him suddenly get a conscience because of his daughter.”Did you see what happened AFTER the bomb sequence? You know, the sequence where he KILLS his former marine buddy. From what I could guess, Brody made the decision to protect his family … and only his family. He couldn’t care less about other people, as long as his family doesn’t get hurt, which makes him even more calculated in his thinking and process.

  18. SÃ¥ flott det ble!! Kan du begripe at de kommer kun i gult og sort?? Du gav meg noen gode ideer, jeg kommer nok til Ã¥ gjøre dem om til hvite… Ha en fin helg

  19. Oh, I’ve been looking forward to Dage’s story! Can’t wait to read Claimed! I’ll have to add it to my review list for sure. I also need to write a new review for Fated and move it over to my new review site. Someday. When I catch up with the rest of my life. LOL And pretty orange. It looks Halloweeny.

  20. I love your posts and bought your book because of the thoughtful ,insightful perspective on these important issues. As for providing advice by phone on specific personal issues , I believe it ought to be for a fee . It just makes sense.

  21. Die letzten “Jahrzehnte” haben wir treu Winter für Winter für die ganze Familie Jahresplaketten gekauft, ob wir sie “rausfahren” konnten oder nicht. Aber unter diesen Bedingungen werden wir dieses Geld in Sprit umsetzen und zum Kniebis fahren – Herrenwies ist eh nicht mehr schneesicher. Schade.

  22. Hamilton pode conquistar dez, quinze títulos, mas, para mim, o melhor dessa geração é Vettel. Só pela vitória com Toro Rosso (ganhar com Mclaren, com todo o respeito, é um trabalho muito menos árduo) em Monza e pelo show de simpatia, já merece meu respeito e admiração.

  23. Mulher Procura Homem Brasil

    Uma dor intensa a amor com a mulher dos sonhos é que diversos
    homens desejam, e também um estimulante sexual nascido publicado como Viagra Genérico é possível que ajudar nesse quesito No entanto, nem todos bem como cada um dos homens sabem disso e também
    não são toda gente que dispõem justamente a mesma virilidade
    e vigor da mocidade bem como similarmente isso finaliza se
    tornando qualquer grande dor de testa e inclusive ainda pretextar vários
    constrangimentos, se desempenho sexual deixar a desejar.
    Razão estes desvantagens Xtrasize Original preço onde
    comprar , uma grande empresa voltada a construção de produtos naturais, conhecida tal como Healwheel Laboratories, acabou desenvolvendo e patenteando uma fórmula exclusiva
    com os ingredientes afrodisíacos naturais mais potentes para aumentar
    desempenho sexual masculino.

    Jamais podemos nos olvidar do aspecto punitivo-pedagógico do devastação vontade,
    decorrente da doutrina Norte Americana do punitive damage, inteligentemente introduzido na
    Jurisprudência Nacional, que deve pautar as condenações
    a fim de desestimular os fornecedores de produtos a reincidir na
    prática censurada, sob pena de odiosa impunidade.

    É filho matando a mãe, pai matando filho, enfim todo característica de
    morte.Há crianças e adultos morrendo a fome, pestes e doenças devastando regiões.A cada dia que
    fumaçada qualquer nova bactéria é descoberta pela ciência.São
    os vírus que estão em mutação.Há também a loucura invadindo a mente do homem deixando- deprimido e sem ângulos na alimentação.

    Aliás, são diferentes apenas na medida em que mulheres não choramingam por aí que “já não tem melhor homens virgens em idade casadoira nesse mundo improdutivo e ateu”.
    Prepare-se para ler em cima de sua cultura, converse com pessoas que já se
    relacionam com mulheres do Brasil e colete todo tipo com informação.

    A nicotina dificulta a buraco de sangue no pênis, consequentemente a ereção.
    Paralelamente, alguns estudos afirmam que as crianças de
    mães que mantiveram relações sexuais frequentes ao longo de a gestação
    são em grau superior confiantes, tranquilas e felizes.

    Com nascente álbum começam dois anos de sucesso nos maiores festivais do mundo.

    Se você já namorou ou namora alguém muito mais
    novo, falece conseguir entender bem os pontos que separamos nessa lista
    em cima de esse tipo de relacionamento. Porém não tem
    vazio nenhum, é só muito amor pra dar bem como pouca vida
    pra ser desperdiçada.

    Sr. Alexander não reconhece delinquente de primeira instância, pois enquanto estava em sua casa, DeLarge usou qualquer máscara, porém, ao tomar um bom banho começa a cantar a
    música a quem cantava enquanto estuprava a mulher a Alexander (Singing In The
    Rain). Ao inverso do Viagra, afrodisíaco natural é um tipo de remédio para aumentar
    prazer feminino que estão disponíveis sem receita médica e
    salubre mais baratos do que Viagra.

    Talarurus idade um dinossauro pertencente
    a casta dos anquilossauros que viveu há aproximadamente 70
    milhões de anos atrás ao longo de final do período Cretáceo na Mongólia,
    como todos de sua casta, possuía enormes placas ósseas que funcionavam como uma armadura protetora ao longo de todo organismo, com
    enormes “espigões” que juntamente com a clava ( maça
    ) na ponta da cauda, tornavam uma verdadeira “máquina de guerra”.

    No caso dos homens seus efeitos são ainda mais visíveis com relatos de melhoras
    significativas proporcionando ereções mais fortes e potentes e também
    orgasmos em grau superior intensos por isso é
    muito utilizada na fabricação de remédios bem como suplementos para tratamento para impotência masculina.

    Não foram apresentados efeitos colaterais relativos ao uso do
    produto. Porém, para efeitos também mais prazerosos, um apertado extra 30 minutos
    antes da correlação venéreo irá sopitar as atividades.
    Na casa de 1940, melhor inovação: em 1941 se tornou uma das primeiras empresas a responder formalmente as
    dúvidas e queixas dos consumidores. http://www.interactingwithcomputers.com/__media__/js/netsoltrademark.php?d=goldet5a0l.uniterre.com%2F387106%2FUna%2BKpoper.html/

  24. Mohon dikomentari ya mbak. Maaf telat reportasenya.salam Omjay wijaya kusumah selesai posting Sumpah Pemuda dan Jiwa Kepahlawan di Era Multitasking yang Beretika

  25. that the cover matches your requirements. Ranges of cover can vary significantly, so don’t make the error of assuming that all parts of your car are covered.3. Verify what a car guarantee business require of you. Vehicle guarantee insurance policies are very significantly a two-way arrangement. Insurance policies will usually have constructed-in demands that are made on you.If you fail to adhere to the policy properly then the guarantee might turn out to be invalid

  26. Elsa, ett varmt tack för dina varma ord. Det gläder mig att du tycker om det du läser på min blogg och vill dela med dig av det.Jag vill önska dig varmt lycka till på din egen resa mot ett liv utan socker. Tack för att jag fick ta del av dina tankar på din fina blogg.Varma hälsningar

  27. Tykkään kanssa kovasti blogistasi. Ja paljon hyödyllistä olen oppinut. Mutta Regina ei kyllä mullekaan avaudu. Kehujesi takia olen yrittänyt kuunnella, mutta ei kun ei…t:mari

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>