Alternativa C - Matriz de adjacências
Introdução à Representação Matricial de Grafos
Em Teoria dos Grafos, representar um grafo utilizando matrizes é uma técnica fundamental para algoritmos computacionais, permitindo operações eficientes de busca e manipulação de dados. Existem diferentes tipos de matrizes, mas uma se destaca como a principal e mais utilizada para descrever a estrutura de conexões direta.
Desenvolvimento
A Matriz de Adjacências (ou Matriz de Ligação) é a representação padrão para grafos. Ela é uma matriz quadrada de dimensão n \times n, onde n é o número de vértices do grafo.
- As linhas e colunas representam os vértices do grafo.
- O valor na interseção (i, j) indica se existe uma aresta saindo do vértice i e chegando no vértice j.
Para um grafo simples não ponderado:
A_{ij} =
\begin{cases}
1 & \text{se existe aresta entre } i \text{ e } j \\
0 & \text{caso contrário}
\end{cases}
Análise das Alternativas
- Alternativa A (Orientação): Não é o termo técnico padrão para a estrutura de representação de grafos.
- Alternativa B (Conectividade): Embora exista uma "matriz de conectividade" (que mostra se há caminho entre vértices), ela é geralmente derivada da matriz de adjacências e não é a estrutura primária de representação.
- Alternativa C (Adjacências): Correta. É a definição clássica de representação matricial de grafos.
- Alternativa D (Interação): Termo genérico, não utilizado formalmente neste contexto.
- Alternativa E (Cardinalidade): Refere-se ao tamanho ou quantidade de elementos, não à topologia do grafo.
Conclusão
A estrutura mais comum e essencial para representar grafos via matrizes é a Matriz de Adjacências, pois ela codifica diretamente as relações de vizinhança entre os nós.