Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FUNCERN 2025
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg467595
Banca
FUNCERN
Órgão
IF-PE
Ano
2025
Nível
Médio
Cargo
Técnico de Laboratório - Área Tecnologia da Informação
As redes sociais modernas utilizam estruturas de dados baseadas em grafos para modelar as conexões entre usuários. Em um grafo de rede social, cada pessoa é representada por um vértice e cada amizade por uma aresta. Para identificar usuários influentes, os algoritmos frequentemente analisam métricas de centralidade. Imagine que você deseja identificar qual dos seus amigos, em uma plataforma de rede social, é o mais influente, considerando que a influência é medida pelo número direto de conexões (amigos) que cada pessoa possui. Nesse sentido, a métrica mais adequada para obter essa informação consiste em
Aaplicar o algoritmo de busca em profundidade para encontrar o caminho mais longo a partir de cada usuário.
Bcalcular o grau de centralidade de cada vértice que conta o número de arestas conectadas diretamente a cada vértice.
Cutilizar o algoritmo de menor caminho para calcular as menores distâncias entre todos os pares de usuários.
Dimplementar o algoritmo de ordenação topológica para hierarquizar os usuários por ordem de importância.
Eexecutar o algoritmo de detecção de ciclos para identificar grupos fechados de amigos mais ativos.Im
Revelar gabarito e comentário▾
GabaritoB — calcular o grau de centralidade de cada vértice que conta o número de arestas conectadas diretamente a cada vértice.
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Métricas de Centralidade em Grafos
Gabarito: letra B. A influência, conforme definida no enunciado, é medida pelo número direto de conexões (amigos) que cada pessoa possui. Essa é exatamente a definição de grau de centralidade (degree centrality) de um vértice em um grafo, que conta o número de arestas incidentes a ele. Nenhuma outra alternativa atende a essa métrica específica.
Métricas de centralidade em grafos: Grau (degree) (Conta arestas incidentes, Mede conexões diretas, Influência direta (gabarito)); Proximidade (closeness) (Menor caminho até outros, Mede alcance indireto); Intermediação (betweenness) (Pontes entre grupos, Mede controle de fluxo); Autovetor (eigenvector) (Conexões com influentes, Mede influência indireta)
Alternativa A — ❌ Incorreta
A busca em profundidade (DFS) é usada para percorrer grafos, mas encontrar o caminho mais longo a partir de cada usuário não está relacionado ao número de amigos diretos. Além disso, o problema do caminho mais longo em grafos gerais é NP-difícil e não é uma métrica de centralidade típica para influência direta.
Alternativa B — ✅ Correta ⟵ GABARITO
O grau de centralidade de um vértice é o número de arestas que incidem sobre ele. Em uma rede social, cada aresta representa uma amizade, portanto contar as arestas é contar os amigos diretos. Quanto maior o grau, mais conexões diretas o usuário possui, indicando maior influência no sentido pedido. É a métrica mais simples e direta para essa finalidade.
Alternativa C — ❌ Incorreta
O algoritmo de menor caminho (Dijkstra, Bellman-Ford, etc.) calcula as distâncias mínimas entre pares de vértices. Isso mede a proximidade indireta (quão rápido a informação pode chegar), não o número de conexões diretas. Não atende ao critério de "número direto de conexões".
Alternativa D — ❌ Incorreta
A ordenação topológica é aplicada apenas a grafos acíclicos dirigidos (DAGs) e serve para linearizar a ordem de dependências. Redes sociais são geralmente não dirigidas ou têm ciclos (amizade mútua), e a ordenação topológica não tem relação com centralidade de grau.
Alternativa E — ❌ Incorreta
Detecção de ciclos identifica subgrafos fechados (como grupos de amigos que se conhecem mutuamente). Embora possa revelar comunidades coesas, não mede quantas conexões diretas um usuário individual possui. A influência individual não é avaliada por essa métrica.
Dica de estudo: Em teoria dos grafos, entenda bem as diferenças entre as principais métricas de centralidade: grau (degree), proximidade (closeness), intermediação (betweenness) e autovetor (eigenvector). Cada uma reflete um aspecto diferente de "influência" ou "importância" em uma rede. O grau é o mais intuitivo: conta as conexões diretas.