Teoria dos Grafos e Matrizes

Prévia do material em texto

INTRODUÇÃO A TEORIA DOS GRAFOSINTRODUÇÃO A TEORIA DOS GRAFOS
TEORIA DOS GRAFOS E AS MATRIZESTEORIA DOS GRAFOS E AS MATRIZES
Autor: Me. Sergio Eduardo Nunes
Revisor : Emerson dos Santos Paduan
IN IC IAR
Processing math: 100%
introdução
Introdução
A teoria dos grafos é uma ferramenta matemática que possibilita diversas formas de representar a
organização dos dados, por meio de um conjunto de vértices e arestas. Isso possibilita a utilização
de conjuntos numéricos dispostos em formato de matriz, assim, agrupando dados e gerando formas
de representações de grafos. Essa técnica é muito útil, pois possibilita análises em agrupamentos de
valores extraídos de determinadas aferições, que possibilita, por meio da representação, auxiliar na
busca de resultados de problemas encontrados no dia a dia.
Para tal, é necessário que se tenha a compreensão das características encontrada nas matrizes.
Contudo, ainda é possível efetuar operações com os vetores, que possibilita adicionar, remover e
fazer demais operações, a �m de manipular as interações em vértices e arestas.
Os conhecimentos adquiridos nesta unidade de ensino possibilitarão que você aumente as
possibilidades de busca de soluções para a área de conhecimento em que se deseja resolver algum
tipo de problema. Os conceitos e exemplos permitirão que você possa ir gradativamente se
aventurando cada vez mais nos conhecimentos acerca da teoria dos grafos.
Processing math: 100%
Diversas aplicações que utilizamos diariamente possuem uma matriz que permite que ocorram
determinadas ações. Um desses exemplos se trata do programa que fornece a geolocalização em
tempo real, conhecido como GPS (Sistema de Posicionamento Global), que utiliza as coordenadas
para gerar valores que compreendem uma localização ao redor do planeta.
Segundo Baratojo (2007, p. 9), “as matrizes são conjuntos ordenados de elementos dispostos em m x
n, sendo m o número de linhas e n o número de colunas”.
Os elementos dessa matriz são dispostos por ai,j , em que:
a: é o elemento dessa matriz.
i: é o posicionamento de um elemento na linha de uma matriz.
j: é o posicionamento de um elemento na coluna de uma matriz.
Com isso os elementos de uma matriz são representados por:
A =[a1, 1 ⋯ a1, n
⋮ ⋱ ⋮
an, 1 ⋯ an, n]
Podemos determinar o tamanho de certa matriz, pois uma matriz A = m x n representa o número de
linhas e colunas de sua estrutura. Por exemplo: uma matriz A3x2 signi�ca que possui três linhas e
duas colunas, conforme representação a seguir:
A =[0 1 2
3 4 1]
As matrizes podem representar um conjunto de valores de qualquer ordem. Ainda é possível que se
efetuem operações como adição, subtração, multiplicação de matrizes, entre outras técnicas (não
sendo o foco da teoria dos grafos discutir os assuntos da Geometria analítica).
Caro(a) aluno(a), neste momento você deve estar se perguntando: mas o que as matrizes têm a ver
com a teoria dos grafos? Existem diversas formas de se representar os grafos, uma delas se dá por
meio das matrizes. Segundo Cardoso (2011), as matrizes na representação dos grafos são
conhecidas por lista de adjacências.
As listas de adjacências especi�cam os vértices e arestas de uma matriz, sendo representado por um
grafo G(V, A), onde:
G: é a representação de grafo.
V: os vértices do grafo.
A: as arestas do grafo.
MatrizesMatrizes
Processing math: 100%
Matriz Adjacência
Agora que você pode relembrar os conhecimentos básicos acerca das matrizes, podemos efetuar a
concatenação das duas áreas de conhecimentos, para obtermos uma nova ferramenta matemática,
de forma que permita ter um maior repertório de técnicas para a busca de soluções mais e�cientes.
Quando temos um grafo simples, em que |V| = n, em que “n” representa o tamanho dessa matriz e
considerando que os vértices de um determinado conjunto sejam representados por: V = {v_1, v_2,
v_3, …, v_n}, podemos dizer que a matriz adjacência, quando igual a 1, representa a ligação entre os
vértices, já quando igual a 0, existe ausência de aresta entre os nós.
Dessa forma, podemos representar esse conceito por meio da expressão:
aij ={1, se (i, j) ∈ E(G)
0, se (i, j) ∉ E(G)
Para melhor exempli�car as matrizes adjacentes na aplicação dos grafos, tome como exemplo a
matriz a seguir:
[ A B C D
A 0 1 0 1
B 1 0 1 0
C 0 1 0 1
D 1 0 1 0
]
Podemos representar a matriz por meio de um diagrama para que possibilite a melhor
compreensão das matrizes adjacentes. Para isso, observe a Figura 2.1.
Figura 2.1 - Exemplo de Matriz adjacente
Fonte: Elaborada pelo autor.
Podemos observar, por meio da análise da matriz em comparação com o grafo, que:
Na primeira linha e na coluna da matriz são representados os vértices de um grafo.
Os valores 0 encontrados nas matrizes representam que não há relação entre o mesmo
vértice ou com outros vértices.
Os valores 1 representam que há relação entre o mesmo vértice ou com outros vértices.
Ainda é possível representar um laço por meio de um apontamento no próprio vértice. Para isso, a
matriz deve possuir o valor 1 no cruzamento do mesmo nó. Pode ser representado como vn,n = 1, de
Processing math: 100%
forma que ganhe uma característica encontrada em um multigrafo.
Para esse exemplo, observe a matriz a seguir:
[ A B C D
A 1 1 0 1
B 1 0 1 0
C 0 1 0 1
D 1 0 1 0
]
Repare que, no índice da matriz na posição V0,0 = 1, ou seja, no vértice A, existe um apontamento
para o próprio vértice A. Para melhor compreensão, observe a Figura 2.2 para representação do
exemplo da matriz.
Figura 2.2 - Representação de grafo para vn , n = 1
Fonte: Elaborada pelo autor.
Podemos observar que, ao utilizarmos o valor 1 em vA,A, é determinado que a aresta será apontada
para o vértice onde se originou a aresta.
praticar
Vamos Praticar
A integração entre matrizes e grafos tende a agregar uma potencialidade nas possíveis aplicações contidas
na teoria dos grafos, de forma a auxiliar na busca de soluções e otimizações em diversas áreas do
conhecimento. O grafo apresentado a seguir foi originado de uma matriz, conforme pode ser observado na
�gura.
Processing math: 100%
Fonte: Elaborada pelo autor.
a) [1 1 1 1
1 0 1 1
0 1 0 1
1 1 1 0
]
b) [0 1 0 0
1 0 1 1
0 1 0 1
0 0 0 0
]
c) [1 1 0 0
1 0 1 1
0 1 0 1
0 1 1 0
]
d) [0 1 0 1
1 0 1 1
0 1 0 1
1 1 1 0
]
e) [1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
]
Processing math: 100%
Agora que você já compreendeu que por meio das matrizes podemos extrair dados para gerar os
grafos, vamos ampliar as possibilidades com uma discussão, onde serão utilizados mais tipos de
matrizes. Será possível utilizar uma ferramenta com maior gama de recursos.
Matriz Incidência
O termo incidência foi utilizado nos primeiros assuntos acerca de teoria dos grafos para indicar onde
determinada aresta que partiu de determinado vértice deve ser apontada (ligada). Esse mesmo
conceito deve ser aplicado nas matrizes incidência, para que assim seja possível desenvolver grafos
de qualquer um dos tipos, conforme poderá ser observado mais adiante.
Segundo Cardoso (2005), a matriz incidência G(V, A) é composta por “n” vértice e “m” arestas. Para
tal, a representação dos elementos de uma matriz dar-se-á por:
Vértices: v1, v2, v3, …, vn.
Arestas: a1, a2, a3, …, an.
A matriz incidência é uma relação de V e A, onde a mesma pode ser representada pela matriz M = mij
. Para determinar as incidências, deve ser seguida as regras, tal que,
Se mij = 1, aj incide em vi.
Se caso, mij = 0, então não ocorre incidência.
Para exempli�car o exposto, observe a matriz a seguir:
[ a1 a2 a3 a4
V1 1 1 0 0
V2 0 0 1 1
V3 0 1 0 1
V4 1 0 1 0
]
Para desenvolver o grafo referente a essa matriz, observe que:
Existem quatro vértices, sendo a1, a2, a3 e a4.
Na segunda coluna (a1), indica que existe uma aresta que liga v1 a v4.
Na terceira coluna (a2), indica que existe uma aresta que liga v1 a v3.
Na quarta coluna (a3), indica que existe uma aresta que liga v2 a v4.
Na quinta coluna (a4), indica que existe uma aresta que liga v2 a v3.
Com isso, é possívelcompreender a estrutura apresentada no grafo representado na Figura 2.3.
Mais Tipos de MatrizesMais Tipos de Matrizes
Processing math: 100%
Figura 2.3 - Representação de grafo por uma matriz incidência
Fonte: Elaborada pelo autor.
Para auxiliar na identi�cação dos vértices, temos que:
a1: v1 para v4.
a2: v1 para v3.
a3: v2 para v4.
a4: v2 para v3.
Observe a �gura a seguir, onde é possível identi�car as arestas descritas anteriormente.
Figura 2.4 - Identi�cação de arestas na matriz incidência
Fonte: Elaborada pelo autor.
A construção de uma matriz incidência pode ser compreendida como orientada a colunas, onde
existe a especi�cação dos relacionamentos entre os vértices, determinando, assim, como as arestas
estão dispostas no grafo.
Processing math: 100%
saiba mais
Saiba mais
A dissertação intitulada Teoria dos grafos e aplicações propõe
uma discussão sobre a aplicabilidade das matrizes frente às
possibilidades de desenvolvimento dos grafos.
SOUZA, A. L. Teoria dos grafos e aplicações . 78 p. 2013.
Dissertação (Mestrado em Matemática) - Instituto de
Ciências Exatas, Universidade Federal do Amazonas,
Manaus, 2013.
ACESSAR
Laços em Matriz Incidência
Assim como nas demais técnicas discutidas até o momento, na matriz incidência é possível ter laços,
onde uma aresta é apontada para o próprio vértice que a originou.
Segundo Cardoso (2011), para que ocorra um laço, uma coluna aj deve possuir apenas um valor 1,
determinando uma única incidência em vi. Isso garante que a aresta ax seja apontada para o próprio
vértice vx. Para compreensão desse conceito, observe a matriz a seguir:
[ a1 a2 a3 a4
V1 1 0 0 0
V3 0 1 1 0
V3 0 1 0 0
V4 0 0 1 1
]
Por meio dessa matriz, podemos perceber que:
Existem quatro vértices, sendo a1, a2, a3 e a4.
Na segunda coluna (a1), indica que existe um laço na aresta v1.
Na terceira coluna (a2), indica que existe uma aresta que liga v2 a v3.
Na quarta coluna (a3), indica que existe uma aresta que liga v2 a v4.
Na quinta coluna (a4), indica que existe um laço na aresta v4.
Com isso, é possível compreender a estrutura apresentada no grafo representado na Figura 2.5.
Processing math: 100%
https://tede.ufam.edu.br/bitstream/tede/4788/2/Disserta%C3%A7%C3%A3o%20-%20Audemir%20Lima%20de%20Souza.pdf
Figura 2.5 - Grafo com laço na matriz incidência
Fonte: Elaborada pelo autor.
Dessa forma, a matriz incidência permite que sejam construídos os grafos com diversos formatos,
dentro das técnicas discutidas até o momento.
praticar
Vamos Praticar
As matrizes incidência propõem a indicação de onde os vértices ligam um ao outro por meio das arestas.
Essa ferramenta pode ser aplicada em diversas áreas do conhecimento e permite, de forma simples,
representar os relacionamentos e, dessa forma, compreender as peculiaridades de certos sistemas. Com
base no exposto, observe as a�rmativas a seguir:
I.   A indicação dos relacionamentos é do tipo linear, ou seja, a orientação está nas linhas da matriz.
II.  O valor 0 (zero) indica que não existe relacionamento entre os vértices.
III. No laço existe um apontamento de va para vb.
Está correto o que se a�rma em:
a) I e II, apenas.
b) I e III, apenas.
c) II e III, apenas.
d) I, apenas.
e) II, apenas.
Processing math: 100%
Os vetores são ferramentas matemáticas muito importantes não só para a Geometria analítica, mas
também para as engenharias, a química e física. Como não podia ser diferente, a teoria dos grafos
também se apropria dos conceitos e das técnicas, a �m de desenvolver grafos na busca de resolução
de problemas. Na física, por exemplo, os vetores são usados para o cálculo de velocidade,
deslocamento, forças e etc.
Antes de iniciarmos os estudos das listas de adjacências (vetores que representam os grafos), é
necessário conhecer os conceitos e as aplicações dos vetores, para que possamos relacionar os
vetores com a teoria dos grafos. Dessa forma, faremos uma discussão acerca dos vetores, pois
servirá como alicerce para que possamos nos aprofundar nos conhecimentos dos grafos e dos
vetores.
Conceitos de Vetores
Os vetores são importantes ferramentas matemáticas que, por meio de conceitos simples, consegue
permitir soluções para diversas áreas do conhecimento. Para tal, inicialmente, existem alguns
conceitos primitivos importantes, entre eles:
Ponto : trata-se de um elemento �xo e único disposto em uma reta ou em um plano.
Podendo ser uma marca, furo, pingo e etc.
Reta : pode ser de�nido como um conjunto �nito de pontos. Um exemplo pode ser uma
linha de um caderno, linhas de uma quadra esportiva, etc.
Plano : é de�nido como uma superfície onde estão dispostos os pontos e as retas. Como
exemplo, podemos citar uma parede, um quadro, etc.
Para a compreensão de tais conceitos, observe como pode ser representado cada um dos
elementos na Figura 2.6.
VetoresVetores
Processing math: 100%
É possível conhecer os elementos essenciais para a compreensão dos vetores. Porém, outro
conceito importante para a compreensão é o termo relacionado a seguir:
Segmento : trata-se de um trecho reto que liga dois pontos. Sua limitação é representada
pelas letras A e B por exemplo. Como uma estrada que liga uma cidade à outra, é um
segmento que percorre o caminho da cidade A até a cidade B.
Para melhor compreensão, observe um exemplo de segmento representado na Figura 2.7.
É possível compreender que é a reta que passa por dois pontos, limitando o espaço a ser objeto de
estudo. As grandezas encontradas nos estudos relacionados aos vetores são classi�cadas em dois
grupos:
Escalar : são grandezas de�nidas por um valor de um módulo e a sua respectiva unidade
de medida, assim como temperatura e energia.
Figura 2.6 - Elementos do vetor
Fonte: Elaborada pelo autor.
Figura 2.7 - Segmento
Fonte: Elaborada pelo autor.
Processing math: 100%
Vetorial : o vetor, além do valor, necessita de direção e sentido. Um exemplo de aplicação
vetorial é velocidade e aceleração.
Vale aqui ressaltar dois conceitos utilizados para se de�nir os vetores:
Módulo : é a distância entre dois pontos. Não importando se o ponto A (início) está
localizado em um valor negativo. O que é calculado é o espaço percorrido entre os dois
pontos encontrados em um segmento. Para melhor compreensão, observe o exemplo na
Figura 2.8.
Figura 2.8 - Módulo
Fonte: Elaborada pelo autor.
Direção : signi�ca o sentido que é direcionado em um segmento de reta. Para a
compreensão desse conceito, observe a Figura 2.9.
Com isso foi possível compreender a importância do vetor, frente às necessidades encontradas nas
diversas áreas do conhecimento, e de que forma pode ser expresso matematicamente.
Figura 2.9 - Direção
Fonte: Elaborada pelo autor.
Processing math: 100%
praticar
Vamos Praticar
Os vetores são ferramentas da matemática que permitem uma vasta aplicação dos seus conhecimentos na
busca de soluções. Contudo, a sua estrutura é composta por diversos elementos que o compõem. Supondo
que um pesquisador queira analisar a taxa de deslocamento de determinado objeto em relação ao tempo,
assinale a alternativa que descreve qual elemento encontrado nos vetores é essencial para determinar tal
valor.
a) Ponto.
b) Reta.
c) Plano.
d) Direção.
e) Segmento.
Processing math: 100%
Caro(a) aluno(a), agora que você pode compreender como são formados os vetores e a sua
importância frente a diversas áreas, vamos atrelar esses conhecimentos à teoria dos grafos, a �m de
se ter mais uma ferramenta que permita o desenvolvimento de diagramas por meio de um conjunto
de valores.
Segundo Cardoso (2005), os vetores utilizados na teoria dos grafos são conhecidos como lista de
adjacências. Essas permitem que, por meio de uma lista de valores, seja possível compreender quais
são as representações dos vértices e os respectivos relacionamentos efetuados pelas arestas. A sua
aplicação na teoria dos grafos ocorre de uma forma bem simpli�cada, porém bastante e�ciente para
a construção dos grafos.
A lista de adjacências encontradas nateoria dos grafos é um G(V, A) em que n = |V| (n é o módulo
dos vértices), em cada entrada que é encontrada nos vértices de determinado grafo. Para tal, as
listas permitem o encadeamento dos vértices não direcionados. Para melhor compreensão, observe
o exemplo de um espaço vetorial:
Vértice A B D
De forma simples, é possível determinar que existe um agrupamento de valores em uma única linha,
onde a intenção é determinar que o vértice A possui arestas ligadas aos vértices B e D. Compreenda
os vetores como matrizes de apenas uma dimensão, ou seja, apenas uma linha é utilizada para
demonstrar os relacionamentos encontrados nos grafos.
reflita
Re�ita
Com uma base nas discussões acerca de matrizes e vetores, onde esses valores
agrupados são encontrados em atividades cotidianas? Ao encontrar tal
questionamento, como podemos utilizar as técnicas de teoria dos grafos, para
gerar qualidade nos processos, produtos ou serviços?
Assim, para compreender como um vetor é apresentado na teoria dos grafos, observe a
representação da Figura 2.10.
Lista de AdjacênciaLista de Adjacência
Processing math: 100%
Figura 2.10 - Vetor
Fonte: Elaborada pelo autor.
É possível utilizar os valores apresentados no vetor, para que seja desenvolvido o grafo, conforme
pode ser observado na Figura 2.11.
Pode-se observar que os valores são retirados do espaço vetorial para que possam compor o grafo.
Já quando se tem a necessidade de demonstrar os laços no vetor, deve-se observar:
Vértice A A D
A segunda coluna indica que existe uma aresta que deve fazer um apontamento para o próprio
vértice A, con�gurando dessa forma um laço. Para melhor compreensão dessa técnica, observe o
vetor demonstrado na Figura 2.12.
Figura 2.11 - Grafo por meio de valores do vetor
Fonte: Elaborada pelo autor.
Processing math: 100%
Figura 2.12 - Vetor com laço
Fonte: Elaborada pelo autor.
O vetor demonstrado na Figura 2.12 é representado na Figura 2.13 conforme pode ser observado a
seguir:
Conforme observado, pode-se perceber que os vetores são poderosas ferramentas matemáticas
que permitem agrupar valores e são facilmente representados pelos grafos.
praticar
Vamos Praticar
Figura 2.13 - Grafo a partir de um vetor com laço
Fonte: Elaborada pelo autor.
Processing math: 100%
Os vetores possibilitam que se implementem os grafos por meio de seu conjunto de valores agrupados nas
linhas. Com isso, é possível representar qualquer formato de grafo e, assim, permitir uma análise mais
precisa do conjunto de dados. Os dados apresentados no vetor a seguir é um desses exemplos:
Com base no vetor, assinale a alternativa que represente o grafo corretamente.
a)
b)
c)
Figura - Vetor em grafos.
Processing math: 100%
d)
e)
Processing math: 100%
indicações
Material Complementar
LIVRO
Matrizes, Vetores e Geometria Análitica
Editora : Livraria Nobel
Autor : Alésio João de Caroli
Ano :
Comentário : A �m de se construir um alicerce acerca de matriz e vetor,
para ampliar a aplicabilidade na teoria dos grafos, esse livro é um
clássico. Possuí uma leitura de fácil compreensão, permitindo que se
construa o conhecimento de forma muito concisa.
FILME
Matrizes
Ano : 2017
Comentário : Uma aula a respeito de matrizes ministrada na Univesp,
onde é possível conhecer mais propriedades e aplicações.
TRA ILER
Processing math: 100%
conclusão
Conclusão
As matrizes e os vetores são ferramentas matemáticas que possibilitam a integração com diversas
outras técnicas, e isso permite que se possa implementar soluções em diversas áreas do
conhecimento. Os grafos possuem alto potencial de adaptação com as técnicas de matriz e vetor e
garantem o desenvolvimento de grafos não direcionados, com integração a laços e demais tipos de
grafos.
Por meio dos estudos de matrizes e vetores, alicerça o conhecimento para que, assim, se possa
utilizar os conhecimentos nas aplicações práticas da teoria dos grafos. Esses conhecimentos podem
ser aplicados em áreas como engenharia, computação, química, biologia, entre diversas outras áreas
do conhecimento.
referências
Referências Bibliográ�cas
BARATOJO, J. T. Matrizes determinantes sistemas de equações lineares . Porto Alegre: EDIPUCRS,
2007.
CARDOSO, D. M. Teoria dos grafos e aplicações . Universidade de Aveiro, 2005.
SOUZA, A. L. Teoria dos grafos e aplicações. 78 p. 2013. Dissertação (Mestrado em Matemática) -
Instituto de Ciências Exatas, Universidade Federal do Amazonas, Manaus, 2013. Disponível em:
https://tede.ufam.edu.br/bitstream/tede/4788/2/Disserta%C3%A7%C3%A3o%20-
%20Audemir%20Lima%20de%20Souza.pdf . Acesso em: 20 jan. 2020.
Processing math: 100%
https://tede.ufam.edu.br/bitstream/tede/4788/2/Disserta%C3%A7%C3%A3o%20-%20Audemir%20Lima%20de%20Souza.pdf
https://tede.ufam.edu.br/bitstream/tede/4788/2/Disserta%C3%A7%C3%A3o%20-%20Audemir%20Lima%20de%20Souza.pdf