Neste artigo, discutiremos a matriz de adjacência juntamente com sua representação.

Definição da matriz de adjacência

Na teoria dos grafos, uma matriz de adjacência é uma forma densa de descrever a estrutura finita do grafo. É a matriz 2D usada para mapear a associação entre os nós do gráfico.

Se um gráfico tiver n número de vértices, então a matriz de adjacência desse gráfico é n x n , e cada entrada da matriz representa o número de arestas de um vértice a outro.

Uma matriz de adjacência também é chamada de matriz de conexão . Às vezes também é chamado de Matriz de vértices .

Representação da Matriz de Adjacência

Se um grafo não direcionado G consiste em n vértices, então a matriz de adjacência de um grafo é a matriz n x n A = [aij] e definida por -

a _{eu j} = 1 {se existe um caminho de V _eu para V _j }

a _{eu j} = 0 {caso contrário}

Vejamos alguns dos pontos importantes em relação à matriz de adjacência.

• Se existe uma aresta entre o vértice V _eu e V _j , onde i é uma linha e j é uma coluna, então o valor de a _{eu j} = 1.
• Se não houver aresta entre o vértice V _eu e V _j , então o valor de a _{eu j} = 0.
• Se não houver loops próprios no gráfico simples, então a matriz de vértices (ou matriz de adjacência) deverá ter 0s na diagonal.
• Uma matriz de adjacência é simétrica para um gráfico não direcionado. Ele especifica que o valor no i ^º linha e j ^º coluna é igual ao valor em j ^º linha eu ^º
• Se a matriz de adjacência for multiplicada por ela mesma, e se houver um valor diferente de zero presente no i ^º linha e j ^º coluna, então há a rota de V _eu para V _{j ­ ­} com comprimento equivalente a 2. O valor diferente de zero na matriz de adjacência representa que o número de caminhos distintos está presente.

Nota: Em uma matriz de adjacência, 0 representa que não existe associação entre dois nós, enquanto 1 representa que existe uma associação entre dois nós.

Como criar uma matriz de adjacência?

Suponha que haja um gráfico g com n número de vértices, então a matriz de vértices (ou matriz de adjacência) é dada por -

UMA = uma _onze a ₁₂ . . . . . a _1n a _{vinte e um} a ₂₂ . . . . . a _2n . . . . . . . . . a _n1 a _n2 . . . . . a _nn

Onde o um _{eu j} é igual ao número de arestas do vértice i a j. Como mencionado acima, a matriz de adjacência é simétrica para um grafo não direcionado, portanto, para um grafo não direcionado, um _{eu j} = um _ei .

Quando os gráficos são simples e não há pesos nas arestas ou múltiplas arestas, então as entradas da matriz de adjacência serão 0 e 1. Se não houver auto-loops, então as entradas diagonais da matriz de adjacência serão 0.

Agora, vamos ver a matriz de adjacência para um grafo não direcionado e para grafos direcionados.

Matriz de adjacência para um gráfico não direcionado

Em um gráfico não direcionado, as arestas não estão associadas às direções a elas. Em um gráfico não direcionado, se existir uma aresta entre o vértice A e o vértice B, então os vértices podem ser transferidos de A para B, bem como de B para A.

Vamos considerar o gráfico abaixo não direcionado e tentar construir a matriz de adjacência dele.

No gráfico, podemos ver que não há loop próprio, então as entradas diagonais da matriz adjacente serão 0. A matriz de adjacência do gráfico acima será -

Matriz de adjacência para um gráfico direcionado

Em um gráfico direcionado, as arestas formam um par ordenado. As arestas representam um caminho específico de algum vértice A para outro vértice B. O nó A é chamado de nó inicial, enquanto o nó B é chamado de nó terminal.

Vamos considerar o gráfico direcionado abaixo e tentar construir a matriz de adjacência dele.

No gráfico acima, podemos ver que não há loop próprio, então as entradas diagonais da matriz adjacente serão 0. A matriz de adjacência do gráfico acima será -

Propriedades da matriz de adjacência

Algumas das propriedades da matriz de adjacência são listadas a seguir:

• Uma matriz de adjacência é uma matriz que contém linhas e colunas usadas para representar um gráfico simples rotulado com os números 0 e 1 na posição de (V _EU , EM _j ), de acordo com a condição de haver ou não os dois V _{eu ­} e V _j são adjacentes.
• Para um gráfico direcionado, se existir uma aresta entre o vértice i ou V _eu para o vértice j ou V _j , então o valor de A[V _eu ][EM _j ] = 1, caso contrário o valor será 0.
• Para um gráfico não direcionado, se existir uma aresta entre o vértice i ou V _eu para o vértice j ou V _j , então o valor de A[V _eu ][EM _j ] = 1 e A[V _j ][EM _eu ] = 1, caso contrário o valor será 0.

Vejamos algumas questões da matriz de adjacência. As perguntas abaixo estão nos gráficos direcionados e não direcionados ponderados.

NOTA: Um gráfico é considerado ponderado se cada aresta receber um número positivo, que é chamado de peso da aresta.

Questão 1 - Qual será a matriz de adjacência para o gráfico ponderado não direcionado abaixo?

Solução - Na questão dada, não há auto-loop, então é claro que as entradas diagonais da matriz adjacente para o gráfico acima serão 0. O gráfico acima é um gráfico não direcionado ponderado. Os pesos nas arestas do gráfico serão representados como as entradas da matriz de adjacência.

A matriz de adjacência do gráfico acima será -

Questão 2 - Qual será a matriz de adjacência para o gráfico ponderado direcionado abaixo?

Solução - Na questão dada, não há auto-loop, então é claro que as entradas diagonais da matriz adjacente para o gráfico acima serão 0. O gráfico acima é um gráfico direcionado ponderado. Os pesos nas arestas do gráfico serão representados como as entradas da matriz de adjacência.

A matriz de adjacência do gráfico acima será -

Espero que este artigo seja benéfico para você entender sobre a matriz de adjacência. Aqui, discutimos a matriz de adjacência juntamente com sua criação e propriedades. Também discutimos a formação de matrizes de adjacência em grafos direcionados ou não direcionados, sejam eles ponderados ou não.