Grafos
29 pág.

Grafos


DisciplinaMatemática Discreta4.134 materiais80.439 seguidores
Pré-visualização2 páginas
Capítulo 5 - Grafos e Árvores 
GRAFOS 
Grafos 
\u2022 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. 
\u2022 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. 
\u2022 Um mapa como qualquer outra representação 
visual de dados é comumente chamada de 
gráfico. 
Grafos 
\u2022 Os gráficos de trataremos agora são chamados 
de grafos. 
\u2022 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. 
\u2022 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. 
\u2022 O conjunto de vértices (nós) do mapa das rotas é 
{Chicago, Nashville, Miami, Dallas, St. Louis, Albuquerque, 
Phoenix, Denver, San Francisco, Los Angeles}. 
\u2022 Existem 16 arestas (arcos); Phoenix-Albuquerque (neste 
caso, denotamos as arestas pelos seus extremos), 
Albuquerque-Dallas, etc 
Exemplo 
\u2022 No grafo a seguir, temos cinco nós e seis arcos. 
O arco \ud835\udc4e1 conecta os nós 1 e 2, \ud835\udc4e3 conecta os 
nós 2 e 2, e assim por diante. 
\u2022 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. 
\u2022 Sem uma figura, no entanto, precisamos de uma 
forma mais concisa de mostrar essa informação. 
Isso nos leva à segunda definição de grafos. 
\u2022 Definição (Formal): Um grafo é uma tripla 
ordenada (N, A, g), onde : 
\u2013 N = um conjunto não vazio de nós (vértices) 
\u2013 A = um conjunto de arcos (arestas) 
\u2013 g = é uma função que associa a cada arco a um par 
ordenado x-y de nós, chamados de extremidades de a 
\u2022 Para o grafo 
 
 
 
 
 
\u2022 a função g que associa arcos a suas extremidades 
é a seguinte: 
g(a1) = 1 - 2 g(a4) = 2 - 3 
g(a2) = 1 \u2013 2 g(a5) = 1 -3 
g(a3) = 2-2 g(a6) = 3 - 4 
\u2022 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. 
\u2022 Definição (Formal): Um grafo Direcionado é uma 
tripla ordenada (N, A, g), onde : 
\u2013 N = um conjunto não vazio de nós (vértices) 
\u2013 A = um conjunto de arcos (arestas) 
\u2013 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 
\u2022 Em um grafo direcionado, cada arco tem um 
sentido ou orientação 
\u2022 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. 
\u2022 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. 
\u2022 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 
\u2022 Antes de prosseguir, precisamos de alguma 
terminologia sobre grafos. 
\u2022 Essa terminologia não é totalmente padronizada 
em todos os livros sobre o assunto, mas vamos 
adotar o seguinte: 
\u2022 Dois nós em um grafo são ditos adjacentes se 
ambos são a extremidade de algum arco. 
\u2022 Um laço em um grafo é um arco com 
extremidades n \u2013 n para algum nó n. 
\u2022 Grafo sem arcos serão grafos que não possuem 
nenhum laço. 
Terminologias 
\u2022 Dois arcos com as mesmas extremidades são ditos 
arcos paralelos; 
\u2022 Um grafo simples é um grafo sem laços nem arcos 
paralelos. 
\u2022 Um nó isolado é um nó que não é adjacente a 
nenhum outro 
\u2022 O grau de um nó é o número de extremidades de 
arcos naquele nó. 
\u2022 Um grafo completo é um grafo no qual dois nós 
distintos quaisquer são adjacentes. 
\u2022 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 
\u2022 Um caminho do nó \ud835\udc5b0 para o nó \ud835\udc5b\ud835\udc58 é uma sequência 
de nós e arcos que encontramos entre o nó \ud835\udc5b0 e \ud835\udc5b\ud835\udc58. 
\u2022 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. 
\u2022 Um grafo é conexo se existe um caminho de qualquer 
nó para qualquer outro. 
\u2022 Um ciclo em um grafo é um caminho de algum nó \ud835\udc5b0 
para ele mesmo tal que nenhum arco aparece mais de 
uma vez, \ud835\udc5b0 é o único nó que aparece mais de uma 
vez e \ud835\udc5b0 aparece apenas nas extremidades. 
\u2022 Um grafo sem ciclos é dito acíclico 
Exercícios 
\u2022 O que é um grafo: 
\u2013 Direcionado 
\u2013 Rotulado 
\u2013 Com pesos 
\u2022 Desenhe um grafo qualquer que seja, direcionado, 
rotulado e com pesos. 
Exercícios 
\u2022 O que é um grafo: 
\u2013 Direcionado 
\u2013 Rotulado 
\u2013 Com pesos 
\u2022 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. \ud835\udc82\ud835\udfd4 
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. \ud835\udc82\ud835\udfd4 
d. Encontre duas arestas paralelas. \ud835\udc82\ud835\udfd1 e \ud835\udc82\ud835\udfd2 
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. \ud835\udc82\ud835\udfd4 
d. Encontre duas arestas paralelas. \ud835\udc82\ud835\udfd1 e \ud835\udc82\ud835\udfd2 
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. \ud835\udc82\ud835\udfd4 
d. Encontre duas arestas paralelas. \ud835\udc82\ud835\udfd1 e \ud835\udc82\ud835\udfd2 
e. Encontre o grau do vértice 3. 3 
f. Caminho de comprimento 5. 2, \ud835\udc82\ud835\udfcf, 1, \ud835\udc82\ud835\udfd0, 3, \ud835\udc82\ud835\udfd1, 4, \ud835\udc82\ud835\udfd2, 3, \ud835\udc82\ud835\udfd1, 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.