04 Passeio e Conectividade

Prévia do material em texto

Teoria dos Grafos
Rodrigo Machado com adaptações de Tadeu Zubaran
rma@inf.ufrgs.br tkzubaran@gmail.com
Instituto de Informática
Universidade Federal do Rio Grande do Sul
Porto Alegre, Brasil
http://www.inf.ufrgs.br
Passeio
Definição: Um passeio (walk) p entre nodos x e y, denotado p(x, y), é uma
sequência alternada
p(x, y) = v0, e1, v1, e2, v2 . . . en, vn
de vértices e arestas no qual
• x = v0 e y = vn
• há ao menos uma aresta
• toda aresta está situada entre dois nodos sobre os quais incide
Definição: o tamanho do passeio, denotado |p|, é a quantidade de arestas
presentes (contando repetições).
Nota: no caso de grafos simples o passeio é determinado unicamente pelos
vértices, portanto podemos escrever simplesmente p(v1, vn) = v1, v2, . . . vn.
Outros tipos de grafos (definidos a seguir) requerem que se nomeie
explicitamente as arestas.
2/11
Passeio: exemplo
Grafo exemplo (arestas nomeadas):
A 1 B
2
C
D
3
4 E 5 F
Exemplos de passeios:
• p1(A, B) = A, 1, B |p1| = 1
• p2(A, E) = A, 1, B, 2, E |p2| = 2
• p3(B, A) = B, 2, E, 4, D, 3, B, 2, E, 4, D, 3, B, 1, A |p3| = 7
3/11
Tipos de passeio
Definição: um passeio p(x, y) é
fechado quando x = y.
Definição: uma trilha (trail) é um
passeio sem arestas repetidas.
Definição: um caminho (path) é uma
trilha p(x, y) sem nodos repetidos (com
exceção de x e y, que podem ser iguais).
Definição: nomes especiais para alguns
passeios:
• circuito (circuit): trilha fechada
• ciclo (cycle): caminho fechado
• laço (loop): caminho fechado de
tamanho 1
Passeio
Trilha
EE
Passeio
Fechado
]]
Caminho
EE
Circuito
YY AA
Ciclo
ZZ DD
Laço
OO
4/11
Propriedades de passeios
Lema: de todo passeio p(x, y) podemos extrair um caminho c(x, y).
Demonstração: por indução no tamanho de p. Hipótese Indutiva: de todo passeio
p′(a, b) onde |p′| < |p| podemos extrair um caminho entre a e b.
1. base: p(x, y) = x, y. Neste caso, p é o próprio caminho.
2. passo de indução: p(x, y) = p′, y, sendo p′(x, v) um sub-passeio. Como
|p′| < |p|, pela H.I. temos que existe caminho c′(x, v). Duas possibilidades:
◦ y /∈ (c′ – {x}). Neste caso, o passeio c = c′, y não forma ciclos internos e
portanto é o caminho desejado.
◦ y ∈ (c′ – {x}). Então c′, y forma um ciclo interno. Portanto, há uma primeira
ocorrência de y dentro do caminho c′(x, v):
c′ = x, . . . , y, . . . , v
Tome como caminho desejado a subsequência x, . . . , y até a primeira
ocorrência de y em c′.
5/11
Conectividade de nós
Podemos estender a noção de adjacência (nodos ligados por arestas)
para conectividade (nodos ligados por rotas).
Definição: dois nós a e b estão conectados (denotado a! b) sss
• a = b, ou
• existe uma rota entre a e b
Definição: a relação de conectividade determina que dois vértices
estão relacionados sss estão conectados.
Lema: em grafos simples, a relação de conectividade é uma relação de
equivalência sobre o conjunto de vértices.
6/11
Distância entre nodos
Seja G = (V, E) um grafo simples.
Definição: a distância entre dois nós a e b, denotada d(a, b), é
definida por:
d : V × V→ N ∪ {∞}
d(a, b) =

0 se a = b
menor comprimento de
passeio entre a e b se (a 6= b)∧ (a! b)
∞ se a 6! b
7/11
Conectividade e distância: exemplo
Exemplo:
A B C
D E F
Conectividade:
• A e A são conectados (iguais).
• A e F são conectados (caminhos
ABDEF e ABEF).
• E e C não são conectados.
Distância:
• d(A, A) = 0
• d(A, B) = 1
• d(A, C) =∞
• d(B, F) = 2
8/11
Grafos conexos e desconexos
Definição: um grafo é conexo quando temos a! b para todos os
vértices a e b.
Definição: Um grafo é desconexo quando existem dois vértices a e b
tal que a 6! b.
Definição: H é um componente conexo de G sss
• H é subgrafo conexo de G
• H não está propriamente contido em nenhum outro subgrafo conexo
de G
Em outras palavras, um componente conexo é um subgrafo conexo
maximal.
9/11
Cliques
Definição: um clique de G é um subgrafo H ⊆ G tal que H ∼= Kn (para
algum n > 1).
Definição: um clique de G é maximal sss não está contido
propriamente em nenhum outro clique de G
Exercício: para o grafo abaixo, determine componentes conexos, cliques
e cliques maximais.
A B C
D E F
10/11
Conjuntos independentes
Definição: um conjunto independente de G = (V, E) é um
subconjunto de V onde nenhum par de vértices é adjacente.
Definição: um conjunto independente de G é maximal se não
pudermos adicionar nenhum vértice a ele sem introduzir uma aresta.
Exercício: para o grafo abaixo, determine os conjuntos independentes e
conjuntos independentes maximais.
A B C
D E F
11/11