Teoria dos Grafos - Introdução e Isomorfismo

Prévia do material em texto

Teoria dos Grafos
Edson Prestes
Teoria dos Grafos
Introdução – Representação
Mostre que todo passeio de u até v contém um caminho de u até v.
Considere um passeio de comprimento l de u até v. 
Se l = 0 então temos um passeio sem nenhuma aresta. Isto denota que o 
caminho entre u e v também tem comprimento igual a 0. 
Se l > 0, temos que considerar o seguinte. Se o passeio de u a v não possuir 
nenhum vértice que tenha sido visitado duas vezes, então ele corresponde a 
um caminho entre u e v. 
Teoria dos Grafos
Introdução – Representação
Se existe um vértice w que tenha sido visitado mais que uma vez, podemos 
remover as arestas e vértices entre as duas aparições de w. 
Se existirem mais vértices que tenham sido visitados mais que uma vez o 
processo é repetido. Isto produz um passeio mais curto onde cada vértice é 
visitado uma única vez. Logo existe nesta situação um caminho entre u e v.
Teoria dos Grafos
Introdução – Representação
Mostre que todo grafo com n vértices e k arestas, onde n > k, tem no 
mínimo n-k componentes
Um grafo com n vértices com nenhuma aresta tem n componentes. Cada 
aresta reduz a quantidade de componentes em 1 unidade. Então, quando k 
arestas tiverem sido adicionadas ao grafo, o número de componentes será no 
mínimo n-k.
Teoria dos Grafos
Introdução – Representação
Mostre que um grafo G com n vértices e c componentes, tem uma 
quantidade de arestas k que satisfaz a seguinte desigualdade
O limite inferior foi mostrado anteriormente. 
O limite superior é definido da seguinte maneira. Considere a situação extrema, 
onde temos (c-1) componentes correspondendo a (c-1) vértices de grau igual a 
0; e n-c+1 vértices constituindo um grafo completamente conexo. 
Este grafo irá possuir
Teoria dos Grafos
Introdução – Representação
Mostre que todo grafo simples com dois ou mais vértices tem pelo menos 
dois vértices de mesmo grau
Considere um grafo com n vértice. Se o grafo é simples então o grau de cada 
vértice deve variar de 0 a n-1. Se existir um vértice de grau 0 então não existe 
um vértice de grau n-1, e vice versa. 
Logo, teremos n-1 valores de graus a associar a n vértices. Usando o 
principio de Dirichlet, podemos considerar n caixas rotuladas com os valores 
de graus de 0 a n-1. Porém sabendo que apenas n-1 caixas serão 
preenchidas. 
Distribuindo n-1 vértices em cada uma das n-1 caixas de acordo com seu 
respectivo grau fará com que cada uma das caixas válidas seja preenchida. 
O n-ésimo vértice será associado a uma caixa que já possui um elemento. 
Logo, a caixa escolhida terá 2 vértices, indicando que existem dois vértices 
com mesmo grau.
Dois grafos G e G' são isomorfos, ou seja, se eles 
apresentam as mesmas propriedades estruturais.
Teoria dos Grafos
Definição: Dois grafos G e G' são isomorfos se existe uma função 
bijetora 
tal que
G G’
1 3 2
Introdução – Isomorfismo
Os grafos abaixo são isomorfos ?
Teoria dos Grafos
Sim!
Introdução – Isomorfismo
Os grafos abaixo são isomorfos ?
Teoria dos Grafos
Não! O grafo G é bipartido e o G’ não é .
G G’
Introdução – Isomorfismo
Os grafos abaixo são isomorfos ?
Teoria dos Grafos
Sim!
Introdução – Isomorfismo
Os grafos abaixo são isomorfos ?
Teoria dos Grafos
Não!
Introdução – Isomorfismo
A relação de isomorfismo é uma relação de equivalência sobre o 
conjunto de grafos simples. 
Propriedade reflexiva: uma permutação da identidade dos vértices de 
G é um isomorfismo de G para si próprio.
Teoria dos Grafos
Introdução – Isomorfismo
Propriedade simétrica: Se é uma função que 
define o isomorfismo entre G e G', então f -1 é a função que define o 
isomorfismo entre G' e G. 
Logo, 
temos que
Propriedade de Transitividade: Suponha que as funções 
 e definam a relação de 
isomorfismo entre os grafos G e H; e H e M, respectivamente. 
Teoria dos Grafos
Introdução – Isomorfismo
Sabemos que e que 
Como f define uma relação de isomorfismo, se , então 
existe uma aresta tal que f(u)=x e f(v)=y. 
Logo, .Portanto, a 
composicão lof define a relação de isomorfismo entre G e M, ou seja, 
Uma relação de equivalência divide um conjunto de grafos em classes de 
equivalência, onde dois grafos pertencem ao mesmo conjunto sse eles são 
isomorfos. 
Uma classe isomórfica de grafos é uma classe de equivalência de grafos 
regida por uma relação de isomorfismo. 
Um exemplo de classe isomórfica é a classe chamada grafo de petersen.
Teoria dos Grafos
Introdução – Isomorfismo
Um grafo de Petersen é um grafo simples não orientado gerado usando o 
seguinte conjunto S={1,2,3,4,5}. Seus vértices estão associados a 
subconjuntos de dois elementos de S. 
Os vértices formados a partir destes subconjuntos serão conectados por 
uma aresta se seus subconjuntos correspondentes forem disjuntos.
Teoria dos Grafos
Introdução – Grafo de Petersen
O grafo abaixo é isomórfico ao grafo de Petersen ?
Teoria dos Grafos
Introdução – Grafo de Petersen
Mostre que dois vértices não adjacentes em um grafo de Petersen têm 
exatamente 1 vizinho em comum.
Teoria dos Grafos
Introdução – Grafo de Petersen
Dois vértices A e B não adjacentes no grafo de Petersen são subconjuntos de 
2 elementos que compartilham um único elemento. 
Um vértice adjacente tanto à A quanto à B tem que ser um subconjunto 
disjunto dos dois subconjuntos associados à A e à B. 
Como estes dois vértices são escolhidos a partir do conjunto {1,2,3,4,5}, a 
quantidade de elementos resultante da união dos subconjuntos associados a 
eles é igual a 3. 
Então existe exatamente uma única combinação de 2 elementos para o 
terceiro vértice de forma que ele seja adjacente tanto ao vértice A quanto ao 
vértice B.
Teoria dos Grafos
Introdução – Automorfismo
Um automorfismo de um grafo G é um isomorfismo de G para si próprio. 
Os automorfismos de G são as permutações de V(G) que podem ser 
aplicadas a ambas as linhas e colunas da matriz de adjacência sem mudar a 
adjacência entre os vértices de G. 
Considere um grafo G representado pela matriz de adjacência abaixo
Teoria dos Grafos
Introdução – Automorfismo
G possui 2 automorfismos: ele próprio e a permutação que mapeia o 
vértice 1 para o vértice 4 e o vértice 2 para o vértice 3. 
Realizando o mapeamento
Re-arranjando linhas e colunas
Teoria dos Grafos
Introdução – Automorfismo
Realizando o mapeamento
Re-arranjando linhas e colunas
Apenas trocar a identidade do vértice 1 pela identidade do 4 não é um 
automorfismo de G. 
Embora este grafo seja isomórfico ao grafo G, ele não é um automorfismo 
de G.
Problema 1 
Desenvolver um algoritmo que receba como entrada um grafo G e produza 
como saída α(G) e ω(G), assim como os conjuntos de vértices que deram 
origem a estas medidas. 
A descrição do grafo deve ser feita através de arquivo texto. 
Entrega 30/11
Teoria dos Grafos
Trabalho - Definição
Problema 2 
Dado um mapa composto por obstáculos, uma posição inicial e uma posição 
final, construa uma RRT que encontre um caminho livre de obstáculos entre a 
posição final e a posição inicial. 1 ponto extra se a implementação funcionar no 
simulador do robô. 
Links uteis 
http://msl.cs.uiuc.edu/rrt/about.html 
http://msl.cs.uiuc.edu/~lavalle/papers/Lav98c.pdf 
http://www.golems.org/papers/AkgunIROS11-sampling.pdf 
http://planning.cs.uiuc.edu(temos o livro na biblioteca :) 
Informações úteis sobre o simulador 
http://www.inf.ufrgs.br/~prestes/Courses/Robotics/instrucoes.rtf 
Falar com o Edson ou com membros do grupo de Edson. 
Entrega 30/11
Teoria dos Grafos
Trabalho - Definição