English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGrafos e RedesGráficos na vida cotidiana
Ao longo deste curso, vimos muitas aplicações da teoria dos grafos, embora algumas tenham sido de alguma forma artificial. Acontece, no entanto, que os gráficos estão no centro de muitos objetos e conceitos na vida cotidiana.
A internet, por exemplo, é um vasto gráfico virtual. Todo vértice é uma página da web individual e cada borda significa que há um hiperlink entre duas páginas. Observe que os links são apenas de uma maneira; portanto, este gráfico é
Alguns sites, como Wikipedia ou Facebook, têm muitos links de entrada, enquanto muitos sites menores podem ter muito poucos links de entrada. Esse é o conceito subjacente usado pelo Google para classificar os resultados da pesquisa.
Sites com mais links recebidos tendem a ser de qualidade superior e devem ser mostrados na parte superior dos resultados da pesquisa. Por exemplo, ao pesquisar "Londres", sites oficiais de informações turísticas são mostrados antes de pequenas lojas em Londres ou blogs de pessoas que moram em Londres. Essa idéia simples da teoria dos grafos, o algoritmo de Page Rank, tornou o Google significativamente melhor do que outros mecanismos de busca antigos.
A internet é a maior rede já criada pela humanidade. Esta imagem mostra uma proporção muito pequena de todos os servidores conectados à Internet:
Enquanto sites e hiperlinks formam um gráfico virtual, também existe a rede física de computadores, servidores, roteadores, linhas telefônicas e cabos.
Toda vez que você faz uma ligação telefônica ou carrega um site, as operadoras de rede precisam encontrar uma maneira de conectar remetente e receptor, sem exceder a capacidade de qualquer cabo ou conexão individual. A teoria e a probabilidade dos grafos possibilitam garantir um serviço confiável, por exemplo, encontrando desvios quando uma conexão específica está ocupada.
Os gráficos também desempenham um papel importante no transporte e na navegação. Todas as redes de vôo, trem e metrô formam gráficos, que podem ser usados ao criar horários eficientes. Um dos gráficos mais reconhecíveis é o mapa do metrô de Londres:
Todas as estradas e rodovias também formam uma grande rede, usada por serviços de navegação como o Google Maps ao elaborar a rota mais curta entre dois pontos.
No futuro, os Sistemas Inteligentes de Transporte reduzirão o congestionamento e os acidentes encaminhando carros com mais eficiência, usando dados de localização coletados de smartphones e carros autônomos. Isso pode economizar milhões de horas perdidas na estrada todos os anos, reduzir significativamente a poluição e permitir que os serviços de emergência viajem mais rapidamente.
Esta imagem mostra a rede de voos de companhias aéreas comerciais no norte da Europa.
Existem inúmeros outros gráficos na ciência, engenharia ou na vida cotidiana:
As ligações entre átomos em moléculas e grades de cristal formam um gráfico.
A propagação de doenças e epidemias podem ser modeladas usando uma rede.
Na biologia, as árvores evolutivas que mostram a ascendência das espécies formam um gráfico.
Os diferentes componentes de circuitos elétricos e chips de computador formam uma rede.
A estrutura gramatical de idiomas pode ser modelada usando gráficos, por exemplo, para criar algoritmos de tradução.
Os gráficos também têm muitas aplicações em probabilidade, teoria dos jogos e matemática financeira.
Redes sociais
Finalmente, vamos pensar em um exemplo particularmente bom de gráficos que existem na vida cotidiana: as mídias sociais. Aqui, os vértices representam
Quando começamos a desenhar gráficos de mídia social, podemos ver claramente alguns grupos de amigos em comum, que podem ter frequentado a mesma escola ou morado na mesma cidade. Também podemos determinar a centralidade das pessoas, que depende de quão bem conectado um vértice está e que pode ser uma medida da popularidade de uma pessoa nas mídias sociais.
Em 2014, o Facebook tinha 1,4 bilhão de usuários ativos e um total de mais de 200 bilhões de amizades. Metade de todos os usuários do Facebook tem mais de 200 amigos e, como a maioria de nossos amigos tem um número semelhante de amigos, poderíamos facilmente ter dezenas de milhares de amigos de amigos.
Uma pergunta interessante agora seria: se você escolher dois usuários aleatórios do Facebook, quantas “arestas de amizade” você precisaria seguir para passar de um para o outro? Por exemplo, a distância entre amigos é
Com base em um estudo realizado pelo Facebook em 2016, você está, em média, conectado a qualquer outra pessoa no Facebook por mais de 3,57 pessoas: dizemos que existem 3,57 graus de separação.
Em outras palavras, se você escolher qualquer um dos bilhões de usuários do Facebook em todo o mundo, eles terão um amigo de um amigo que conhece um amigo de um de seus amigos. E isso inclui celebridades, políticos ou realeza ...
Geographic visualisation of all Facebook friendships in 2010.
Em 1929, quando o autor húngaro
Em 1967,
Hoje, cada um de nós faz parte de inúmeros gráficos invisíveis, subjacentes às nossas interações sociais, viagens, Internet e tecnologia, ciência e muito mais.