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...

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 ...

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.

Considere o grafo direcionado  abaixo , representado por sua lista de adjacência: Grafo G: a → b, d b → e c → f d → e → g f → f g → d Sabendo que: O algoritmo  DFS  é executado com os vértices em ordem  alfabética  (a, b, c, d, e, f, g), O grafo é  direcionado , Não há arestas paralelas nem pesos, O algoritmo DFS registra os  tempos de descoberta ( d ) e finalização ( f ) , Com base nesses tempos, é possível classificar as arestas em:  tree ,  forward ,  backward  e  cross , Após a execução completa do  DFS , qual das seguintes afirmações é  falsa ? A) A aresta  f → f  é uma aresta  backward , indicando a presença de um  ciclo . B) A aresta  g → d  é classificada como uma  forward edge . C) A árvore de recursão de DFS terá  duas árvores  distintas (floresta), uma começando por  a  e outra por  c . D) A aresta  c → e  será classificada ...