Teoria dos Grafos - Subgrafos, Caminhos e Circuitos

Prévia do material em texto

subgrafos.doc – Teoria dos Grafos – Prof. Maria do Socorro Rangel – DCCE/UNESP - 23/08/07 - 1 / 3 
 
4 - Caminhos e Circuitos 
 
4.1 - Subgrafos 
 
Definição.1 - Um grafo h (V’, A’) é um subgrafo de um grafo G(V,A) se todos os vértices e 
todas as arestas de h pertencem a G ( AAVV ⊆⊆ ',' ), e cada aresta de h possui as mesmas 
extremidades que em G. Denotamos um subgrafo através da mesma notação usada para 
conjuntos, isto é Gh ⊂ . 
 
Exemplo 4.1 - Dado o grafo: 
 
Fig1: G 
 
 
 
 
 
 
os seguintes grafos são subgrafos de G. 
G1 G2 
 
 
 
 
 
 
 
 
As seguintes observações podem ser feitas: 
 
1 - Todo grafo é um subgrafo de si próprio. 
2 - Um subgrafo de um subgrafo de G também é um subgrafo de G. 
3 - Um vértice de G é um subgrafo de G 
4 - Uma aresta, juntamente com as suas extremidades é um subgrafo de G. 
 
 
Definição 4.2 - Dois subgrafos, g1 e g2 são aresta-disjuntos de um grafo G se eles não possuem 
arestas em comum. Se g1 e g2 não possuírem vértices em comum, os dois subgrafos são 
chamados de vértice-disjuntos. 
 
Exemplo 2 
G3 G4 G5 
 
 
 
 
 
Aresta disjuntos: 
Vértice-disjuntos:
 1 
 a b 
 2 3 4 5 6 
 c 7 d 
 9 
 8 10 
 
 e 11 f 
 
 1 
 a b 
 3 4 5 6 
 d 
 9 
 10 
 
 e 11 f 
 
 
 a b 
 2 5 
 c d 
 
 8 
 
 e 
 a 
 
c d
 
 
 e 
 e 
b 
 
c 
 
 
f 
 
a 
 d 
 
 
e 
subgrafos.doc – Teoria dos Grafos – Prof. Maria do Socorro Rangel – DCCE/UNESP - 23/08/07 - 2 / 3 
 
4.2 - Trajetos, caminhos e circuitos 
 
 Vamos discutir aqui alguns tipos especiais de subgrafos de um grafo G. Quando 
discutimos o problema das Pontes de konigsbergh, estávamos interessados em determinar um 
trajeto na cidade que passasse pôr todas as pontes apenas uma vez. Se estudarmos este problema 
através de grafos, vamos precisar de alguns conceitos para acharmos a solução do problema. 
 
Definição 4.3 - Trajeto - Dado um grafo G(V,A), um trajeto em G consiste de uma seqüência 
finita alternada de vértices e arestas, começando e terminando pôr vértices, tal que cada aresta 
aparece apenas uma vez e é incidente ao vértice que a precede e que a sucede. 
 
Nos exemplos abaixo considere o grafo G da fig 1. 
 
Exemplo 3 
(trajeto onde há repetição de vértices) (trajeto onde não há repetição de vértices) 
 
 
 
 
Definição 4.4 - Caminho - Dado um grafo G(V,A), um caminho em G consiste de uma 
seqüência finita alternada de vértices e arestas, começando e terminando pôr vértices, tal que 
cada aresta é incidente ao vértice que a precede e que a sucede e não há repetição de vértices. Em 
outras palavras, um caminho é um trajeto onde não repetição de vértices. 
 
Exemplo 4.4 
(caminhos) 
 
obs: Em grafos simples podemos mencionar um caminho ou trajeto listando apenas os vértices 
(ou arestas), sem menção explícita ás arestas (ou vértices). 
 
Questão 1: Qual é o grau dos vértices pertencentes a um caminho? 
Os vértices finais de um caminho possuem grau 1 e os demais, vértices intermediários, possuem 
grau 2. 
 
Questão 2: Qual é o comprimento de um caminho/trajeto em grafos não valorados? E em grafos 
valorados? 
 Para grafos não valorados o comprimento é igual ao número de arestas incluídas no caminho. 
 
Definição 4.5 - Trajeto fechado - É um trajeto no qual o vértice inicial e o final são iguais. 
 
Definição 4.6 - Ciclo ( circuito ou caminho fechado) - É um trajeto fechado no qual nenhum 
vértice (com exceção do inicial e do final ) aparece mais de uma vez. 
 
Exemplo 4.5 : { c,a,d.e,c} 
Contra exemplo: { a,b,d,a,e,c,a} 
Observe neste contra-exemplo que o vértice inicial é: 
o vértice final é: 
qual é o 4º vértice desta seqüência? Esta seqüência não é um ciclo pois o 4º vértice 
aparece mais de vez. 
 
Estes conceitos podem ser resumidos através do seguinte diagrama: 
subgrafos.doc – Teoria dos Grafos – Prof. Maria do Socorro Rangel – DCCE/UNESP - 23/08/07 - 3 / 3 
 
 
 
 
 
 
 
 
 
 
 
Exercícios 
 
1)Considere o grafo: 
 
a) Liste todos os trajetos existentes entre os vértices 5 e 6. 
a) Liste todos os caminhos existentes entre os vértices 5 e 6. 
b) Quais dos trajetos obtidos no item a) são caminhos? 
c) De o comprimento de cada um dos caminhos do item b. 
 
 
2) Seja a, b e c três vértices distintos em um grafo. Existe um caminho entre a e b e também 
existe um caminho entre b e c. Mostre que existe um caminho entre a e c. 
 
Subgrafo 
trajeto 
caminho circuito 
 
 1 
 i b f 
 c a 
6 2 4 5 
 
 j d e g 
 
 3 
h