Membros

quinta-feira

Grafos e Matrizes de Adjacência (Parte 2)

Neste post, responderemos as duas perguntas que foram apresentadas na parte 1 o qual reproduzimos abaixo:

[;i);] Quais os vértices que estão conectados por uma sequência de dois lados?
[;ii);] Quantas sequências distintas de dois lados conectam cada par de vértices?

Considere a figura acima. Os vértices [;B;] e [;F;] estão conectados por duas sequências de dois lados ([;BCF;] ou [;BEF;]). Note que os dois lados entre [;B;] e [;C;] são indistinguíves.

Seja [;m_{ij};] a [;(i,j);] entrada na matriz de adjacência [;M;]. Note que

[;m_{21}m_{16} + m_{22}m_{26} +m_{23}m_{36} + m_{24}m_{46} + m_{25}m_{56} + m_{26}m_{66} =;]
[; = 1\cdot 0 + 0\cdot 0 + 1\cdot 1 + 0\cdot 0 + 1\cdot 1 + 0\cdot 1 = 2;]
o qual é o número de sequências de dois lados entre [;B;] e [;F;]. Note que, desde que [;B;] conecta com [;C;] e [;C;] com [;F;], [;m_{23}m_{36} = 1;]; desde que [;B;] conecta com [;A;] e [;A;] não conecta com [;F;], [;B;] não conecta com [;F;] através de [;A;] com uma sequência de dois lados, por isso, [;m_{21}m_{16} = 0;]. Somando todos os pontos intermediários temos o resultado. 

Agora note que 
[;\sum_{k=1}^{6}m_{2k}m_{k6};]
é a entrada [;(2,6);] da matriz [;M^2;].

Observação 1: O número de sequências de dois lados entre o vértice [;i;] e o vértice [;j;] em um grafo com matriz adjacência [;M;] é a entrada [;(i,j);] na matriz [;M^k;]. Se [;M;] é a matriz adjacência para a figura acima, então
e
Portanto, existe uma sequência de dois passos (lados) de [;C;] a [;F;], e existem [;5;] sequências de [;3;] passos entre [;C;] e [;F;]. Observando a figura abaixo, 


As iniciais acima representam as seguintes cidades:
B = Boston
H = Hyannis
M = Martha`s Vineyard
Na = Nantucket 
Ne = New Bedford
P = Providence
Pr = Provincetown

vemos que Nantucket é conectada em duas etapas a partir de Boston (via Hyannis ou Martha's Vineyard), mas observe que existe um vôo direto entre as duas cidades. Assim, temos a seguinte pergunta:

Qual é o menor número de arestas (lados) que devem ser percorridos para ir de um vértice [;A;] para um vértice [;B;]? 

Para responder esta questão, considere a matriz 
[;S_k = M + M^2 + \ldots + M^k;]

A [;(i,j);] entrada nesta matriz fornece o número de maneiras de interligar o vértice [;i;] ao vértice [;j;] em [;k;] passos ou menos. Se tal viagem é impossível, esta entrada será zero. Portanto, para encontrar o menor número de passos entre os vértices continue calculando [;S_k;] à medida que aumenta [;k;], o primeiro [;k;] para o qual a entrada [;(i,j);] em [;S_k;] é diferente de zero é o menor número de passos entre [;i;] e [;j;]. 

Outra questão referente a um grafo é se é possível ir de um vértice a qualquer outro. Se um grafo possui a propriedade de que cada vértice está ligado a todos os outros em um determinado número de passos dizemos que ele está conectado.

Como podemos determinar se um grafo está conectado?

Isso é fácil de ver se o grafo é pequeno. Mas é mais difícil de ver a partir da matriz de adjacência. No entanto, existe um cálculo que pode ser feito. 

Suponha que o grafo possui [;n;] vértices. Então o maior número de passos que poderia tomar para ir de um vértice para qualquer outro é [;n;] passos. Assim, 

[;S_n = \sum_{k=1}^{n}M^k;]


pode nos ajudar. Se houver qualquer zero nesta matriz será impossível conectar um par de vértices e portanto, o grafo não está conectado.

Gostará de ler também:
- Grafos e Matrizes de Adjacência (Parte 1);
- Matrizes (Parte 1);

2 comentários:

  1. GENIAL! Adoro o assunto de grafos e fiquei fascinado com esse post. Poderia indicar onde posso encontrar mais conteúdo sobre grafos?
    Parabéns professor.

    ResponderExcluir
    Respostas
    1. Não conheço nenhum material em português. Este post foi baseado em um artigo em inglês que eu já joguei fora. Parece que o IMPA tem um livro sobre este assunto. Obrigado pelo assunto e volte sempre!

      Excluir