03 intro grafos

Prévia do material em texto

Otimização em Redes
Allexandre Fortes S. Reis
Coordenadoria de Engenharia de Produção
Departamento de Engenharia Mecânica
Campus Santo Antônio
Universidade Federal de São João Del Rei
24 de agosto de 2017
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 1 / 38
Conteúdo
1
Introdução
2
Grafos
3
Terminologia
4
Isomorfismo
5
Grafos Especiais
6
Representação Computacional
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 2 / 38
Histórico da Teoria dos Grafos
Primórdios
Um grafo é uma estrutura de abstração muito útil na representação e
solução de problemas computacionais, por representarem relações de
interdependência entre elementos de um conjunto;
O primeiro registro de uso data de 1736, pelo matemático suiço Eüler;
O problema das pontes de Königsberg: Encontrar um caminho
circular usando cada uma das pontes sobre o rio Pregel exatamente
uma vez.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 3 / 38
O problema das pontes de Königsberg
Questão
Partindo de uma das margens, pode-se encontrar um percurso que passe
somente uma vez em cada ponte e retorne ao ponto de partida?
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 4 / 38
O problema das pontes de Königsberg: O Grafo
Questão
Partindo de uma das margens, pode-se encontrar um percurso que passe
somente uma vez em cada ponte e retorne ao ponto de partida?
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 5 / 38
Grafos
Representação concisa de inúmeros problemas reais e computacionais.
Definição Formal
G = (N,A)
N = {v1, v2, . . . , vn} é o conjunto de nós ou vértices do grafo, constituído
por n elementos
A = {(v1, v2), (v1, v3), . . . , (v2, v1), (v2, v3), . . . , (vn−1, vn)} é o conjunto de
arestas ou arcos (quando direcionados) do grafo, constituído por m
elementos
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 6 / 38
Grafos
Representação concisa de inúmeros problemas reais e computacionais.
Definição Formal
G = (N,A)
N = {v1, v2, . . . , vn} é o conjunto de nós ou vértices do grafo, constituído
por n elementos
A = {(v1, v2), (v1, v3), . . . , (v2, v1), (v2, v3), . . . , (vn−1, vn)} é o conjunto de
arestas ou arcos (quando direcionados) do grafo, constituído por m
elementos
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 6 / 38
Grafos
Representação concisa de inúmeros problemas reais e computacionais.
Definição Formal
G = (N,A)
N = {v1, v2, . . . , vn} é o conjunto de nós ou vértices do grafo, constituído
por n elementos
A = {(v1, v2), (v1, v3), . . . , (v2, v1), (v2, v3), . . . , (vn−1, vn)} é o conjunto de
arestas ou arcos (quando direcionados) do grafo, constituído por m
elementos
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 6 / 38
Grafos não-direcionados
Definição
i. conexões expressas por ares-
tas
ii. Se o vértice a está ligado a
b, a recíproca é verdadeira;
iii. Cada aresta é representada
por um conjunto {v1, v2},
indicando os dois vértices en-
volvidos.
v1
v2
v3
v4
v5
{v1, v3}
{v1, v2}
{v2, v4}
{v3, v4}
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 7 / 38
Grafos direcionados
Definição
i. Conexões expressas por arcos
ii. Se o vértice i está ligado a j,
a recíproca não é necessaria-
mente verdadeira;
iii. Cada arco é representada por
um par ordenado (v1, v2), in-
dicando os dois vértices en-
volvidos.
v1
v2
v3
v4
v5
(v1, v3)
(v1, v2)
(v2, v4)
(v3, v4)
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 8 / 38
Exemplos
Internet - World Wide Web
Abril de 2016, ≈ 5 bilhões de páginas (indexadas).
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 9 / 38
Exemplos
Deep Web
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 10 / 38
Exemplos
Redes sociais
(a) (b)
Figura: Redes sociais
Facebook ≈ 1,49 bilhão de usuários em agosto de 2015.
Google+ ≈ 500 milhões de usuários em junho de 2014
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 11 / 38
Exemplos
Rede de Metro
Rede de Metro de Barcelona, Espanha.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 12 / 38
Exemplos
Mapa rodoviário
Mapa rodoviário de Minas Gerais
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 13 / 38
Terminologia
Laço
Uma aresta cujas duas extremidades incidem em um mesmo vértice.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 14 / 38
Terminologia
Arestas paralelas
Mais de uma aresta associada ao mesmo par de vértices.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 15 / 38
Terminologia
Grafo simples
Grafo que não possui laços e nem arestas paralelas.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 16 / 38
Terminologia
Vértices adjacentes
Vértices que são os pontos finais de uma mesma aresta. A função Γ(i)
retorna o conjunto de vértices adjacentes ao vértice i.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 17 / 38
Terminologia
Arestas adjacentes
Arestas não paralelas que são adjacentes a um vértice comum.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 18 / 38
Terminologia
Grau de um vértice
O grau (gi) de um vértice i em um grafo não direcionado é igual o
número de arestas incidentes a i;
O grau de entrada (g−i ) de um vértice i em um grafo não direcionado
é igual o número de arestas que entram em i;
O grau de saída (g+i ) de um vértice i em um grafo não direcionado é
igual o número de arestas que saem de i;
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 19 / 38
Terminologia
Teorema do Aperto de Mãos
A soma dos graus de todos os n vértices de um GND G é duas vezes o
número de arestas m de G.
n∑
i=1
gi = 2m
Teorema
O número de vértices de grau ímpar em um GND é par.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 20 / 38
Terminologia
Teorema do Aperto de Mãos
A soma dos graus de todos os n vértices de um GND G é duas vezes o
número de arestas m de G.
n∑
i=1
gi = 2m
Teorema
O número de vértices de grau ímpar em um GND é par.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 20 / 38
Terminologia
Grafo Completo - Kn
Um grafo completo com n vértices, denominado Kn é um grafo simples
contendo exatamente uma aresta para cada par de vértices distintos.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 21 / 38
Terminologia
Grafo Regular
Grafo no qual todos os vértices possuem o mesmo grau.
*Qualquer grafo completo é regular.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 22 / 38
Terminologia
Grafo Nulo
Grafo sem arestas.
Grafo Pendente
Vértice i com gi = 1.
Vértice Isolado
Vértice i com gi = 1.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 23 / 38
Terminologia
Grafo Conexo
Para todo par de vértices i e j de G existe pelo menos um caminho entre
i e j.
Grafo Desconexo
Consiste de 2 ou mais grafos conexos, chamados de componentes.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 24 / 38
Isomorfismo
Definição
Dois grafos G e H são ditos isomorfos se existir uma correspondência
um-para-um entre seus vértices e entre suas arestas, de maneira que asrelações de incidência são preservadas.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 25 / 38
Isomorfismo
Condições necessárias, mas não suficientes
1. mesmo número de vértices;
2. mesmo número de arestas;
3. mesmo número de componentes
4. mesmo número de vértices de mesmo grau.
*Não existe algoritmo suficiente para provar que dois grafos são Isomorfos.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 26 / 38
Grafos Distintos
Número total é dado por:
2
n2−n
2
A potência indica o número possível de arestas desse grafo.
n: Número de vértices;
2 (base da potência): Cada possível aresta pode ser utilizada ou não (2 estados);
n2 − n: Cada vértice pode se ligar a todos os demais, menos a si próprio;
2 (divisor): Cada aresta incide em dois vértices, mas só deve ser contada uma vez.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 27 / 38
Grafo Complemento
Definição
Seja G = (N,A) um grafo simples dirigido ou não-dirigido, o complemento
de G, G, é um grafo formado da seguinte maneira:
Os vértices de G são todos os vértices de G; e
As arestas de G são exatamente as arestas que faltam em G para
formarmos um grafo completo.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 28 / 38
Grafo Bipartido
Definição
Um grafo é bipartido se o conjunto de vértices N pode ser particionado em
2 subconjuntos N1 e N2 tal que todas as arestas do grafo são incidentes a
um vértice de N1 e a um vértice de N2.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 29 / 38
Grafo Bipartido Completo
Definição
Um grafo bipartido é completo (K|N1|,|N2|) se cada vértice do subconjunto
N1 é adjacente a todos os vértices do subconjunto N2 e vice-versa.
Exemplo de grafos completos (1) e bipartidos completos (2 e 3).
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 30 / 38
Representação Computacional
Matriz de Adjacências
Matriz An×m, tal que:
aij =
{
1 ,se existe (vi, vj)
0 ,caso contrário
simétrica para grafos não direcionados;
n2 de espaço mesmo para grafos esparsos.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 31 / 38
Matriz de Adjacências - GND
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 32 / 38
Matriz de Adjacências - GD
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 33 / 38
Representação Computacional
Listas de Adjacências
Usa n listas, uma para cada vértice;
Lista de vi contém todos os vértices adjacentes a ele;
Ocupa menos memória;
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 34 / 38
Lista de Adjacências
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 35 / 38
Exercício
1) Dado os conjuntos de nós e arestas/arcos abaixo, represente o grafo de
cada um deles.
a. N = {1, . . . , 6}, Existe aresta {i, j} de todos para todos;
b. N = {1, . . . , 8}, Existe arco (i, j)∀i < j ∈ N , se i < 4 ;
2) Construa todos os grafos simples isomorfos com 3 vértices.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 36 / 38
Dúvidas? Valar joll	oris
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 37 / 38
Referências
(1) Notas de aula Professor Dr. Marco Antônio Carvalho (DECOM/UFOP);
(2) Notas de aula Professor Dr. Gustavo Peixoto (DECOM/UFOP);
(3) Goldbarg, Marco e Goldbarg, Elizabeth. Grafos: Conceitos, algoritmos e apli-
cações (2012);
(4) Taha, Hamdy. Pesquisa Operacional (2008);
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 24 de agosto de 2017 38 / 38
	Introdução
	Grafos
	Terminologia
	Isomorfismo
	Grafos Especiais
	Representação Computacional