2021-Q3-BCM0506 - AULA 02 - Introducao A Teoria Dos Grafos

BCM0506 - Comunicação e Redes
Introdução à Teoria dos

Clique para editar o estilo do subtítulo mestre
Grafos
Prof. Alexandre Donizeti Alves

As setes pontes de Königsberg
Cidade de Königsberg, Prússia (situada no leste europeu)
⚫ Ficava em ambos os lados do Rio Pregel (ou Prególia)
⚫ Tinha 2 ilhas centrais, com áreas conectadas por 7 pontes.
O rio divide a cidade em quatro áreas de terra
Foi feito um desafio a Leonhard Euler (1707-1783)
⚫ Como fazer para passar por toda a cidade de modo que
cada ponte seja cruzada uma única vez?
Modelagem do Problema
Euler demonstrou em 1735 que não existe nenhuma rota
que resolva o problema!
Para tal, o primeiro passo foi simplificar o problema
⚫ Caminhos dentro dos pedaços de terra não interessavam
⚫ O que interessa são apenas as conexões entre os
pedaços de terra, isto é, as pontes
Grafos
Chamamos a estrutura matemática resultante
de grafo
Os pontos são chamados de vértices e as

conexões de arestas
A forma de um grafo influi apenas na sua

visualização, mas matematicamente é irrelevante
Grafos
Esboço da Solução de Euler
Se uma pessoa entra num pedaço de terra e sai dele, é preciso
que no respectivo grafo cada vértice tenha um número par de
arestas
⚫ Com exceção dos vértices onde a caminhada começa e
termina
Olhando o grafo, por que é impossível encontrar um caminho que
cruze cada ponte uma única vez?
Exercício
Tente resolver o problema de dois modos:
1) Construindo uma nova ponte
2) Derrubando uma ponte existente
Resposta
Construindo uma nova ponte Derrubando uma das pontes

Caminho Euleriano
Euler demonstrou que, para que exista um caminho
que percorra todos os vértices passando por cada
aresta uma única vez:
⚫ É necessário que ou nenhum ou 2 dos vértices
tenham um número ímpar de arestas
Carl Hierholzer demonstrou posteriormente que
esta condição é também suficiente
E assim começou o desenvolvimento da teoria dos

grafos
Circuito Euleriano
Um Circuito Euleriano é um caminho

Euleriano onde tanto o vértice de origem
como o de destino é o mesmo
Neste caso, é preciso que todos os

vértices do grafo tenham um número par
de arestas
Exercício
Inclua um novo vértice no problema das 7 pontes de
modo a formar um Circuito Euleriano
Resposta
Inclua um novo vértice no problema das 7 pontes de
modo a formar um Circuito Euleriano
Resposta
1-5 5-2
2-1 1-2 2-4 4-5
5-3 3-1 1-4 4-3 ...

Definições
Podemos definir um grafo por
um par ordenado, G = (V, A), onde:
- V é um conjunto de vértices
- A é um conjunto de arestas
No exemplo ao lado, temos:
⚫ V = {1, 2, 3, 4, 5, 6}
⚫ A = { {1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6} }
Este grafo é simples (não possui laços (i.e., aresta que
conecta um vértice a ele mesmo) e há no máximo uma aresta
entre cada par de vértices) e não-direcionado (as arestas
não possuem uma direção definida).
Exemplo
Definições
Um caminho do vértice s ao vértice t é uma sequência
de vértices <s, u, v, … , t>, onde cada par de vértices
consecutivos é conectado por uma aresta
Dizemos que o caminho começa em s e termina em t

Definições
O comprimento de um caminho é o total de
arestas usadas no caminho
Definições
Pseudo-grafo Grafo direcionado Grafo ponderado

(ou multigrafo) (orientado)
Grafo Grafo
Grafo simples não- direcionado não- ponderado
Definições
Grafo não-direcionado
Arestas
Grafo direcionado
Arcos
Definições
Laço: uma aresta cuja duas extremidades
incidem em um mesmo vértice
Definições
Existem outras propriedades de grafos:
⚫ Ordem: Número de vértices
⚫ Tamanho: Número de arestas
⚫ Diâmetro: O maior dos menores caminhos entre cada

par de vértices
⚫ Encontre o caminho mínimo (menor) entre cada par de

vértices;
⚫ O maior comprimento de qualquer um desses caminhos

representa o diâmetro do grafo
Exemplo Caminhos entre os vértices
1-2: <1, 2>

1-3: <1, 3>
1-4: <1, 4>
1-5: <1, 2, 5>
1-6: <1, 3, 6>
1-7: <1, 2, 7>
2-3: <2, 3>
2-4: <2, 3, 4>
2-5: <2, 5>
2-6: <2, 3, 6>
2-7: <2, 7>
3-4: <3, 4>
3-5: <3, 5>
O grafo possui 7 vértices, 3-6: <3, 6>
neste caso, dizemos que 3-7: <3, 2, 7>
ele tem ordem 7. 4-5: <4, 3, 5>
4-6: <4, 3, 6>
O grafo possui 9 arestas, 4-7: <4, 3, 2, 7>
neste caso, dizemos que 5-6: <5, 3, 6>
ele tem tamanho 9. 5-7: <5, 2, 7>
Diâmetro = 3 6-7: <6, 3, 2, 7>
Exemplo
Comprimento do caminho Diâmetro = 3

em laranja (1 ao 6) = 5
Exercício
Qual a ordem, o tamanho e o diâmetro dos
grafos abaixo?
Definições
Um grafo é conexo se existe um caminho
entres quaisquer pares de vértices
Definições
A Conectividade dos Vértices é o número mínimo
de vértices cuja remoção desconecta o grafo
Conectividade dos Vértices = 1

Definições
A Conectividade das Arestas é o número mínimo
de arestas cuja remoção desconecta o grafo
Conectividade das Arestas = 1

Exercício
Qual a conectividade dos vértices e das

arestas nos grafos abaixo?
Grafos Planares
Grafos podem ser utilizados para representar objetos
Um grafo planar é aquele que pode ser desenhado em

um plano sem que nenhuma aresta se cruze
Exercício
É possível transformar o grafo do cubo em um
grafo planar? Se sim, redesenhe o grafo
Resposta
É possível transformar o grafo do cubo em um
grafo planar? Se sim, redesenhe o grafo
Sim, é possível
Jogo de Xadrez 3x3
Grafos podem ser utilizados para representar
diversos problemas:
Em um tabuleiro 3x3, você deseja

mapear todos os movimentos que
podem ser realizados por um bispo
que se move nas casas brancas
Jogo de Xadrez 3x3
O grafo à direita representa

os movimentos deste bispo
Exercício
Desenhe um grafo que represente todos os

movimentos da torre em um tabuleiro 3x3
Resposta
Resposta
Representação de Grafos
Mas como representar grafos em computadores?
As duas maneiras mais usadas são:
⚫ Lista de adjacência
⚫ Matriz de adjacência
Lista de Adjacência
Representamos um grafo por
um conjunto de listas, uma por nó X
Cada lista contém todos os
nós com os quais o nó X se conecta
Na figura ao lado, vemos a

representação de um grafo
Notem que cada aresta
é representada 2 vezes,
uma para cada nó que ela
conecta
Lista de Adjacência
Grafo direcionado
1: 4, 7
2: 1
3: 1, 6
4: 3
5: 2
6: 6
7: 2
Matriz de Adjacência
O grafo é representado por uma matriz,
na qual cada elemento (x, y) recebe o valor
1 se houver uma conexão entre os nós
x e y, e 0, caso contrário
Na figura ao lado, vemos a representação
de um grafo com a matriz de adjacência.
Notem que:
⚫ Para o grafo não direcionado,
a Matriz de Adjacência é simétrica
⚫ Se houver poucas arestas, a matriz
será esparsa (grande quantidade de elementos com
valor 0)
Grafo direcionado
Consulta existência de uma aresta/arco com um acesso à memória O(1)

n2 de espaço mesmo para grafos esparsos
Grafo de tamanho 33
Grafo de tamanho 33
Representação de Grafos
Podemos também representar grafos direcionados e
que contenham laços, como abaixo:
Neste caso, as representações contêm a aresta apenas

em uma direção, como a aresta de 3 para 5
Para o grafo direcionado, basta 1 bit para representar
cada aresta
Bibliografia
Capítulo 1 Capítulo 22
Atividade 1
Desenhe um grafo que represente todos os
movimentos do cavalo em um tabuleiro 3x3 e 5x5
Atividade 2
Pesquise no Google Maps pelo mapa de um

estado qualquer do Brasil
Selecione 10 cidades no mapa e crie um grafo

que represente suas conexões por estradas
Atribua pesos às arestas utilizando um critério

desejado (tempo estimado de viagem, distância
etc.)

2021-Q3-BCM0506 - AULA 02 - Introducao A Teoria Dos Grafos

Enviado por

Direitos autorais:

Formatos disponíveis

2021-Q3-BCM0506 - AULA 02 - Introducao A Teoria Dos Grafos

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

2021-Q3-BCM0506 - AULA 02 - Introducao A Teoria Dos Grafos

Enviado por

Direitos autorais:

Formatos disponíveis

BCM0506 - Comunicação e Redes

Introdução à Teoria dos

Prof. Alexandre Donizeti Alves

Os pontos são chamados de vértices e as

A forma de um grafo influi apenas na sua

Construindo uma nova ponte Derrubando uma das pontes

E assim começou o desenvolvimento da teoria dos

Um Circuito Euleriano é um caminho

Neste caso, é preciso que todos os

2-1 1-2 2-4 4-5

5-3 3-1 1-4 4-3 ...

Dizemos que o caminho começa em s e termina em t

Pseudo-grafo Grafo direcionado Grafo ponderado

⚫ Ordem: Número de vértices

⚫ Tamanho: Número de arestas

⚫ Diâmetro: O maior dos menores caminhos entre cada

⚫ Encontre o caminho mínimo (menor) entre cada par de

⚫ O maior comprimento de qualquer um desses caminhos

1-2: <1, 2>

Comprimento do caminho Diâmetro = 3

Conectividade dos Vértices = 1

Conectividade das Arestas = 1

Qual a conectividade dos vértices e das

Um grafo planar é aquele que pode ser desenhado em

Em um tabuleiro 3x3, você deseja

O grafo à direita representa

Desenhe um grafo que represente todos os

Na figura ao lado, vemos a

Consulta existência de uma aresta/arco com um acesso à memória O(1)

Neste caso, as representações contêm a aresta apenas

Pesquise no Google Maps pelo mapa de um

Selecione 10 cidades no mapa e crie um grafo

Atribua pesos às arestas utilizando um critério

Você também pode gostar