1
Análise de Decisão Aplicada a Gerência
Empresarial – UVA
Grafos - V
Bibliografia: GOMES, Carlos – Apendice C
Prof. Felipe Figueira
www.felipefigueira.com
[email protected]
2
Conceitos Básicos
• A teoria dos grafos é um ramo da matemática que estuda as
relações entre os objetos de um determinado conjunto.
• G(V,A) onde V é um conjunto não vazio de objetos denominados
vértices e A é um conjunto de pares não ordenados de V,
chamado arestas.
• Se as arestas têm uma direção associada (indicada por uma seta
na representação gráfica) temos um grafo direcionado, grafo
orientado ou digrafo.
• Um grafo com um único vértice e sem arestas
é conhecido como o grafo trivial ou "o ponto".
3
Conceitos Básicos
Geometricamente, um grafo é um conjunto de pontos (vértices
ou nós) conectados por linhas (arestas).
G = (V, A)
vértices
V = {v1, v2, ..., vn}
A = {a1, a2, ..., am}
arestas
|V | = n
|A| = m
4
Conceitos Básicos
• Um grafo direcionado (digrafo ou quiver) consiste de:
- um conjunto V de vértices,
- um conjunto A de arestas e
- mapas s, t : A → V, onde s(a) é a fonte e t(a) é o alvo da
aresta direcionada e.
• Um grafo não direcionado (ou simplesmente grafo) é dado
por:
- um conjunto V de vértices,
- um conjunto A de arestas e
- uma função w : A → P(V) que associa a cada aresta um
subconjunto de dois ou de um elemento de V, interpretado
como os pontos terminais da aresta.
5
Problema do caixeiro viajante
• O problema do caixeiro-viajante consiste na procura de um
circuito que possua a menor distância, começando em
qualquer cidade, entre várias, visitando cada cidade
precisamente uma vez e regressando à cidade inicial.
6
Conceitos Básicos
• Uma aresta conecta dois vértices; esses dois vértices são ditos
como incidentes à aresta.
• A valência (grau) de um vértice é o número de arestas
incidentes a ele, com loops contados duas vezes.
• A ordem de um grafo é dada pela cardinalidade do conjunto
de arestas.
• Cadeia (percurso) é a sequência de
arestas adjacentes que ligam dois vértices.
7
Conceitos Básicos
• Dois vértices são considerados adjacentes ou vizinhos se existe
uma aresta entre eles.
• Grafo é conexo quando se consegue estabelecer um caminho de
qualquer vértice para qualquer outro vértice de um grafo.
• Grafo simples é um grafo não direcionado, sem laços e que
existe no máximo uma aresta entre quaisquer dois vértices (sem
arestas paralelas).
• No grafo de exemplo, (1, 2, 5, 1, 2, 3)
é um caminho com comprimento 5,
e (5, 2, 1) de comprimento 2.
8
Conceitos Básicos
• Grau de saída - o número de arestas saindo de um vértice.
Grau de entrada - o número de arestas entrando em um
vértice. O grau de um vértice é igual à soma dos graus de
saída e de entrada.
• Grafo completo é o grafo simples em que, para cada vértice
do grafo, existe uma aresta conectando este vértice a cada um
dos demais. Ou seja, todos os vértices do grafo possuem
mesmo grau.
• Kn: grafo completo com n nós
número de arestas: n(n-1)/2.
9
Conceitos Básicos
• Grafo nulo é o grafo cujo conjunto de vértices é vazio.
• Grafo vazio é o grafo cujo conjunto de arestas é vazio.
• Grafo trivial é o grafo que possui apenas um vértice e
nenhuma aresta.
• Grafo regular é um grafo em que todos os vértices tem o
mesmo grau.
10
Conceitos Básicos
• Multigrafo é um grafo que permite múltiplas arestas ligando os
mesmos vértices (arestas paralelas).
• Laço (loop) é uma aresta que conecta um vértice a ele mesmo
• Pseudografo é um grafo que contém arestas paralelas e laços.
• Ciclo (ou circuito) é um caminho que começa e acaba com o
mesmo vértice. Ciclos de comprimento 1 são laços. No grafo de
exemplo, (1, 2, 3, 4, 5, 2, 1) é um ciclo de comprimento 6.
11
Conceitos Básicos
• Um ciclo simples é um ciclo que tem um comprimento pelo
menos de 3 e no qual o vértice inicial só aparece mais uma
vez, como vértice final, e os outros vértices aparecem só uma
vez.
• Um grafo chama-se acíclico se não contém ciclos simples.
Conceitos Básicos
• Caminho de a v i : v j
Sequência P de vértices e arestas alternados, tais que cada aresta é
incidente ao nó (vértice) anterior e ao nó posterior.
vi  v jP é um ciclo ou circuito.
• Caminho simples: cada vértice aparece exatamente uma vez.
• Comprimento de um caminho: número de arestas.
• Caminhos disjuntos em vértices/arestas: não têm vértices/arestas em
comum.
12
Conceitos Básicos
• Árvore: grafo conexo sem circuitos.
• Floresta: grafo cujas componentes conexas são árvores.
Um caminho é uma árvore?
Sim!
13
14
Árvores de voos
15
Menor escala de Árvores de voos
16
Caminho Euleriano
• É um caminho em um grafo que visita cada aresta apenas uma vez.
Com caso especial o Caminho Euleriano começa e termina no
mesmo vértice.
• Precisam ter grau par.
• Um grafo G conexo possui caminho Euleriano se e somente se ele
tem no máximo dois vértices de grau ímpar,
que são justamente a entrada e saída.
17
Pontes de Königsberg - Kaliningrado, na Rússia
• Possibilidade de atravessar todas as pontes sem repetir nenhuma.
• Transformou os caminhos em retas e suas intersecções em
pontos, criando possivelmente o primeiro grafo da história.
• Percebeu que só seria possível
atravessar o caminho inteiro passando
uma única vez em cada ponte se
houvesse exatamente zero ou dois
pontos de onde saísse um número
ímpar de caminhos.
18
Caminho Hamiltoniano
• Caminho Hamiltoniano ou caminho rastreável é
um caminho que visita cada vértice exatamente uma vez.
• Um grafo é Hamilton-conectado se para cada par de
vértices existe um caminho Hamiltoniano entre os dois
vértices.
Conceitos Básicos
•
Matriz de adjacência:
Uma linha para cada nó
Uma coluna para cada nó
aij = 1  (i , j )  A
aij = 0  (i , j )  A
1
a12
2
a24
a13
4
a34
a23
Ann
3
0
0

0

0
1
0
0
0
1
1
0
0
0
1
1

0
19
Conceitos Básicos
•
Matriz de incidência nó-arco:
Uma linha para cada nó
Uma coluna para cada aresta
G  (V , A)
|V | n
| A | m
1
a1
a2
4
a5
a  (i , j )  A
2
a4
a
a3
3
Am n
 0
i   1
 0
 
j   1
 0 
0
0
0
 1  1



1
0

1

1
0


 0 1 1
0  1


0
0  1  1
 0
20
Conceitos Básicos
•
Matriz de incidência nó-arco:
Uma linha para cada nó
Uma coluna para cada aresta
G  (V , A)
|V | n
| A | m
1
a1
a2
4
a5
a  (i , j )  A
2
a4
a
a3
3
Am n
 0
i   1
 0
 
j   1
 0 
0
0
0
 1  1



1
0

1

1
0


 0 1 1
0  1


0
0  1  1
 0
21
Charles Chaplin
“A vida é uma peça de teatro que não permite ensaios. Por isso,
cante, chore, dance, ria e viva intensamente, antes que a cortina
se feche e a peça termine sem aplausos”.
22