PAA-10-introducaoGrafos

Prévia do material em texto

Profa. Thaís Alves Burity Rocha 
GRAFOS 
Agenda 
 Definição 
 
 Exemplos de problemas 
 
 Conceitos básicos 
 
 
 
 
 
Introdução 
 Grafo é um modelo matemático que representa relações 
de interdependência entre objetos de um conjunto 
 Vértices 
 Arestas 
 
 Muitos problemas algorítmicos são simplificados se 
pensados em termos de grafos 
 
 Exemplos 
 Descobrir a melhor rota para um restaurante em uma cidade 
 Escalonamento de classes em uma universidade 
 
Outras definições 
 Ferramenta para resolver problemas 
 
 Estrutura de dados 
 
 Ferramenta de modelagem 
 
 Ferramenta utilizada na abstração de problemas 
computacionais 
Origem 
 A teoria dos grafos foi originada da solução 
definida por Leonhard Euler, em 1736, para o 
famoso problema matemático das pontes de 
Konigsberg 
 
 Lembrando que a palavra grafo e o seu uso 
generalizado para a resolução de problemas só 
surgiram a partir do final do século 19 
a 
b 
c 
d 
 Há como percorrer todas as 7 pontes, sem passar mais de 
uma vez por qualquer uma delas, e voltar ao ponto de 
partida? 
Pontes de Konigsberg 
Pontes de Konigsberg 
a 
b 
c 
d 
 Euler provou não ser possível 
 Para atravessar qualquer vértice, são 
gastas 2 linhas: 
 1 linha para entrar no vértice 
 1 linha para sair no vértice 
 Conclusão: 
 Cada vértice deve ter grau par de linhas 
 O grafo das pontes de Konigsberg tem 
pontos de grau ímpar e, portanto, o 
problema não pode ter solução 
 
Pontes de Konigsberg 
Pontes de Konigsberg 
 Aspectos relevantes da solução de Euler 
 Foram eliminados os detalhes geométricos do 
problema, como o comprimento das pontes, a sua 
forma, o tamanho das ilhas 
 Foco somente ao que importava 
 Capacidade de abstração 
 
 Teorema: Grafo de Euler 
 (i) de uma aresta é possível chegar em qualquer outra 
 (ii) o número de arestas de cada vértice é par 
Exemplos 
 A ideia de grafos serve de modelo para uma enorme 
quantidade de problemas práticos 
 Exemplos: 
 Entrega de cartas: O carteiro parte da sede dos correios, 
percorre as ruas para fazer as entregas e volta ao seu 
posto de trabalho. É preciso que o carteiro evite ao máximo 
passar na mesma rua mais de uma vez. 
 Coleta de lixo: O caminhão tem que sair do depósito e 
percorrer o seu trajeto com o mínimo de repetição de ruas 
 Internet: Os pontos são os computadores e as linhas que os 
ligam são as conexões de rede 
 Conexão de vôos aéreos 
Problema das três casas 
 É possível fornecer serviços de água, energia e 
telefone a três casas distintas sem que as redes 
(supostamente em um mesmo plano) se cruzem? 
água energia telefone 
Problema das três casas 
 Estamos interessados em entidades e nas relações 
entre elas 
 
 Ignorar detalhes não relevantes 
 Cor da casa 
 Área da casa 
 
 Quais são as entidades e relações no problema 
anterior? 
Problema das três casas 
 
 
 
 
 
 
 
 
 
 
 A teoria dos grafos mostra que não é possível prover os 3 
serviços às 3 casas sem existir cruzamento de tubulação! 
Casa 1 Casa 2 Casa 3 
água energia telefone 
? ? ? ? 
Grafos: Conceitos básicos 
 Um grafo G = (V, E) é um conjunto não-vazio V, cujos 
elementos são chamados vértices (vertex), e um 
conjunto E de arestas (edge) 
 
 Uma aresta a é um par não-ordenado (vi, vj), onde vi 
e vj são elementos de V 
 a é incidente a vi e vj 
 vi e vj são adjacentes ou vizinhos 
 
 Normalmente, utiliza-se uma representação gráfica de 
um grafo 
Grafos: Exemplo 
 V = {v1, v2, v3, v4, v5} 
 E = {a1, a2, a3, a4, a5, a6, a7, a8} 
 a1 = (v1,v2) 
 a2 = (v1,v3) 
 a3 = (v1,v3) 
 a4 = (v2,v3) 
 a5 = (v2,v5) 
 a6 = (v5,v5) 
 a7 = (v3,v5) 
 a8 = (v3,v4) 
 a2 é incidente a v1 e v3 
 v2 e v3 são adjacentes a v5 
 
 
V4 
V5 
V3 
V2 
V1 a8 
a1 
a3 
a4 
a7 
a5 
a6 
a2 
Graus de vértices 
 O grau de um vértice v (deg(v)) é o número de arestas 
que incidem em v 
 Vértice ímpar 
 Vértice par 
 Vértice isolado 
 
 Um grafo é regular (k-regular) se todos os seus vértices 
tem o mesmo grau (k) 
 
 Sequência de graus de um grafo consiste em escrever 
em ordem decrescente os graus de seus vértices 
Grafos k-regular: Exemplos 
Grafo 0-regular Grafo 1-regular Grafo 2-regular Grafo 3-regular 
Sequência de graus: Exemplos 
1 3 
2 
2 
2 
2 
1 
1 
1 
1 
1 2 2 2 2 3 
Sequencia de graus (3, 2, 2, 2, 2, 1, 1, 1) 
Teoremas 
 A soma dos graus dos vértices de um grafo é igual 
a duas vezes o número de arestas 
 
 
 
 
 
 Consequência: Em qualquer grafo existe um número 
par de vértices com grau ímpar 
Grafos: Terminologia 
 Laços 
 Aresta a6 
 Arestas paralelas ou 
multiarestas 
 Arestas a2 e a3 
 
 Grafo simples: grafo que não 
contém nenhum laço e nenhuma 
aresta paralela 
 Multigrafo: grafo que contém 
arestas paralelas 
 
V4 
V5 
V3 
V2 
V1 
a8 
a1 
a3 
a4 
a7 
a5 
a6 
a2 
Isomorfismo de grafos 
 Dois grafos são isomórficos: 
 São essencialmente iguais 
 Correspondência entre os vértices e arestas 
 
 Sejam G1=(V1,E1) e G2(V2,E2) 
G1 ≈ G2, se existir uma bijeção f: V1 V2: 
 Dois vértices v e w são adjacentes em G1 se e somente se 
f(v) e f(w) são adjacentes em G2 
Isomorfismo de grafos: Exemplo 1 
Isomorfismo de grafos: Exemplo 1 
Isomorfismo de grafos: Exemplo 2 
Subgrafos 
 G1 = (V1, E1) é subgrafo de G2 = (V2, E2) se e 
somente se: 
 V1 é subconjunto de V2 
 E1 é subconjunto de E2 
 
 Subgrafos podem ser obtidos através da remoção 
de arestas e vértices 
Subgrafos 
 
G2 = G1 \ {uz} 
G3 = G1 \ {v} 
Grafos completos e nulos 
 Grafo nulo é aquele em que E = O 
 
 Um grafo simples é completo se qualquer par de 
vértices distintos é adjacente 
Grafo completo de n vértices é dito Kn 
K3 
K4 
K5 
Grafos bipartidos 
 Grafo bipartido é aquele em que V pode ser 
dividido em dois subconjuntos disjuntos não vazios 
V1 e V2 
 Cada aresta conecta um vértice de V1 e um vértice de 
V2 
 
 Grafo bipartido completo: cada um dos elementos 
de V1 é adjacente a cada um dos elementos de V2 
Grafos bipartidos 
V1 = {u, v, w} 
V2 = {x, y, z} 
K3,3 
V1 = {a, b} 
V2 = {c, d, e} 
K2,3 
Exercício 1 
 Um grafo é k-regular se todo vértice de G possui 
grau k. Quais dos seguintes grafos são grafos 
regulares? 
Grafos completos 
Grafos bipartidos 
Grafos bipartidos completos 
Exercício 1: Solução 
 Grafos completos 
 Grafos bipartidos completos 
 
Exercício 2 
 Quantas arestas possui um grafo k-regular com n 
vértices? 
 
Exercício 2: Solução 
 A soma dos graus dos vértices de um grafo é igual 
a duas vezes o número de arestas 
 
 
 Em um grafo k-regular, todo vértice possui grau k 
 
 
 Daí: 
 
 
 
Exercício 3 
 Os grafos a seguir são isomorfos? Justifique. 
 
Exercício 3: Solução 
 Observe que os grafos são 3-regulares e todos 
possuem 6 vértices 
 Apesar disso, somente os grafos (a) e (c) são 
isomorfos 
 Análise: 
 f(1) = r 
 f(2) = m 
 f(3) = q 
 f(4) = n 
 f(5) = p 
 f(6) = o 
Grafo (a) Grafo (b) Grafo (c) 
1: 2, 4, 6 a: b, d, e r: m, n, o 
2: 1, 3, 5 b: a, c, f q: m, n, o 
3: 2, 4, 6 c: b, d, f p: m, n, o 
4: 1, 3, 5 d: a, c, e m:r, q, p 
5: 2, 4, 6 e: a, d, f n: r, q, p 
6: 1, 3, 5 f: b, c, e o: r, q, p 
Complemento de grafo 
 O complemento ou inverso de um grafo G = (V, E) 
é um grafo G nos mesmos vértices de G, tais que 
dois vértices de G são adjacentes se e somente se 
eles não são adjacentes em G 
 
 Para encontrar o complemento de um grafo G, 
basta preencher todas as arestas que faltavam em 
G para obter um grafo completo e, em seguida, 
remover todas as arestas de G 
_ 
_ 
Complemento de Grafo: Exemplo 
a 
f 
e 
c 
b 
d 
Grafo G 
a 
f 
e 
c 
b 
d 
Grafo G 
_ 
Exercício 4 
 Determine o complemento de um K6 
Exercício 4: Solução 
1 
4 
5 
2 
3 
6 
1 
4 
5 
2 
3 
6 
K6