ICUnicamp.blogspot.com

Questão 5 — When 1.5 Beats 2: The Strength of Christofides under the Triangle Inequality Consider a symmetric, weighted, complete graph \( G = (V, E) \) with \( |V| = 6 \) vertices that satisfies the triangle inequality. The minimum spanning tree (MST) of \( G \) has total cost \( c(T) = 60 \). Two algorithms are applied to this graph: Rosenkrantz–Stearns–Lewis (RSL) Finds \( T=\mathrm{mst}(G) \); doubles each edge of \(T\) to get an Eulerian multigraph \(T'\); finds an Euler tour and removes repeated vertices. Performance guarantee: \( c(C_{\mathrm{RSL}}) \le 2\,c(TSP^*) \). Christofides Finds \( T=\mathrm{mst}(G) \); lets \( S \) be the set of odd-degree vertices of \(T\); finds a minimum perfect matching \( M \) on \(S\); adds \(M\) to \(T\) to get an Eulerian multigraph \(T'\); finds an Euler tour and removes repeated vertices. Performance guarantee: \( c(C_{\mathrm{Chr}}) \le 1.5\,c(TSP^*) \). Answer in one go: (i) the maximum tot...

Em teoria dos grafos, o algoritmo do Caixeiro Viajante (TSP) é um clássico: dado um conjunto de cidades e as distâncias entre elas, o desafio é encontrar o caminho mais curto que visita cada cidade exatamente uma vez e retorna ao ponto de partida. Mas, além de seu fascínio matemático, o TSP é uma metáfora poderosa para problemas reais de decisão, inclusive em política. Enquanto estudava o algoritmo, percebi o quanto ele se conecta ao meu projeto de rede de Emendas Parlamentares . Cada deputado pode ser visto como um “viajante” que precisa distribuir suas emendas (recursos) entre diversos municípios, tentando equilibrar  alinhamento político e retorno eleitoral . Na prática, isso cria um problema de otimização multidimensional: como percorrer os “nós” (municípios) maximizando o impacto político com o menor custo possível? Modelar esse comportamento em grafos permite testar hipóteses como: Deputados priorizam municípios geograficamente próximos? Há padrões regionais que...

When Identical Degree Distributions Hide Distinct Correlation Patterns “Two networks may share the same degree distribution and yet encode profoundly different organizational principles.”   Context Consider two undirected networks, A and B , each with the same degree distribution $P(k)$ and identical average degree $\langle k \rangle = 6.2$. Despite this structural similarity, empirical analysis shows that the average neighbor degree function $k_{nn}(k)$ behaves differently for each network: For Network A , $k_{nn}(k)$ increases approximately as a power law $k_{nn}(k) \sim a,k^{\mu}$ with $\mu > 0$. For Network B , $k_{nn}(k)$ decreases with $k$, following $k_{nn}(k) \sim a,k^{\mu}$ with $\mu < 0$. Definition The Pearson correlation coefficient of degree correlation r r r is defined as: r = ∑ j , k j k   ( e j k − q j q k ) σ 2 r = \frac{\sum_{j,k} j k \,\big(e_{jk} - q_j q_k\big)}{\sigma^2} r = σ 2 ∑ j , k ​ jk ( e jk ​ − q j ​ q k ​ ) ​ where: ejk e_{jk} e ...

Entendendo a Correlação de Grau em Redes: quem se conecta com quem? Você já parou para pensar se os “nós populares” de uma rede tendem a se conectar entre si — ou se preferem fazer amizade com nós menores, menos conectados? Essa simples pergunta leva a um dos conceitos mais elegantes da Ciência de Redes : a correlação de grau  e o coeficiente de assortatividade . O que é o grau de um nó? O grau  de um nó é o número de conexões que ele possui. Em redes não direcionadas , é apenas o número de vizinhos. Já em redes direcionadas , distinguimos: grau de entrada (in-degree) : quantas conexões chegam; grau de saída (out-degree) : quantas conexões saem. Esse número simples — o grau — é a base de muitas propriedades emergentes das redes complexas. Correlação de grau: quando a afinidade cria estrutura A correlação de grau  mede o quanto o grau de um nó influencia o grau dos nós com que ele se conecta. Em termos simples: quem se conecta com quem: Quando nós de alto grau se conectam ...