Grafos e matrizes: contando passeios

Grafos e matrizes

A matriz de adjacência A de um grafo tem um 1 na posição (u, v) quando existe aresta de u para v, e 0 caso contrário. Essa matriz é um jeito de guardar o grafo, mas ela também faz contas com significado.

Passeios por potências

Um passeio de comprimento k é uma sequência de k arestas em que cada uma começa onde a anterior terminou; ao contrário de um caminho, pode repetir vértices. A entrada (u, v) de A^k é o número de passeios de comprimento k de u até v.

A razão está na multiplicação de matrizes: (A²)(u, v) soma, sobre todos os intermediários w, os produtos A(u, w)·A(w, v), ou seja, conta os passeios u → w → v. Em geral, (A^k)(u, v) conta passeios com k passos.

Na aula, a tabela de A^k mostra essas contagens. O traço de A^k (soma da diagonal) conta os passeios fechados de comprimento k.

Autovalores

Para um grafo não dirigido, a matriz A é simétrica e tem n autovalores reais. Eles resumem a estrutura do grafo:

• A soma dos autovalores é o traço de A, que é 0 num grafo sem laços.
• A soma dos quadrados dos autovalores é 2m, o dobro do número de arestas.
• O maior autovalor de um grafo conexo está entre o grau mínimo e o grau máximo, e é igual ao grau médio num grafo regular.

No grafo completo K_n, os autovalores são n − 1 e −1 (repetido n − 1 vezes). No grafo de Petersen, são 3, 1 (cinco vezes) e −2 (quatro vezes).

Laços e a diagonal

Na matriz de adjacência, um laço soma 1 na diagonal, e assim conta uma vez quando o passeio o percorre. Por isso o grau de um vértice (que conta o laço duas vezes) pode ser diferente da soma da linha correspondente da matriz. A aula não usa laços, mas o editor do grafo deixa criá-los para explorar essa diferença.