ICUnicamp.blogspot.com

Introdução  O nosso projeto busca analisar os dados de emendas parlamentares a partir da teoria de grafos. A ideia é transformar uma tabela aparentemente burocrática, com informações sobre autores das emendas, funções orçamentárias e localidades, em redes que revelem padrões de relação, influência e concentração de recursos . O objetivo é compreender como parlamentares direcionam suas emendas, em quais áreas (funções) estão mais presentes e para quais localidades os recursos se destinam. A teoria de grafos oferece as ferramentas para representar essas conexões e, a partir daí, aplicar métricas de análise de redes. Primeira reunião – A recomendação Na nossa primeira reunião com o professor, ele recomendou que o primeiro passo fosse instanciar a rede em três grafos diferentes, cada um com um foco distinto: Autor → Função Autor → Localidade Função → Localidade Essa orientação foi fundamental porque mostrou, na prática, que não existe um único grafo “correto”: a forma como escolhemos i...

Neste espaço registro as minhas perguntas e descobertas em Algoritmos em Grafos. A cada semana, vou trazer aqui as questões que surgiram nas aulas e nas minhas sessões de estudo, minhas tentativas de respostas e os exemplos que me ajudaram a clarear a ideia ou conceito. Foi uma demanda do professor e entendi que é uma maneira de transformar dúvidas em aprendizado compartilhado!

Depois de entender o BFS, que explora primeiro os vizinhos mais próximos, estudei o DFS (Depth-First Search). No começo, parecia apenas “o oposto do BFS”, mas encontrei a analogia dos parentes e conhecidos me ajudou muito a fixar a lógica. O BFS é como se você quisesse conhecer todos os vizinhos do seu bairro. Você começa pela sua casa (o nó inicial). Depois visita todas as casas da mesma rua, depois passa pra rua seguinte, e assim por diante. É um percurso em camadas: você esgota primeiro quem está perto, depois expande para os que estão mais longe. DFS é como visitar parentes distantes em profundidade: Você começa pela sua casa (o nó inicial). Em vez de visitar todos os vizinhos primeiro, você escolhe um caminho e segue até o fim (como visitar uma tia distante, depois a prima dessa tia, depois a amiga da prima…). Só quando não há mais ninguém para visitar naquele ramo, você volta e segue para outro caminho. Enquanto o BFS é como conhecer todos os vizinhos do seu bairro antes de sair,...

Estudar os conceitos de coeficiente de clustering e cauda longa me ajudou a entender porque algumas redes são tão desiguais, mas também muito eficientes em espalhar informação. O clustering mede o quanto os vizinhos de um nó também estão conectados entre si, algo muito comum em redes sociais (meus amigos também são amigos entre si). Já a cauda longa aparece em distribuições de grau: poucos nós têm muitas conexões, e muitos nós têm poucas conexões. Me dei conta de que é o que vemos, por exemplo, em sites da internet ou influenciadores em redes sociais. E fiquei com a pergunta de c omo o coeficiente de clustering pode influenciar a rapidez com que uma informação se espalha em uma rede social?

Nos meus estudos sobre representação de grafos, aprendi que existem três formas principais: matriz de adjacência, lista de adjacência e matriz de incidência. No começo fiquei em dúvida sobre quando usar cada uma. A matriz de adjacência é uma tabela em que as linhas e colunas representam os nós. Se o grafo for não direcionado, a matriz é simétrica (ex.: se A está ligado a B, então B também está ligado a A). Se o grafo for direcionado, a matriz não é necessariamente simétrica: a posição [A,B] pode ter valor (aresta de A para B), mas [B,A] pode estar vazia (não existe volta). Isso mostra claramente a direção das conexões. A lista de adjacência é mais eficiente para grafos grandes, pois lista apenas os vizinhos que realmente existem para cada nó. A matriz de incidência relaciona nós e arestas, sendo útil em análises mais específicas, como problemas de fluxo. Pergunta: Qual dessas representações seria mais adequada para um grafo muito grande, com milhões de nós, mas poucas conexões entre el...

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