ICUnicamp.blogspot.com

Hoje mergulhei em um dos temas mais fascinantes da Teoria dos Grafos: fluxo em redes . Mais do que uma abstração matemática, esse conceito aparece em situações muito concretas — da logística de caminhões até a coordenação militar da OTAN O que é uma Rede de Fluxo? Podemos imaginar uma rede de fluxo como um sistema de canos de água ou de caminhões em estradas : Existe uma fonte (source) que gera o recurso. Um sorvedouro (sink) onde esse recurso precisa chegar. E arestas com capacidades que limitam quanto pode ser transportado por cada conexão. Três propriedades fundamentais governam esse sistema: Conservação : tudo o que entra em um nó intermediário precisa sair (não há estoque local). Antissimetria : o fluxo de ida e volta se cancelam (se A envia 4 para B, então B envia –4 para A). Valor do fluxo : corresponde ao total que sai da fonte (ou entra no sorvedouro). Rede Residual: onde a mágica acontece Quando já usei parte de uma estrada, sempre sobra a possibi...

NATO Logistics Flow — Quiz Question NATO is coordinating the shipment of military supplies to reinforce its eastern flank. Units are produced in the United States and Germany , entering Europe through the ports of Rotterdam and Naples . From there, they move to the logistics hubs of Rotterdam and the Czech Republic , with final delivery to three defense lines: Baltic States (demand 50) , Eastern Poland (demand 60) , and Romania (demand 40) . Capacities (in units/week): US → Rotterdam : 15 US → Naples : 15 Germany → Rotterdam : 15 Germany → Czech Republic : 15 Rotterdam → Baltics : 20 Rotterdam → Eastern Poland : 15 Czech Republic → Eastern Poland : 15 Czech Republic → Romania : 15 Naples → Romania : 10 Based on the maximum flow model in directed graphs : What is the maximum supply that can reach Romania ? Why can Eastern Poland not receive more than 30 units, even if production is sufficient at the sources? If the Baltic States demand 50 but can o...

No grafo de emendas parlamentares, você encontra que apenas 10% dos vértices estão em SCCs com mais de 3 nós, e os outros 90% estão em SCCs unitários. Analise as afirmações: A rede apresenta alta reciprocidade estrutural, já que a maioria dos nós pertence a SCCs. O fato de existirem muitos SCCs unitários indica baixa reciprocidade estrutural. Apenas olhar o grau de entrada e saída dos nós seria suficiente para explicar essa distribuição de SCCs. Emendas que formam SCCs maiores podem indicar blocos fechados de influência política. Qual alternativa está correta? A) Apenas 1 e 2 são verdadeiras. B) Apenas 2 e 4 são verdadeiras.  C) Apenas 1, 3 e 4 são verdadeiras. D) Apenas 2, 3 e 4 são verdadeiras. E) Nenhuma das anteriores.

Hoje avancei no estudo de componentes fortemente conexas (SCCs), um conceito central em grafos dirigidos. Pode soar técnico, mas vou explicar de um jeito simples: um SCC é como um grupo de nós que conseguem se alcançar mutuamente, respeitando as direções das arestas. Dentro de um SCC, você sempre consegue ir “de A até B e de B até A”. Grau de Entrada e Saída: o primeiro passo Antes de falar em SCC, precisei entender duas medidas básicas: Grau de entrada (in-degree): quantas arestas chegam a um nó. É como contar quantas pessoas me seguem no Twitter. Grau de saída (out-degree): quantas arestas saem de um nó. É como contar quantas pessoas eu sigo. Essas medidas dão uma visão local da rede — mostram popularidade e atividade de cada nó, mas não revelam o que acontece quando seguimos os caminhos mais longos. Reciprocidade Estrutural: o próximo nível É aqui que entra o poder dos SCCs. Diferente do grau, que olha só a vizinhança imediata, a reciprocidade estrutural considera se existe um camin...

Nos últimos dias tenho mergulhado no Capítulo 3 do Network Science Book , e cada seção tem aberto novas formas de entender como as redes funcionam. Ontem registrei minhas descobertas sobre distribuições de grau, limiares críticos e o momento em que uma rede “ganha vida”. Hoje, avancei para três conceitos fascinantes: 1. O fenômeno do Small World A ideia central é simples: a distância média entre dois nós em uma rede aleatória cresce de forma logarítmica com o tamanho da rede. Em uma rede com grau médio ⟨k⟩, o número de vizinhos acessíveis cresce exponencialmente : Distância 1 → ⟨k⟩ vizinhos Distância 2 → ⟨k⟩² vizinhos Distância 3 → ⟨k⟩³ vizinhos Isso explica porque, mesmo em redes gigantes, conseguimos atravessar de um nó a outro em poucos passos — o famoso “seis graus de separação”. Surpresa: Nossa intuição vem de redes regulares ( lattices ), onde as distâncias crescem polinomialmente: N 1 / d N^{1/d} Em 1D, d m a x ∼ N d_{max} \sim N . Em 2D, d m a x ∼ ...

Depois de mergulhar no exemplo da festa do vinho — e na diferença entre fofoca em redes sociais reais e o modelo de Erdős–Rényi — avancei para outra parte fundamental: a matemática por trás da conectividade em redes aleatórias . Do número de links ao grau médio Em um grafo com N N nós, o número máximo de pares possíveis é: M = N ( N − 1 ) 2 M = \frac{N(N-1)}{2}. O número de links L L segue uma distribuição binomial: P ( L ) = ( M L ) p L ( 1 − p ) M − L P(L) = \binom{M}{L} p^L (1-p)^{M-L}. O valor esperado é: ⟨ L ⟩ = M p \langle L \rangle = M \cdot p. Como cada link conecta dois nós, o grau médio é: ⟨ k ⟩ = 2 ⟨ L ⟩ N = p ( N − 1 ) \langle k \rangle = \frac{2\langle L \rangle}{N} = p (N-1). Minha  intuição : cada nó tem N − 1 N-1 chances de se conectar, cada uma com probabilidade p p . O limiar crítico: ⟨ k ⟩ = 1 \langle k \rangle = 1 Esse foi o ponto mais marcante do meu aprendizado: Se ⟨ k ⟩ < 1 \langle k \rangle < 1 : a rede é formada por pequenos fragmen...

Nos últimos dias, fiquei com uma dúvida interessante ao ler um exemplo do livro de redes: a história da festa em que alguém descobre qual é o melhor vinho e essa informação acaba se espalhando entre os convidados. A minha primeira interpretação foi: “ah, claro, isso mostra como a fofoca se espalha rápido”. Mas, na aula, o professor me corrigiu — e aí começou meu aprendizado. O que eu entendi depois? O texto, na verdade, está descrevendo o modelo de redes aleatórias (Erdős–Rényi). Nesse modelo: As conexões entre as pessoas surgem ao acaso. A propagação da informação só decola quando a rede atinge um limiar crítico de conectividade . Nesse ponto, aparece a chamada componente gigante — e qualquer informação consegue se espalhar para quase todos. Esse é o momento em que a rede “ganha vida” : de repente, ela deixa de ser um conjunto de pares isolados e passa a funcionar como um todo conectado. As redes aleatórias são a base, mas na realidade não descrevem as redes sociais humanas. Isso por...