Aula 7 - Grafos

Prévia do material em texto

Grafos
Prof. Diego Brandão
Centro Federal de Educação Tecnológica Celso Suckow da Fonceca (CEFET/RJ)
Departamento Acadêmico de Informática (DEPIN)
16 de Maio de 2019
Diego Brandão (CEFET/RJ) Matemática Discreta 1 / 1
Roteiro
Diego Brandão (CEFET/RJ) Matemática Discreta 2 / 1
Introdução
Grafos, Vértices e Arestas
Um grafo é uma tripla ordenada (N,A, g) onde:
N = um conjunto não-vazio de vértices (nós ou nodos);
A = um conjunto de arestas (arcos);
g = uma função que associa cada aresta a a um par não-ordenado x-y de
vértices chamados de extremos de a.
A função g relaciona cada aresta a seus extremos; cada aresta está relacionada
a um único par de vértices extremos.
Diego Brandão (CEFET/RJ) Matemática Discreta 3 / 1
Exemplo 01
O conjunto de vértices do mapa de uma empresa aérea corresponde às cidades
Chicago, Nashville, Miami, Dallas, St. Louis, Albuquerque, Phoenix, Denver,
San Francisco, Los Angeles. Existem 16 arestas; por exemplo,
Phoenix-Albuquerque, Albuquerque-Dallas etc.
Diego Brandão (CEFET/RJ) Matemática Discreta 4 / 1
Exemplo 02
No grafo da figura abaixo, temos cinco vértices e seis arestas. A função que
associa as arestas aos seus extremos assume os seguintes valores: g(a1) = {1,
2}, g(a2) = {1, 2} g(a3) = {2, 2}, g(a4) = {2, 3}, g(a5) = {1, 3} e g(a6) = {3,
4}.
Diego Brandão (CEFET/RJ) Matemática Discreta 5 / 1
Terminologia - vértices adjacentes
Definição
Dois vértices em um grafo são ditos adjacentes se forem os extremos de uma
mesma aresta.
Por exemplo, no grafo abaixo, 1 e 3 são vértices adjacentes, mas 1 e 4 não
são. O vértice 2 é adjacente a ele mesmo.
Diego Brandão (CEFET/RJ) Matemática Discreta 6 / 1
Terminologia - vértices adjacentes
Definição
Dois vértices em um grafo são ditos adjacentes se forem os extremos de uma
mesma aresta.
Por exemplo, no grafo abaixo, 1 e 3 são vértices adjacentes, mas 1 e 4 não
são. O vértice 2 é adjacente a ele mesmo.
Diego Brandão (CEFET/RJ) Matemática Discreta 6 / 1
Terminologia - laços e arestas paralelas
Definição
Um laço em um grafo G é uma aresta com extremos n-n para algum vértice n
de G.
Definição
Arestas paralelas são aquelas que possuem os mesmos extremos.
Na figura abaixo, a aresta a3 é um laço com extremos 2-2; as arestas a1 e a2
são paralelas.
Diego Brandão (CEFET/RJ) Matemática Discreta 7 / 1
Terminologia - laços e arestas paralelas
Definição
Um laço em um grafo G é uma aresta com extremos n-n para algum vértice n
de G.
Definição
Arestas paralelas são aquelas que possuem os mesmos extremos.
Na figura abaixo, a aresta a3 é um laço com extremos 2-2; as arestas a1 e a2
são paralelas.
Diego Brandão (CEFET/RJ) Matemática Discreta 7 / 1
Terminologia - grafo simples
Definição
Um grafo simples é um grafo que não nem tem arestas paralelas nem laços.
Diego Brandão (CEFET/RJ) Matemática Discreta 8 / 1
Terminologia - grafo simples
Definição
Um grafo simples é um grafo que não nem tem arestas paralelas nem laços.
Diego Brandão (CEFET/RJ) Matemática Discreta 8 / 1
Terminologia - vértice isolado e grau
Definição
Um vértice isolado não é adjacente a qualquer outro vértice.
Definição
O grau de um vértice é o número de arestas que o tem como ponto extremo.
(Eventuais laços são contados duas vezes no cálculo.)
Na figura abaixo, 5 é um vértice isolado. Os vértices 1 e 3 têm grau 3, o
vértice 2 tem grau 5, o vértice 4 tem grau 1 e o vértice 5 tem grau 0.
Diego Brandão (CEFET/RJ) Matemática Discreta 9 / 1
Terminologia - vértice isolado e grau
Definição
Um vértice isolado não é adjacente a qualquer outro vértice.
Definição
O grau de um vértice é o número de arestas que o tem como ponto extremo.
(Eventuais laços são contados duas vezes no cálculo.)
Na figura abaixo, 5 é um vértice isolado. Os vértices 1 e 3 têm grau 3, o
vértice 2 tem grau 5, o vértice 4 tem grau 1 e o vértice 5 tem grau 0.
Diego Brandão (CEFET/RJ) Matemática Discreta 9 / 1
Terminologia - grafo completo
Definição
Um grafo completo é um grafo simples e não direcionado no qual todos os
vértices distintos são adjacentes (i.e., são conectados por uma única aresta).
Um grafo completo cuja quantidade de vértices é n é denotado por Kn.
No caso de grafos completos:
g é uma função injetiva, e consequentemente há apenas uma aresta
associada a cada par de vértices (i.e., o grafo não possui arestas
paralelas).
g é quase uma função sobrejetiva: todo par x-y de vértices distintos está
no conjunto imagem de g, mas não há um laço em cada vértice, de forma
que pares do tipo x-x não têm imagem.
Diego Brandão (CEFET/RJ) Matemática Discreta 10 / 1
Terminologia - grafo completo
O grafo abaixo é denominado K5, o grafo completo de 5 vértices.
Diego Brandão (CEFET/RJ) Matemática Discreta 11 / 1
Terminologia - subgrafo
Definição
Um subgrafo G′(V ′,E′) de um grafo G(V,E) é tal que:
V ′ ⊆ V
E′ ⊆ E (ou seja, os extremos de qualquer aresta em G′ precisam ser os
mesmos que em G′)
Um subgrafo é obtido por meio da remoção de partes (arestas ou vértices) do
grafo original e deixando o restante sem alterações.
Diego Brandão (CEFET/RJ) Matemática Discreta 12 / 1
Terminologia - subgrafo
Como exemplo, a figura abaixo apresenta dois subgrafos do grafo apresentado
anteriormente.
Diego Brandão (CEFET/RJ) Matemática Discreta 13 / 1
Terminologia - caminho
Definição
Um caminho de um vértice n0 a um vértice nk é uma seqüência
n0, a0, n1, a1, . . . , nk−1, ak−1, nk de vértices e arestas, onde para cada i, os
extremos da aresta ai são ni e ni+1.
No grafo abaixo, por exemplo, um dos caminhos entre os vértices 2 e 4
consiste na sequência 2, a1, 1, a2, 2, a4, 3, a6, 4.
Diego Brandão (CEFET/RJ) Matemática Discreta 14 / 1
Terminologia - caminho
Definição
Um caminho de um vértice n0 a um vértice nk é uma seqüência
n0, a0, n1, a1, . . . , nk−1, ak−1, nk de vértices e arestas, onde para cada i, os
extremos da aresta ai são ni e ni+1.
No grafo abaixo, por exemplo, um dos caminhos entre os vértices 2 e 4
consiste na sequência 2, a1, 1, a2, 2, a4, 3, a6, 4.
Diego Brandão (CEFET/RJ) Matemática Discreta 14 / 1
Terminologia - comprimento de um caminho
Definição
O comprimento de um caminho é o número de arestas que ele contém; se uma
aresta for usada mais de uma vez, ela deve ser contada tantas vezes quantas
for usada.
No grafo a seguir, o comprimento do caminho (2,a1, 1, a2, 2, a4, 3, a6, 4) é 4.
Diego Brandão (CEFET/RJ) Matemática Discreta 15 / 1
Terminologia - comprimento de um caminho
Definição
O comprimento de um caminho é o número de arestas que ele contém; se uma
aresta for usada mais de uma vez, ela deve ser contada tantas vezes quantas
for usada.
No grafo a seguir, o comprimento do caminho (2,a1, 1, a2, 2, a4, 3, a6, 4) é 4.
Diego Brandão (CEFET/RJ) Matemática Discreta 15 / 1
Terminologia - conectividade
Definição
Um grafo conexo é aquele no qual há um caminho entre quaisquer dois
vértices. Em caso contrário, o grafo é dito desconexo.
Ambos os grafos apresentados abaixo são conexos.
Diego Brandão (CEFET/RJ) Matemática Discreta 16 / 1
Terminologia - conectividade
Definição
Um grafo conexo é aquele no qual há um caminho entre quaisquer dois
vértices. Em caso contrário, o grafo é dito desconexo.
Ambos os grafos apresentados abaixo são conexos.
Diego Brandão (CEFET/RJ) Matemática Discreta 16 / 1
Terminologia - ciclo
Definição
Um ciclo em um grafo é um caminho de algum vértice n0 até n0 de novo, de
forma que nenhum vértice ocorra mais de uma vez no caminho. Um grafo
sem ciclos é dito acíclico.
n0 é o único vértice que ocorre mais de uma vez e este ocorre apenas nos
extremos do caminho.
Os vértices e as arestas podem repetir-se em um caminho, mas não em
um ciclo - exceto pelo vértice n0.
Como exemplo,no grafo abaixo, (1, a1, 2, a4, 3, a5, 1) é um ciclo.
Diego Brandão (CEFET/RJ) Matemática Discreta 17 / 1
Terminologia - ciclo
Definição
Um ciclo em um grafo é um caminho de algum vértice n0 até n0 de novo, de
forma que nenhum vértice ocorra mais de uma vez no caminho. Um grafo
sem ciclos é dito acíclico.
n0 é o único vértice que ocorre mais de uma vez e este ocorre apenas nos
extremos do caminho.
Os vértices e as arestas podem repetir-se em um caminho, mas não em
um ciclo - exceto pelo vértice n0.
Como exemplo, no grafo abaixo, (1, a1, 2, a4, 3, a5, 1) é um ciclo.
Diego Brandão (CEFET/RJ) Matemática Discreta 17 / 1
Grafo Direcionado
Grafo Direcionado
Um grafo direcionado (digrafo) é uma tripla ordenada (N,A, g) onde:
N = um conjunto de vértices;
A = um conjunto de arestas;
g = uma função que associe a cada aresta a um par ordenado (x, y) de
vértices, onde x é o ponto inicial e y é o ponto final de a.
Em um grafo direcionado, portanto, existe uma direção associada a cada
aresta.
Diego Brandão (CEFET/RJ) Matemática Discreta 18 / 1
Grafo Direcionado
Um caminho do vértice n0 até o vértice nk é uma seqüência n0, a0, n1,
a1, . . ., nk−1, ak−1, nk onde, para cada i, ni é o ponto inicial e ni+1 é o
ponto final de a se existe um caminho do vértice n0 até o vértice nk,
então nk é alcançável a partir de n0.
A definição de ciclo também se aplica a grafos direcionados.
Uma fonte é um vértice que possui grau de entrada igual a zero.
Um sumidouro é um vértice que possui apenas arestas incidentes (grau
de saída igual a zero).
Cada vértice possui graus de entrada e de saída.
Diego Brandão (CEFET/RJ) Matemática Discreta 19 / 1
Exemplo 13
No grafo direcionado a seguir,
existem diversos caminhos do vértice 1 ao vértice 3: (1, a4, 3) e (1, a1, 2,
a2, 2, a2, 2, a3, 3) são dois possíveis caminhos.
o vértice 3 é alcançável a partir do vértice 1.
o vértice 1 não é alcançável a partir de qualquer outro vértice.
os ciclos são o laço a2, e o caminho (3, a5, 4, a6, 3).
Diego Brandão (CEFET/RJ) Matemática Discreta 20 / 1
Roteiro
Diego Brandão (CEFET/RJ) Matemática Discreta 21 / 1
Representações Computacionais de Grafos
Para o armazenamento e manipulação de grafos por um computador, eles
precisam ser representados de forma adequada.
Duas estruturas de dados podem ser usadas para representação
computacional de grafos.
matriz de adjacências
lista de adjacências
Diego Brandão (CEFET/RJ) Matemática Discreta 22 / 1
Matriz de Adjacências
Suponha que um grafo tem n vértices numerados n1, n2, . . ., nn.
Esta numeração define uma ordenação arbitrária no conjunto de vértices.
(serve para identificar os vértices)
De posse dos vértices ordenados, podemos formar uma matriz n× n
onde o elemento (i, j) é o número de arestas entre o vértice ni e nj.
Esta é a chamada de matriz de adjacências A do grafo com relação à
ordenação.
Portanto, aij = p onde existem p arestas entre ni e nj.
Diego Brandão (CEFET/RJ) Matemática Discreta 23 / 1
Exemplo 19
Considere o grafo abaixo. Considere também a ordenação (arbitrária) 1, 2, 3,
4 de seus vértices:
Diego Brandão (CEFET/RJ) Matemática Discreta 24 / 1
Exemplo 19 (cont.)
Sobre o grafo anterior, podemos afirmar que:
a matriz de adjacências é da ordem 4× 4;
o elemento (1,1) é um 1 porque há um laço no vértice 1;
todos os demais elementos da diagonal são 0;
o elemento (2,1) é 1 porque há apenas uma aresta entre os vértices 2 e 1,
o que também indica que o elemento (1,2) é 1.
Até este ponto, temos o seguinte:
Diego Brandão (CEFET/RJ) Matemática Discreta 25 / 1
Matriz de adjacências para grafos direcionados
Em um grafo direcionado, sua matriz de adjacências reflete a direção das
arestas.
Em uma matriz direcionada aij = p, onde p é o número de arestas do
vértice ni para o vértice nj.
Uma matriz de adjacências de um grafo direcionado não é
necessariamente simétrica, uma vez que uma aresta do vértice ni para o
vértice nj não implica uma aresta do vértice nj para o vértice ni.
Em um grafo simples ponderado, os elementos da matriz de adjacências
podem indicar o peso de cada aresta, em vez de apenas indicar a
presença ou não da aresta.
Diego Brandão (CEFET/RJ) Matemática Discreta 26 / 1
Exemplo 20
Um exemplo de grafo direcionado e sua matriz de adjacências são
apresentados abaixo.
Diego Brandão (CEFET/RJ) Matemática Discreta 27 / 1
Lista de Adjacências
Diversos grafos, ao contrário de serem completos, têm relativamente
poucas arestas.
Esses grafos têm matrizes de adjacências ditas esparsas; isto é, suas
matrizes de adjacências contêm muitos zeros.
No caso de o grafo ter n vértices, serão necessários n2 elementos para
representar sua matriz de adjacências, ainda que a maior parte desses
elementos seja zero.
Nesse caso, a representação com matrizes de adjacências é ineficiente
computacionalmente.
Um grafo com relativamente poucas arestas pode ser representado mais
eficientemente se armazenarmos apenas os elementos não-nulos de sua
matriz de adjacências.
Diego Brandão (CEFET/RJ) Matemática Discreta 28 / 1
Lista de Adjacências
Esta representação consiste em uma lista para cada vértice de todos os
vértices adjacentes a ele.
Esta representação na forma de lista encadeada pode ser mais eficiente
que a matriz de adjacências.
Para encontrarmos todos os vértices adjacentes a ni, precisamos varrer a
lista referente a ni, que deve ter menos elementos que os n que teríamos
que examinar na matriz de adjacências.
No entanto, se desejarmos determinar se um vértice nj é adjacente ao
vértice ni, temos que varrer toda a lista encadeada de nj, enquanto que na
matriz de adjacências poderíamos pesquisar o elemento (i, j) diretamente.
Diego Brandão (CEFET/RJ) Matemática Discreta 29 / 1
Exemplo 21
Considere o grafo abaixo.
Diego Brandão (CEFET/RJ) Matemática Discreta 30 / 1
Exemplo 21 (cont.)
Sua lista de adjacências contém um vetor de quatro elementos de ponteiros,
um para cada vértice. O ponteiro de cada vértice aponta para um vértice
adjacente, que aponta para outro vértice adjacente, e assim por diante. A
estrutura da lista de adjacências é apresentada abaixo.
Diego Brandão (CEFET/RJ) Matemática Discreta 31 / 1
Roteiro
Diego Brandão (CEFET/RJ) Matemática Discreta 32 / 1
Relação de adjacência
Suponha que G(V,E) é um grafo direcionado com n vértices e sem arestas
paralelas.
Se (ni, nj) é um par ordenado de vértices, então existe ou não uma aresta
entre os vértices ni e nj.
Podemos usar esta propriedade para definir uma relação binária 𝜌 no
conjunto V:
ni 𝜌 nj se, e somente se, existe uma aresta em G de ni para nj.
Esta relação é a denominada relação de adjacência do grafo.
Diego Brandão (CEFET/RJ) Matemática Discreta 33 / 1
Relação de adjacência - exemplo
Exemplo
Para o grafo direcionado abaixo, qual a relação de adjacência correspondente?
Solução.
{(1, 2), (1, 3), (3, 3), (4, 1), (4, 2), (4, 3)}
Diego Brandão (CEFET/RJ) Matemática Discreta 34 / 1
Relação de adjacência - exemplo
Exemplo
Para o grafo direcionado abaixo, qual a relação de adjacência correspondente?
Solução.
{(1, 2), (1, 3), (3, 3), (4, 1), (4, 2), (4, 3)}
Diego Brandão (CEFET/RJ) Matemática Discreta 34 / 1
Relação de adjacência - exemplo
Exemplo
Para o conjunto V = {1, 2, 3, 4} e a relação de adjacência em V dada por
{(1, 4), (2, 3), (2, 4), (4, 1)}, qual o grafo direcionado correspondente?
Solução.
Diego Brandão (CEFET/RJ) Matemática Discreta 35 / 1
Relação de adjacência - exemplo
Exemplo
Para o conjunto V = {1, 2, 3, 4} e a relação de adjacência em V dada por
{(1, 4), (2, 3), (2, 4), (4, 1)}, qual o grafo direcionado correspondente?
Solução.
Diego Brandão (CEFET/RJ) Matemática Discreta 35 / 1
Roteiro
Diego Brandão (CEFET/RJ)Matemática Discreta 36 / 1
Isomorfismo de grafos
Dois grafos podem parecer diferentes em suas representações gráficas,
mas, ainda assim, ser equivalentes de acordo com a definição dada.
Por exemplo, os grafos abaixo são os mesmos; eles têm os mesmos
vértices, as mesmas arestas e a mesma função de associação de arestas a
seus extremos.
Diego Brandão (CEFET/RJ) Matemática Discreta 37 / 1
Isomorfismo de grafos
O grafo da figura abaixo também é o mesmo grafo que os das figuras
anteriores. Se mudarmos os rótulos dos vértices e arestas do grafo à esquerda
da figura anterior segundo a correspondência a seguir, os grafos se tornarão os
mesmos:
f1: 1 → a, 2 → c, 3 → b, 4 → d.
f2: a1 → e2, a2 → e1.
Diego Brandão (CEFET/RJ) Matemática Discreta 38 / 1
Isomorfismo de grafos
Estruturas que são iguais, a menos de um novo rotulamento de seus
elementos, são chamadas de isomorfas.
Para mostrar que duas estruturas são isomorfas, precisamos produzir
novos rótulos (uma função bijetiva entre os elementos de ambas as
estruturas) e então mostrar que as propriedades importantes das
estruturas são mantidas pelo novo rotulamento.
No caso de a estrutura ser um grafo, os elementos são vértices e arestas,
e a propriedade importante é a lista de quais arestas conectam quais
vértices.
Diego Brandão (CEFET/RJ) Matemática Discreta 39 / 1
Exemplo 04
Os grafos mostrados na figura abaixo são isomorfos. As bijeções que
estabelecem o isomorfismo são parcialmente dadas abaixo:
f1: 1 → c, 2 → e, 3 → d, 4 → b, 5 → a.
f2: a1 → e1, a2 → e4, a3 → e2, . . ..
Diego Brandão (CEFET/RJ) Matemática Discreta 40 / 1
Detecção de isomorfismo
Apesar de não ser uma tarefa simples em todos os casos, existem certas
condições sob as quais se torna fácil ver que dois grafos NÃO são isomorfos.
Essas condições incluem as seguintes:
a) Um grafo tem mais vértices que o outro.
b) Um grafo tem mais arestas que o outro.
c) Um grafo tem arestas paralelas e o outro não.
d) Um grafo tem um laço e o outro não.
e) Um grafo tem um vértice de grau k e o outro não.
f) Um grafo é conexo e o outro não.
g) Um grafo tem um ciclo e o outro não.
Diego Brandão (CEFET/RJ) Matemática Discreta 41 / 1