Engenharia de
CONTROLE e
AUTOMAÇÃO
Grafos
Aula 01
DPEE 1038 – Estrutura de Dados para Automação
Curso de Engenharia de Controle e Automação
Universidade Federal de Santa Maria
Prof. Rafael Concatto Beltrame
[email protected]
1/5
Sumário
•
Introdução
– Aplicações
•
Definições
Prof. Rafael Concatto Beltrame
2
1/5
Introdução
•
Teoria de grafos
– Estudo de objetos combinatórios (grafos)
– Modelo adequado para problemas em
• Matemática, informática, engenharia
•
Euler (1736)  Solução do problema das pontes de Konigsberg
Prof. Rafael Concatto Beltrame
3
1/5
Introdução
•
É possível andar por toda a cidade de tal modo que cada ponte seja atravessada exatamente uma vez?
– Após aplicar a teoria de grafos, Euler obteve a resposta: Não!
•
Problemas que envolvem grafos
– Dado um mapa, determinar a maneira mais rápida e de menor custo de se deslocar da cidade A para a cidade B
– Modelar uma rede de computadores
– Modelar uma rede de dispositivos industriais (sensores, atuadores, controladores lógico programáveis, etc.)
– Modelar o relacionamento das páginas web
– Robótica
Prof. Rafael Concatto Beltrame
4
1/5
Introdução
•
Exemplos
– Aplicação em robótica
– Planejar o movimento do robô  Grafo de pontos de movimento
Prof. Rafael Concatto Beltrame
5
1/5
Introdução
•
Exemplos
– Circuitos elétricos
Prof. Rafael Concatto Beltrame
6
1/5
Introdução
•
Exemplos
– Roteamento de PCIs
(placas de circuito impresso)
Prof. Rafael Concatto Beltrame
7
1/5
Definições
•
Um grafo consiste de um conjunto de nós (vértices) e um conjunto de arcos (arestas)
– Cada arco é especificado por um par de nós
– Sequência de nós: { A, B, C, D, F }
– Conjunto de arcos: { (A,B), (A,D), (A,C), (C,F), (A,A) }
B
D
A
C
F
Prof. Rafael Concatto Beltrame
8
1/5
Definições
•
Se os pares de nós que formam os arcos forem pares ordenados  grafo orientado (dígrafo)
– As setas entre os nós representam os arcos
– Conjunto de arcos: { <A,B>, <A,D>, <A,C>, <F,C>, <A,A> }
B
A
D
A
C
C
B
D
F
Prof. Rafael Concatto Beltrame
9
1/5
Definições
•
Grau de um nó
– Número de arcos incidentes no nó
•
Grau de entrada de um nó n
– Número de arcos convergentes à n
•
Grau de saída de um nó n
– Número de arcos divergentes de n
A
C
B
• Grau de A = 3
• Grau de entrada de A = 1
• Grau de saída de A = 2
D
Prof. Rafael Concatto Beltrame
10
1/5
Definições
•
Um nó n será adjacente de um nó m se
– Existir um arco de m até n
k
– m  predecessor de n
– n  sucessor de m
•
j
m
n
Grafo ponderado (rede)
– Tem‐se um número (peso) associado a cada arco
1
B
5
A
3
C
D
1
2
Prof. Rafael Concatto Beltrame
F
11