Pular para o conteúdo principal

Introdução à Teoria dos Grafos

A Teoria dos Grafos é uma das mais interessantes e promissoras áreas da Matemática, possuindo diversas aplicações em vários campos da sociedade, da Ciência e dos Negócios. Neste post, vamos entender o que é um grafo e conhecer alguns conceitos fundamentais, como vértices, arestas e grau.



Representação das pontes de Königsberg


Essa interessante teoria se iniciou no século XVIII, quando na cidade de Königsberg, na Prússia, - hoje Kaliningrado, uma parte da Federação Russa - havia sete pontes que conectavam as margens e as ilhas do rio Pregel. Os habitantes daquela cidade gostavam de passear e se perguntavam se poderia ser possível iniciar um passeio em um determinado ponto, cruzar cada uma das pontes exatamente uma vez e retornar ao ponto inicial.


Representação gráfica das pontes de Representação das pontes de Königsberg


Em 1.736, o famoso matemático Leonard Euler publicou um artigo com a solução do problema, através de uma das primeiras utilizações conhecidas da teoria dos Grafos, representando as regiões como vértices e as pontes como arestas.


Formalmente, então, dizemos que um grafo G(V, E) consiste de um conjunto de vértices V e um conjunto de arestas E. Cada aresta é um par não ordenado de vértices {i, j}, chamados de extremidades da aresta. Em geral, representamos os vértices por pontos ou por círculos e as arestas por segmentos de retas ou por linhas curvas.


Dizemos que uma aresta é incidente aos vértices aos quais ela está associada e vice-versa. Duas arestas que são incidentes ao mesmo vértice são chamadas de adjacentes. Um grafo possui arestas múltiplas se existem duas ou mais arestas incidentes ao mesmo par de vértices. Chamamos de laço as arestas cujas extremidades são o mesmo vértice.


Um grafo é chamado simples se ele não possui laços ou arestas múltiplas; caso contrário, ele é chamado de multigrafo. O grau de um vértice é o número de arestas incidentes a ele, sendo que um laço conta como dois. O grau de um grafo é a soma do grau de todos os vértices. Um vértice de grau zero é chamado de vértice isolado; um vértice de grau um é chamado de pendente.


Um grafo é chamado de orientado ou de dígrafo se há um sentido imposto nas arestas que ligam dois vértices.. Neste caso, as arestas orientadas são associadas a pares ordenados, e não a conjuntos. Um grafo que possua tanto arestas orientadas como não orientadas é chamado de misto.


Existem muitas aplicações da teoria dos grafos em nosso cotidiano, conforme veremos a seguir:



Google Maps


Tela do Google Maps


O famoso serviço de mapas da gigante de buscas Google nada mais é do que uma aplicação direta da Teoria dos Grafos. Nele, as ruas são as arestas e as esquinas são os vértices. Quando pedimos ao serviço para que ele nos indique qual o caminho mais rápido de um lugar a outro, ele atribui um determinado valor a um conjunto de ruas e decide qual percurso terá a menor soma.



Redes sociais


Grafo do Twitter


As famosas redes sociais também são uma aplicação da teoria dos grafos. No caso acima, que ilustra um grafo da rede social Twitter, podemos associar os usuários aos vértices e utilizar arestas orientadas caso um usuário A siga outro usuário B. Essa abordagem permite modelar um grupo social e planejar campanhas de marketing. Os famosos seis graus de separação, teoria a qual afirma que quaisquer duas pessoas no mundo estão conectadas por, no máximo, seis conhecidos em comum, e que se popularizou na época do finado Orkut, é uma aplicação desse campo que veremos em breve.



A World Wide Web


Grafo da World Wide Web


A parte mais conhecida e usada da Internet pode ser modelada como um grafo orientado na qual cada página é representada por um vértice e em que uma aresta começa na página A e termina na página B se e só se existir um link na página A que leve à página B. Como tais páginas são criadas e excluídas a todo instante, esse grafo está constantemente se modificando. Um estudo recente apurou que esse grafo tem mais de 129 bilhões de arestas. O grafo da Web é utilizado, entre outras coisas, para computar o PageRank, índice pelo qual o Google classifica a relevância dos resultados das buscas nele realizadas.

Comentários

  1. Olá, André!

    Que ótima aplicações matemáticas você compartilhou conosco. E ainda com alguns dados históricos ficou ainda melhor.

    Um abraço!

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Como acessar configurações avançadas no Sagemcom F@st 2704N

NOVO TUTORIAL: GUIA DEFINITIVO DAS CONFIGURAÇÕES AVANÇADAS DO SAGEMCOM F@ST 2704N!
Atualização 23/01/2015: Alguns problemas apontados e descobertos nesse modem:
1. Alguns usuários relatam dificuldade em salvar alterações na configuração ADSL;
2. Não sei como acessar os logs do modem; mesmo habilitando, eles não aparecem;
3. Se você trocar o DNS do modem, ele voltará ao da Oi ao ser reiniciado;
4. Estou enfrentando alguns problemas sérios de lentidão. Não sei se isso é relacionado ao modem ou a algum dispositivo na minha rede interna.
-----
Os modens da marca Sagemcom estão se tornando muito populares no Brasil, não, quiçá, por sua qualidade, mas porque eles são os atuais queridinhos das operadoras: quando você assina um plano ADSL, geralmente a operadora envia um modem wireless para sua casa a fim de que você possa navegar sem precisar ter gastos extras com esse equipamento. É claro que os equipamentos fornecidos pelas operadoras são básicos, mas saciam as necessidades dos usuários comuns - …

O Guia Definitivo das configurações avançadas no Sagemcom F@st 2704N

Há alguns meses, eu contei minha experiência com o Sagemcom F@st 2704N e tenho recebido diversos comentários sobre suas configurações avançadas. Agora que minhas aulas na faculdade estão acabando, resolvi reservar um tempinho para explorar melhor esse modem que, diga-se de passagem, é muito bom.