Aula_03_-Matriz_e_Lista_de_Adjacencia_

Prévia do material em texto

ARA0175-ALGORITMOS EM GRAFOS
MATRIZ DE ADJACÊNCIA E LISTA DE ADJACÊNCIA
Tema
2ARA0175-ALGORITMOS EM GRAFOS
MATRIZ DE ADJACÊNCIA E LISTA DE ADJACÊNCIA
Agenda
AULA 1: APRESENTAÇÃO DA DISCIPLINA
• Objetivos da aula
• Contexto
• Introdução
• Tipos de Matriz
- Simples 
- Direcionada
• Matriz de Adjacência
• Lista de Adjacência
• Kahoot
ARA0175-ALGORITMOS EM GRAFOS
Objetivos
AULA 1: APRESENTAÇÃO DA DISCIPLINA
-Construir uma matriz/lista de adjacência;
ARA0175-ALGORITMOS EM GRAFOS
-Compreender matriz de adjacência ;
-Compreender lista de adjacência;
Contexto
AULA 1: APRESENTAÇÃO DA DISCIPLINA
A teoria dos grafos apresenta diversas formas de representa-los e a
matriz de adjacência é uma delas, outra forma é a lista de Adjacência,
que também podem ser implementadas a partir de uma Grafo simples
ou direcionado (orientado).
ARA0175-ALGORITMOS EM GRAFOS
Conceitos e formalização de grafos
AULA 1: APRESENTAÇÃO DA DISCIPLINA
é uma matriz de representação de grafos, onde os elementos podem ser booleanos
e acessados de maneira direta.
ARA0175-ALGORITMOS EM GRAFOS
O que é uma matriz de adjacência?
Grafo simples não direcionado
Conceitos e formalização de grafos
AULA 1: APRESENTAÇÃO DA DISCIPLINA
é uma matriz de representação de grafos, onde os elementos podem ser booleanos
e acessados de maneira direta.
ARA0175-ALGORITMOS EM GRAFOS
O que é uma matriz de adjacência?
Onde, 
Para representar um grafo não direcionado, simples e
sem pesos nas arestas, basta que as entradas aij da
matriz A contenham 1 se vi e vj são adjacentes e 0 caso
contrário.
Observação: um grafo simples retorna uma matriz booleana, ou seja, composta
por 0 e 1
Matriz de Adjacência
AULA 1: APRESENTAÇÃO DA DISCIPLINA
O primeiro passo é identificar no grafo quem são os vértices e suas respectivas arestas,
caso os tenham G = (V, A),onde V é o conjunto de vértices e A é o conjunto de arestas.
ARA0175-ALGORITMOS EM GRAFOS
A
BE
D C
V = (A ,B ,C ,D ,E)
A = { (A,B) ;(B,A);(A,E);(E,A);(B,C);(C,B);(C,D);(D,C);(D,E);(E,D)}
Possíveis arestas:
Posicionamento dos elementos da matriz de Adjacência
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
linha i=1 primeira linha
Onde, 
A
B
C
D
E
A B C D E
coluna j=1 primeira coluna
coluna j=2 segunda coluna
linha i=1 primeira linha
coluna j=3 terceira coluna
linha i=1 primeira linha
“i” = linha
“j” = coluna
coluna j=4 quarta coluna
linha i=1 primeira linha
coluna j=5 quinta coluna
linha i=1 primeira linha
Diagonal principal da matriz
(a11,a22, a33, a44 e a55)
Matriz n x n
Posicionamento dos elementos da matriz de Adjacência
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
linha i=A primeira linha
Onde, 
A
B
C
D
E
A B C D E
A
coluna j=A primeira coluna
A
coluna j=B segunda coluna
B
linha i=A primeira linha
A
coluna j=C terceira coluna
C
linha i=A primeira linha
A
“i” = linha
“j” = coluna
coluna j=D quarta coluna
D
linha i=A primeira linha
A EA
coluna j=E quinta coluna
linha i=A primeira linha
Diagonal principal da matriz
(AA, BB, CC, DD, EE)
Matriz n x n
B A BB CB DB EB
C A BC CC DC EC
D A BD CD DD ED
E A BE CE DE EE
Definição da matriz de Adjacência
ARA0175-ALGORITMOS EM GRAFOS
Onde, 
A
B
C
D
E
A B C D E
0 1 0
“i” = linha
“j” = coluna
0 1
Diagonal principal da matriz
(0, 0, 0, 0, 0)
Matriz n x n
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
Definição da matriz de Adjacência
ARA0175-ALGORITMOS EM GRAFOS
Onde, 
A
B
C
D
E
A B C D E
0 1 0
“i” = linha
“j” = coluna
0 1
ObservaçãoII: se a Diagonal principal
da matriz for igual a zero é porque o
grafo não possui laço.
(0, 0, 0, 0, 0)
Matriz n x n
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 0 0 1 0
Observe que a
parte da diagonal
superior da matriz
é igual a parte
diagonal inferior.
Observação I: o grafo simples retornou uma matriz booleana composta por 0 e 1
Matriz de Adjacência com grafo direcionado ou orientado
AULA 1: APRESENTAÇÃO DA DISCIPLINA
O primeiro passo é identificar no grafo quem são os vértices e suas respectivas arestas,
caso os tenham G = (V, A),onde V é o conjunto de vértices e A é o conjunto de arestas.
ARA0175-ALGORITMOS EM GRAFOS
A
BC
D
V = (A ,B ,C ,D)
A = { (A,B);(A,E);(B,D) ;(D,A);(D,C)}
Matriz de Adjacência com grafo direcionado
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
A
BC
D
V = (A ,B ,C ,D)
A = { (A➔B);(A➔C);(B➔D);(D➔A);(D➔C)}
A
B
C
D
A B C D
0 1 1 0
0 0 0 1
0 0 0 0
1 0 1 0
Observação I: Num grafo orientado a matriz de retorno é sempre assimétrica
Conceitos e formalização de grafos
AULA 1: APRESENTAÇÃO DA DISCIPLINA
É um grafo onde para cada vértice do grafo, fazemos uma lista de todos os outros vértices 
com os quais ele tem uma aresta.
ARA0175-ALGORITMOS EM GRAFOS
O que é uma lista de adjacência?
Grafo simples não direcionado
Conceitos e formalização de grafos
AULA 1: APRESENTAÇÃO DA DISCIPLINA
É um grafo onde para cada vértice do grafo, fazemos uma lista de todos os outros vértices 
com os quais ele tem uma aresta.
ARA0175-ALGORITMOS EM GRAFOS
O que é uma lista de adjacência?
a
b
c
d
e
b c e .
a c d .
a b d e .
c .b
a c .
Observação I: Neste caso a representação é somente das arestas que envolve o vértice. Ex. O vértice “a” são todas
as arestas que ele esta envolvido.
Espaço para colocar o peso das arestas.
Conceitos e formalização de grafos
AULA 1: APRESENTAÇÃO DA DISCIPLINA
É um grafo onde para cada vértice do grafo, fazemos uma lista de todos os outros vértices 
com os quais ele tem uma aresta.
ARA0175-ALGORITMOS EM GRAFOS
O que é uma lista de adjacência?
Grafo com laço:
Conceitos e formalização de grafos
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
Lista com grafos orientados
Grafo não orientado:
Grafo orientado:
Conceitos e formalização de grafos
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
O que é uma lista de adjacência?
Conclui-se que para um Grafo orientado em geral é melhor a lista de adjacência,
em relação a um Grafo não orientado é melhor a matriz de adjacência, do ponto de
vista de consumo de memória.
Créditos
AULA 1: APRESENTAÇÃO DA DISCIPLINAARA0175-ALGORITMOS EM GRAFOS
Professor Maioli (UNICAMP)
Sistemas Embarcados
Bibliografia Básica
NETTO, Paulo O. B.; JURKIEWICZ, Samuel. Grafos: 
Introdução e Prática. 2 ed.. São Paulo:
Blucher, 2017. Disponível em: 
https://plataforma.bvirtual.com.br/Acervo/Publicacao/173348
SCHEINERMAN, Edward R. Matemática Discreta: uma 
introdução. São Paulo: Cengage
Learning., 2016. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788522125388
/cfi/0!/4/2@100:0.00
SIMÕES PEREIRA, J.M.S. Grafos e Redes: Teoria e 
Algoritmos Básicos. RJ: Ed. Rio de Janeiro,
2013. Disponível em: 
https://plataforma.bvirtual.com.br/Leitor/Publicacao/42049/pdf
ARA0175-ALGORITMOS EM GRAFOS
Sistemas Embarcados
Bibliografia Complementar
AIGNER, Martin. Paul. Erdós: As mais belas demonstrações matemáticas. São Paulo: 
Blucher,2017. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788521210047/cfi/0!/4/2@100:0.00
DASGUPTA, Sanjoy. Algoritmos. Porto Alegre: AMGH, 2010.
Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788563308535/cfi/0!/4/2@100:0.00
DROZDEK, Adam. Estrutura de Dados e Algoritmos em C++. São Paulo: Cengage
Learning Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788522126651/cfi/0!/4/2@100:0.00
LOESCH, CLa?udio; HEIN, Nelson. Pesquisa Operacional: Fundamentos e modelos. São 
Paulo:Saraiva, 2009. Disponível em:
https://integrada.minhabiblioteca.com.br/#/books/9788502088924/cfi/0!/4/2@100:0.00
STEIN, Clifford; DRYSDALE, Robert L.; BOGART, Kenneth. Matemática Discreta para 
Ciência da Computação. São Paulo: Pearson, 2013.
Disponível em: https://plataforma.bvirtual.com.br/Acervo/Publicacao/3824
ARA0175-ALGORITMOS EM GRAFOS