Membros

segunda-feira

Grafos e Matrizes de Adjacência (Parte 1)

O propósito deste post é apresentar os grafos e mostrar como a potência de matrizes pode ser usada na investigação de tais entes matemáticos. Daremos ênfase nas rotas aéreas como exemplos de grafos.

Definição 1: Um grafo é um conjunto de pontos (chamados vértices) e um conjunto de linhas chamados lados que conectam alguns pares de vértices. Dois vértices conectados por um lado são ditos adjacentes. 

Considere o grafo na figura 1 abaixo. 
Fig. 1
Note que dois vértices podem ser conectados por mais de um lado (A e B são conectados por 2 lados distintos), que um vértice não precisa estar conectado a nenhum outro vértice, por exemplo o vértice D e que um vértice pode ser conectado a ele mesmo, que é o caso do vértice F. Outro exemplo de grafo é o mapa gerado pelas rota aéreas em uma região americana conforme a figura abaixo:
Fig. 2
As iniciais acima representam as seguintes cidades:
B = Boston
H = Hyannis
M = Martha`s Vineyard
Na = Nantucket 
Ne = New Bedford
P = Providence
Pr = Provincetown

Na figura 2, os vértices são as cidades e dois vértices são conectados se existe um vôo entre direto entre eles. Algumas perguntas naturais surgem a respeito dos grafos. Pode ser importante saber se dois vértices são conectados por uma sequência de dois lados, mesmo que eles não sejam ligados diretamente por um lado.  

Na figura 1, [;A;] e [;C;] são conectados por uma sequência de dois lados (na verdade, existem quatro formas distintas para ir de A para C em duas etapas) conforme a figura 4 abaixo. 
Fig. 4
No mapa das rotas aéreas na Fig. 2, Provincetown e Hyannis estão conectados por uma sequência de dois lados (Pr-B-H) e (Pr-B-Na-H). Outras perguntas interessantes são: 
[;i);] É possível ir de um vértice para outro vértice?
[;ii);] Sendo possível, qual o número mínimo de passos a serem dados de um vértice a qualquer outro vértice do grafo?

Enquanto essas perguntas são relativamente fáceis de responder para um grafo de pequeno porte, o mesmo não ocorre quando o número de vértices e lados aumentam de forma significativa. As matrizes e o uso de computadores podem nos auxiliar a responder estas perguntas. 

Definição 2: A matriz de adjacência de um grafo com [;n;] vértices é uma matriz quadrada de ordem [;n;] cuja entrada [;(i,j);] é igual a [;1;] se o i-ésimo vértice e o j-ésimo vértice estão conectados e [;0;] caso contrário. 
Na figura 1, [;A;] é o vértice [;1;], [;B;] é o vértice [;2;], etc... de modo que a matriz de adjacência para este grafo é 
 Se os vértices no mapa das rotas aéreas correspondem as cidades: Boston, Hyannis, Martha`s Vineyard, Nantucked, New Bedford, Providence e Provincetown, então a matriz de adjacência é dada por
 Matrizes de adjacência podem ser usadas para responder as seguintes perguntas: 
[;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?

Responderemos estas questão na segunda e última parte desta série.

Gostará de ler também:
- Matrizes (Parte 1);
-

7 comentários:

  1. Excelente exposição. Remonta a Euler o surgimento dos grafos, no clássico problema das pontes de Königsberg. Minha pergunta é: Euler utilizou a representação da matriz de adjacência no problema?

    Att!

    ResponderExcluir
  2. Oi, Paulo!

    Eu não sabia desta aplicação das matrizes. É muito interessante. O exemplo prático da rota dos aviões indica que é uma teoria muito importante.

    Qual foi o soft que utilizou para desenhar as figuras?

    Até mais!

    ResponderExcluir
    Respostas
    1. Olá Aloisio, irei apresentar a segunda parte deste post usando matrizes. Este assunto também é novo para mim e estou aprendendo. Como eu fiz este post a algum tempo, fiz as figuras no Paint mesmo, mas agora estou dando os primeiros passos no Geogebra e lá as figuras ficam melhor. Obrigado pelo comentário.

      Excluir
  3. Isso é matemática com base conceitual em conexão de campos nucleares, fatalmente é usado em engenharia reversa.
    Utílíssimo post. Grato por comunicar.
    Estou estudando uma queatão avançada sobre o "quadrado" na Gravidade.
    Qualquer dia a gente se fala sobre isso.
    Gostaria que visitasse, quando puder, o site Gleam(er)(s) Team.
    Vou indicá-lo sempre que possível a pesquisadores que conheço.
    Tens o sucesso em ti.

    Até.

    ResponderExcluir
    Respostas
    1. Obrigado pelos elogios e indicação do blog. Sucesso em suas pesquisas.

      Excluir
  4. Excelente blog! Me demorarei ao explorá-lo.

    Gostaria de apresentar, também, um blog que consta curiosidades matemáticas em uma linguagem acessível e democrática.

    matematicanorecreio.blogspot.com.br

    ResponderExcluir
    Respostas
    1. Bonito layout do seu blog. Muito bom de visualizá-lo. Se não faz ainda da UBM recomendo que filie-se e tenha o seu blog em maior destaque na rede. Obrigado pelo comentário e volte sempre.

      Excluir