Introdução aos Grafos

Prévia do material em texto

Capítulo 5 - Grafos e Árvores 
GRAFOS 
Grafos 
• Todas essas informações sobre rotas podem ser 
expressas de forma verbal; por exemplo, existe 
uma rota direta entre Chicago e Nashville, mas 
não entre St. Louis e Nashville. 
• No entanto a forma verbal será muito longa e as 
vezes confusa, e não será capaz de passar as 
informações tão rapidamente e de forma tão 
clara quanto um mapa. 
• Um mapa como qualquer outra representação 
visual de dados é comumente chamada de 
gráfico. 
Grafos 
• Os gráficos de trataremos agora são chamados 
de grafos. 
• Usaremos duas definições de grafos: uma é 
baseada em uma representação visual como da 
figura a seguir e a outra é uma definição mais 
formal que não fala nada em representação 
visual. 
• Definição (Informal): Grafo é um conjunto não-
vazio de nós (vértices) e um conjunto de arcos 
(arestas) tais que cada arco conecta dois nós. 
• O conjunto de vértices (nós) do mapa das rotas é 
{Chicago, Nashville, Miami, Dallas, St. Louis, Albuquerque, 
Phoenix, Denver, San Francisco, Los Angeles}. 
• Existem 16 arestas (arcos); Phoenix-Albuquerque (neste 
caso, denotamos as arestas pelos seus extremos), 
Albuquerque-Dallas, etc 
Exemplo 
• No grafo a seguir, temos cinco nós e seis arcos. 
O arco 𝑎1 conecta os nós 1 e 2, 𝑎3 conecta os 
nós 2 e 2, e assim por diante. 
• A definição informal de um grafo funciona muito 
bem se tivermos a representação visual do grafo 
na nossa frente mostrando que arcos conectam 
que nós. 
• Sem uma figura, no entanto, precisamos de uma 
forma mais concisa de mostrar essa informação. 
Isso nos leva à segunda definição de grafos. 
• Definição (Formal): Um grafo é uma tripla 
ordenada (N, A, g), onde : 
– N = um conjunto não vazio de nós (vértices) 
– A = um conjunto de arcos (arestas) 
– g = é uma função que associa a cada arco a um par 
ordenado x-y de nós, chamados de extremidades de a 
• Para o grafo 
 
 
 
 
 
• a função g que associa arcos a suas extremidades 
é a seguinte: 
g(a1) = 1 - 2 g(a4) = 2 - 3 
g(a2) = 1 – 2 g(a5) = 1 -3 
g(a3) = 2-2 g(a6) = 3 - 4 
• Podemos querer que arcos de um grafo comecem 
em um nó e terminem em outro, caso em que 
teríamos o que chamamos de grafo direcionado. 
• Definição (Formal): Um grafo Direcionado é uma 
tripla ordenada (N, A, g), onde : 
– N = um conjunto não vazio de nós (vértices) 
– A = um conjunto de arcos (arestas) 
– g = é uma função que associa a cada arco a um par 
ordenado (x , y) de nós, onde x é o ponto inicial 
(extremidade inicial) e y é o ponto final 
(extreminadade final) de a 
• Em um grafo direcionado, cada arco tem um 
sentido ou orientação 
• Além de impor orientação aos arcos de um grafo, 
podemos querer modificar a definição básica de 
um grafo de outras maneiras. 
• Queremos, muitas vezes, que os nós de um grafo 
contenham informações identificadoras, ou 
rótulos, como nomes das cidades no mapa. Esse 
seria um grafo rotulado. 
• Podemos querer usar um grafo com pesos, onde 
cada arco tem um valor numérico, ou peso, 
associado. Por exemplo, distância, consumo de 
combustível, duração, etc 
Terminologias 
• Antes de prosseguir, precisamos de alguma 
terminologia sobre grafos. 
• Essa terminologia não é totalmente padronizada 
em todos os livros sobre o assunto, mas vamos 
adotar o seguinte: 
• Dois nós em um grafo são ditos adjacentes se 
ambos são a extremidade de algum arco. 
• Um laço em um grafo é um arco com 
extremidades n – n para algum nó n. 
• Grafo sem arcos serão grafos que não possuem 
nenhum laço. 
Terminologias 
• Dois arcos com as mesmas extremidades são ditos 
arcos paralelos; 
• Um grafo simples é um grafo sem laços nem arcos 
paralelos. 
• Um nó isolado é um nó que não é adjacente a 
nenhum outro 
• O grau de um nó é o número de extremidades de 
arcos naquele nó. 
• Um grafo completo é um grafo no qual dois nós 
distintos quaisquer são adjacentes. 
• Um subgrafo de um grafo, consiste em um conjunto 
de nós e um conjunto de arcos que são subconjuntos 
de um conjunto original de nós e arcos. 
Terminologias 
• Um caminho do nó 𝑛0 para o nó 𝑛𝑘 é uma sequência 
de nós e arcos que encontramos entre o nó 𝑛0 e 𝑛𝑘. 
• O comprimento de um caminho é o número de arcos 
que ele contém, se um arco for usado mais de uma 
vez, ele é contado cada vez que for usado. 
• Um grafo é conexo se existe um caminho de qualquer 
nó para qualquer outro. 
• Um ciclo em um grafo é um caminho de algum nó 𝑛0 
para ele mesmo tal que nenhum arco aparece mais de 
uma vez, 𝑛0 é o único nó que aparece mais de uma 
vez e 𝑛0 aparece apenas nas extremidades. 
• Um grafo sem ciclos é dito acíclico 
Exercícios 
• O que é um grafo: 
– Direcionado 
– Rotulado 
– Com pesos 
• Desenhe um grafo qualquer que seja, direcionado, 
rotulado e com pesos. 
Exercícios 
• O que é um grafo: 
– Direcionado 
– Rotulado 
– Com pesos 
• Desenhe um grafo qualquer que seja, direcionado, 
rotulado e com pesos. 
a. Encontre dois vértices que não sejam adjacentes. 
b. Encontre um vértice que seja adjacente a ele mesmo. 
c. Encontre um laço. 
d. Encontre duas arestas paralelas. 
e. Encontre o grau do vértice 3. 
f. Encontre um caminho de comprimento 5. 
g. Encontre um ciclo. 
h. Este grafo é completo? 
i. Este grafo é conexo? 
a. Encontre dois vértices que não sejam adjacentes. 2 e 3 
b. Encontre um vértice que seja adjacente a ele mesmo. 
c. Encontre um laço. 
d. Encontre duas arestas paralelas. 
e. Encontre o grau do vértice 3. 
f. Caminho de comprimento 5. 
g. Encontre um ciclo. 
h. Este grafo é completo? 
i. Este grafo é conexo? 
Respostas possíveis 
a. Encontre dois vértices que não sejam adjacentes. 2 e 3 
b. Encontre um vértice que seja adjacente a ele mesmo. 5 
c. Encontre um laço. 
d. Encontre duas arestas paralelas. 
e. Encontre o grau do vértice 3. 
f. Caminho de comprimento 5. 
g. Encontre um ciclo. 
h. Este grafo é completo? 
i. Este grafo é conexo? 
Respostas possíveis 
a. Encontre dois vértices que não sejam adjacentes. 2 e 3 
b. Encontre um vértice que seja adjacente a ele mesmo. 5 
c. Encontre um laço. 𝒂𝟔 
d. Encontre duas arestas paralelas. 
e. Encontre o grau do vértice 3. 
f. Caminho de comprimento 5. 
g. Encontre um ciclo. 
h. Este grafo é completo? 
i. Este grafo é conexo? 
Respostas possíveis 
a. Encontre dois vértices que não sejam adjacentes. 2 e 3 
b. Encontre um vértice que seja adjacente a ele mesmo. 5 
c. Encontre um laço. 𝒂𝟔 
d. Encontre duas arestas paralelas. 𝒂𝟑 e 𝒂𝟒 
e. Encontre o grau do vértice 3. 
f. Caminho de comprimento 5. 
g. Encontre um ciclo. 
h. Este grafo é completo? 
i. Este grafo é conexo? 
Respostas possíveis 
a. Encontre dois vértices que não sejam adjacentes. 2 e 3 
b. Encontre um vértice que seja adjacente a ele mesmo. 5 
c. Encontre um laço. 𝒂𝟔 
d. Encontre duas arestas paralelas. 𝒂𝟑 e 𝒂𝟒 
e. Encontre o grau do vértice 3. 3 
f. Caminho de comprimento 5. 
g. Encontre um ciclo. 
h. Este grafo é completo? 
i. Este grafo é conexo? 
Respostas possíveis 
a. Encontre dois vértices que não sejam adjacentes. 2 e 3 
b. Encontre um vértice que seja adjacente a ele mesmo. 5 
c. Encontre um laço. 𝒂𝟔 
d. Encontre duas arestas paralelas. 𝒂𝟑 e 𝒂𝟒 
e. Encontre o grau do vértice 3. 3 
f. Caminho de comprimento 5. 2, 𝒂𝟏, 1, 𝒂𝟐, 3, 𝒂𝟑, 4, 𝒂𝟒, 3, 𝒂𝟑, 4 
g. Encontre um ciclo. 
h. Este grafo é completo? 
i. Este grafo é conexo? 
Respostas possíveis 
a. Encontre dois vértices que não sejam adjacentes.2 e 3 
b. Encontre um vértice que seja adjacente a ele mesmo. 5 
c. Encontre um laço. 𝒂𝟔 
d. Encontre duas arestas paralelas. 𝒂𝟑 e 𝒂𝟒 
e. Encontre o grau do vértice 3. 3 
f. Caminho de comprimento 5. 2, 𝒂𝟏, 1, 𝒂𝟐, 3, 𝒂𝟑, 4, 𝒂𝟒, 3, 𝒂𝟑, 4 
g. Encontre um ciclo. 3, a3, 4, a4, 3 
h. Este grafo é completo? 
i. Este grafo é conexo? 
Respostas possíveis 
a. Encontre dois vértices que não sejam adjacentes. 2 e 3 
b. Encontre um vértice que seja adjacente a ele mesmo. 5 
c. Encontre um laço. 𝒂𝟔 
d. Encontre duas arestas paralelas. 𝒂𝟑 e 𝒂𝟒 
e. Encontre o grau do vértice 3. 3 
f. Caminho de comprimento 5. 2, 𝒂𝟏, 1, 𝒂𝟐, 3, 𝒂𝟑, 4, 𝒂𝟒, 3, 𝒂𝟑, 4 
g. Encontre um ciclo. 3, a3, 4, a4, 3 
h. Este grafo é completo? não 
i. Este grafo é conexo? 
Respostas possíveis 
a. Encontre dois vértices que não sejam adjacentes. 2 e 3 
b. Encontre um vértice que seja adjacente a ele mesmo. 5 
c. Encontre um laço. 𝒂𝟔 
d. Encontre duas arestas paralelas. 𝒂𝟑 e 𝒂𝟒 
e. Encontre o grau do vértice 3. 3 
f. Caminho de comprimento 5. 2, 𝒂𝟏, 1, 𝒂𝟐, 3, 𝒂𝟑, 4, 𝒂𝟒, 3, 𝒂𝟑, 4 
g. Encontre um ciclo. 3, a3, 4, a4, 3 
h. Este grafo é completo? não 
i. Este grafo é conexo? sim 
Respostas possíveis 
• Esboce um desenho para cada um dos grafos 
indicados a seguir: 
– Um grafo simples com três nós, cada um de grau 2; 
– Um grafo com 4 nós e ciclos de comprimento 1, 2, 3, 
4 
– Um grafo não completo com 4 nós, cada um de grau 
4 
• Use o grafo direcionado da figura para responder 
Quais nós são acessíveis a partir do nó 3? 
 
Qual o comprimento do caminho mais curto 
do nó 3 para o nó 6? 
 
Qual o caminho de comprimento 8 do nó 1 
para o nó 6? Obs: para este exemplo, listar 
apenas os nós 
• Esboce um desenho para cada um dos grafos 
indicados a seguir: 
– Um grafo simples com três nós, cada um de grau 2; 
– Um grafo com 4 nós e ciclos de comprimento 1, 2, 3, 
4 
– Um grafo não completo com 4 nós, cada um de grau 
4 
• Use o grafo direcionado da figura para responder 
Quais nós são acessíveis a partir do nó 3? 4, 5, 6 
 
Qual o comprimento do caminho mais curto do nó 3 para o nó 
6? 2 
 
Qual o caminho de comprimento 8 do nó 1 para o nó 6? Obs: 
para este exemplo, listar apenas os nós. 1-2-1-2-2-1-4-5-6 
• Use o grafo direcionado da figura para responder 
Quais nós são acessíveis a partir do nó 3? 4, 5, 6 
 
Qual o comprimento do caminho mais curto do nó 3 para o nó 
6? 2 
 
Qual o caminho de comprimento 8 do nó 1 para o nó 6? Obs: 
para este exemplo, listar apenas os nós. 1-2-1-2-2-1-4-5-6 
• Use o grafo direcionado da figura para responder 
Quais nós são acessíveis a partir do nó 3? 4, 5, 6 
 
Qual o comprimento do caminho mais curto do nó 3 para o nó 
6? 2 
 
Qual o caminho de comprimento 8 do nó 1 para o nó 6? Obs: 
para este exemplo, listar apenas os nós. 1-2-1-2-2-1-4-5-6