AULA 3 PPT - OTIM DE SISTEMAS DE TRANS GST0311

Prévia do material em texto

OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES
Aula 3 – Grafos
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
 GRAFOS
Objetivos:
1. Identificar os conceitos iniciais para a construção de grafos. 2. Conhecer exemplos de aplicação prática de grafos. 
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
 A Pesquisa Operacional utiliza os grafos em diversas situações.
 Exemplo: interligações entre “locais”. 
 Os “locais” são chamados vértices (ou nós) e as ligações são chamadas arestas entre os “locais”.
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
 
 Conjunto de vértices: V= {a,b,c,d,}.
 Arcos representam as ligações entre os vértices.
 Arcos são representados como pares ordenados.
 O par ordenado (a,b), por exemplo, representa o arco
 que liga os vértices a e b.
 Conjunto de todos os arcos: A={(a,b),(a,d),(d,b),(b,c),(d,c)}
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
Malha rodoviária ligando cidades de uma região.
Os vértices representam as cidades e os arcos representam as ligações entre as cidades.
Se ab, então (a,b)(b,a)
 mas, se estradas forem de mão dupla, por exemplo, os arcos (a,b) e (b,a) são iguais.
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
É possível definir grafo como um par G = (V,E) onde V é um conjunto finito e não vazio e E é uma relação (função) sobre os elementos de V.
Os elementos de V são chamados de vértices ( ou nós), e os pares ordenados (vi,vj), que representam as relações entre os elementos de V, são chamados de arestas ( linhas) do grafo.
QUESTÃO EXEMPLO 1
QUESTÃO EXEMPLO 2
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
Uma aresta é dita incidente com os vértices que ela liga. Se uma aresta é incidente em um único vértice é chamado de laço.
2. Dois vértices são chamados de adjacentes se estão ligados pôr arestas. Um vértice é dito isolado, se não tem aresta incidindo sobre ele.
Aqui podemos ver a incidência entre o vértice “V1” e o vértice “V2”. E o vértice “V3” como vértice isolado
QUESTÃO EXEMPLO 3
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
3. Define-se grau de um vértice v  V, denotado pôr gr (v) como sendo o número de arestas incidentes em v. Um grafo é dito regular de grau r se todos seus vértices possuem grau r.
Grafo regular de grau 3 (r = 3) 
Ordem do grafo: V = 4 A = 6
QUESTÃO EXEMPLO 4
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
4. Se o grafo é regular de grau zero, é dito nulo. Um vértice de grau 1, é dito pendente.
Grafo regular de grau zero (r = 0) 
Ordem do grafo: V = 4 A = 0
Vértices pendentes: (v4 e v5)
Ordem do grafo: V = 5 A = 1
QUESTÃO EXEMPLO 5
QUESTÃO EXEMPLO 6
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
5. Duas arestas que incidam sobre o mesmo vértice são ditas adjacentes. Se os dois vértices de incidência são os mesmos, as arestas são ditas paralelas.
Vértices (v1e v4) possuem arestas paralelas;
Ordem do grafo: V = 4 A = 5
QUESTÃO EXEMPLO 7
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
Vértices adjacentes: 
(V6,V2) (V6,V5) (V2,V3) (V2,V4) (V3,V5) (V4,V5)
Vértice isolado:
V1
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
Vértice de grau nulo: V4 Vértice Pendente: V2 pois gr (V2) = 1 
Arestas adjacentes que incidem sobre:
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
Um grafo é dito dirigido ou dígrafo se suas arestas possuem orientação. Em caso contrário diz-se que o grafo é não dirigido. Em um grafo dirigido as arestas são chamadas arcos.
Antecessor de um vértice vi é todo vértice vj que seja extremidade inicial de uma arco que termina em vi.
Sucessor de um vértice vi é todo vj que seja extremidade final de um arco que parte de vi.
O grau de um vértice de um grafo orientado é a soma dos graus dos arcos que saem do vértice , isto é, o grau de emissão (de saída) e o grau de recepção (de entrada).
QUESTÃO EXEMPLO 8
QUESTÃO EXEMPLO 9
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
Um grafo onde existe um número Wij associado a cada aresta é um grafo denominado valorado e o número Wij é chamado custo da aresta.
Multígrafo é o grafo que contém arestas paralelas ou laços.
Grafo simples é um grafo que não contém nenhum par de arestas paralelas ou laços.
Grafo completo é um grafo simples que será completo quando existir uma aresta entre cada par de seus vértices.
QUESTÃO EXEMPLO 10
RESUMINDO
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
É possível definir grafos como sendo: 
Um par G = (V, E), onde V é um conjunto finito e não vazio, e E é uma relação (função) sobre os elementos de V.
Um par G = (V, E), onde V é um conjunto finito e vazio, e E é uma relação (função) sobre os elementos de V.
Um par G = (V, E), onde E é um conjunto infinito e não vazio, e V é uma relação (função) sobre os elementos de V.
Um par G = (V, E), onde V é um conjunto finito e não vazio, e E é uma relação (função) sobre os elementos que não pertençam V.
Um par G = (V, E), onde E é um conjunto finito e não vazio, e V é uma relação (função) sobre os elementos que pertençam E.
1ª - Questão Proposta:
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
É possível definir grafos como sendo:­
 Um par G = (V, E), onde V é um conjunto finito e vazio, e E é uma relação (função) sobre os elementos de V.
Um par G = (V, E), onde E é um conjunto infinito e não vazio, e V é uma relação (função) sobre os elementos de V.
Um par G = (V, E), onde V é um conjunto finito e não vazio, e E é uma relação (função) sobre os elementos de V.
Um par G = (V, E), onde V é um conjunto finito e não vazio, e E é uma relação (função) sobre os elementos que não pertençam V.
Um par G = (V, E), onde E é um conjunto finito e não vazio, e V é uma relação (função) sobre os elementos que pertençam E.
Gabarito 1ª - Questão Proposta:
RETORNAR
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
Pode-se dizer que vértices são:
Os elementos de E que são chamados de nós.
Os elementos de V que são chamados de nós.
Os pares ordenados (vi, vj), que representam as relações entre os elementos de E, do grafo
Os pares ordenados (vi, vj), que representam as relações entre os elementos de V, do grafo
Os elementos de V ou E que são chamados de nós.
2ª - Questão Proposta:
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
Pode-se dizer que vértices são:
 Os elementos de E que são chamados de nós.
Os pares ordenados (vi, vj), que representam as relações entre os elementos de E, do grafo
Os elementos de V que são chamados de nós.
Os pares ordenados (vi, vj), que representam as relações entre os elementos de V, do grafo
Os elementos de V ou E que são chamados de nós.
Gabarito 2ª - Questão Proposta:
RETORNAR
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
É possível afirmar sobre uma aresta incidente em um único vértice que:
 
É chamada de paralela
É chamada de laço ou paralela
É Chamado de nulo
É chamada de laço 
É chamado de pendente
3ª - Questão Proposta:
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
É possível afirmar sobre uma aresta incidente em um único vértice que:
 
É chamada de paralela
É chamada de laço ou paralela
É Chamado de nulo
É chamada de laço
É chamado de pendente
Gabarito 3ª - Questão Proposta:
RETORNAR
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMASDE TRANSPORTES 
É dito que o “Grafo” é regular quando:
Existir o mesmo grau em todos os seus vértices.
Existir uma aresta entre cada par de seus vértices.
Existir uma aresta entre cada par de seus vértices e o mesmo grau em todos os seus vértices.
Existir uma aresta entre pelo menos um par de seus vértices.
Existir uma aresta entre quase todos os pares de seus vértices.
4ª - Questão Proposta:
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
É dito que o “Grafo” é regular quando:
Existir o mesmo grau em todos os seus vértices.
Existir uma aresta entre cada par de seus vértices.
Existir uma aresta entre cada par de seus vértices e o mesmo grau em todos os seus vértices.
Existir uma aresta entre pelo menos um par de seus vértices.
Existir uma aresta entre quase todos os pares de seus vértices.
Gabarito 4ª - Questão Proposta:
RETORNAR
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
É possível afirmar sobre um vértice com seu Grau gr(v) = 0, que:
 
É chamada de laço
É Chamado de nulo ou isolado
É chamada de paralela
É chamada de laço ou paralela
É chamado de pendente
5ª - Questão Proposta:
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
É possível afirmar sobre um vértice com seu Grau gr(v) = 0, que:
 
É chamada de laço
É Chamado de nulo ou isolado
É chamada de paralela
É chamada de laço ou paralela
É chamado de pendente
Gabarito 5ª - Questão Proposta:
RETORNAR
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
É possível afirmar sobre um vértice com seu Grau gr(v) = 1, que:
 
É chamada de laço
É chamada de paralela
É chamado de pendente
É chamada de laço ou paralela
É Chamado de nulo
6ª - Questão Proposta:
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
É possível afirmar sobre um vértice com seu Grau gr(v) = 1, que:
 
É chamada de laço
É chamada de paralela
É chamado de pendente
É chamada de laço ou paralela
É Chamado de nulo
Gabarito 6ª - Questão Proposta:
RETORNAR
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
É possível afirmar sobre duas arestas incidentes em dois vértices sendo esses os mesmos vértices que:
 
São chamadas de laços
São chamadas de laços ou paralelas
São chamadas de nulas
São chamadas de pendentes
São chamadas de paralelas
7ª - Questão Proposta:
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
É possível afirmar sobre duas arestas incidentes em dois vértices sendo esses os mesmos vértices que:
 
São chamadas de laços
São chamadas de laços ou paralelas
São chamadas de nulas
São chamadas de pendentes
São chamadas de paralelas
Gabarito 7ª - Questão Proposta:
RETORNAR
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
Todo vértice vj, que seja extremidade inicial de um arco que termina em vi, é chamado de:
Sucessor de um vértice vi
Antecessor de um vértice vi
Pendente de um vértice vi
Regular de um vértice vi
Laço de um vértice vi
8ª - Questão Proposta:
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
Todo vértice vj, que seja extremidade inicial de um arco que termina em vi, é chamado de:
Sucessor de um vértice vi
Antecessor de um vértice vi
Pendente de um vértice vi
Regular de um vértice vi
Laço de um vértice vi
Gabarito 8ª - Questão Proposta:
RETORNAR
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
Todo vj que seja extremidade final de um arco que parte de vi, é chamado de:
 
Antecessor de um vértice vi:
Pendente de um vértice vi
Sucessor de um vértice vi
Regular de um vértice vi
Laço de um vértice vi
9ª - Questão Proposta:
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
Todo vj que seja extremidade final de um arco que parte de vi, é chamado de:
 
Antecessor de um vértice vi:
Pendente de um vértice vi
Sucessor de um vértice vi
Regular de um vértice vi
Laço de um vértice vi
Gabarito 9ª - Questão Proposta:
RETORNAR
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
É dito que o “Grafo” é completo quando:
Existir o mesmo grau em todos os seus vértices.
Existir uma aresta entre cada par de seus vértices e o mesmo grau em todos os seus vértices.
Existir uma aresta entre pelo menos um par de seus vértices.
Existir uma aresta entre cada par de seus vértices.
Existir uma aresta entre quase todos os pares de seus vértices.
10ª - Questão Proposta:
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
É dito que o “Grafo” é completo quando:
Existir o mesmo grau em todos os seus vértices.
Existir uma aresta entre cada par de seus vértices e o mesmo grau em todos os seus vértices.
Existir uma aresta entre pelo menos um par de seus vértices.
Existir uma aresta entre cada par de seus vértices.
Existir uma aresta entre quase todos os pares de seus vértices.
Gabarito 10ª - Questão Proposta:
RETORNAR
Tema da Apresentação
AULA 3- GRAFOS
– 
OTIMIZAÇÃO DE SISTEMAS DE TRANSPORTES 
BONS ESTUDOS E ATÉ A PRÓXIMA
Tema da Apresentação