TechCodeview

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

o que é hibernar

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_eupara V_j}

a_{eu j}= 0 {caso contrário}

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

linguagem de computador bacana

• Se existe uma aresta entre o vértice V_eue 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_eue 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_eupara 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_onzea₁₂. . . . . a_1na_{vinte e um}a₂₂. . . . . a_2n. . . . . . . . . a_n1a_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_jsão adjacentes.
• Para um gráfico direcionado, se existir uma aresta entre o vértice i ou V_eupara 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_eupara 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.

reinicie o mysql ubuntu

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.

java concatenar strings

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.