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.
Teoria dos Grafos
Introdução – Isomorfismo
Dois grafos G e G' são isomorfos, ou seja,
apresentam as mesmas propriedades estruturais.
se eles
Definição: Dois grafos G e G' são isomorfos se existe uma função
bijetora
tal que
1
3
G
2
G’
Teoria dos Grafos
Introdução – Isomorfismo
Os grafos abaixo são isomorfos ?
Sim!
Teoria dos Grafos
Introdução – Isomorfismo
Os grafos abaixo são isomorfos ?
G
G’
Não! O grafo G é bipartido e o G’ não é .
Teoria dos Grafos
Introdução – Isomorfismo
Os grafos abaixo são isomorfos ?
Sim!
Teoria dos Grafos
Introdução – Isomorfismo
Os grafos abaixo são isomorfos ?
Não!
Teoria dos Grafos
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.
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
Teoria dos Grafos
Introdução – Isomorfismo
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.
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,
Teoria dos Grafos
Introdução – Isomorfismo
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 – Grafo de Petersen
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.
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
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.
Realizando o mapeamento
Re-arranjando linhas e colunas
Teoria dos Grafos
Trabalho - Definição
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