Grafos - Parte 1

Prévia do material em texto

Grafos
Renato Ramos da Silva
Universidade Federal de Lavras
renato.ramos@dcc.ufla.br
10 de novembro de 2014
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 1 / 37
Overview
1 Grafos
2 Terminologia dos Grafos
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 2 / 37
Porque estudar Grafos
Importante ferramenta matemática com aplicação em diversas áreas
do conhecimento
I Genética, química, pesquisa operacional, telecomunicações, engenharia
elétrica, redes de computadores, conexão de vôos aéreos, restrições de
precedência, fluxo de programas, dentre outros
Utilizados na definição e/ou resolução de problemas
Os estudos teóricos em grafos buscam o desenvolvimento de
algoritmos mais eficientes.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 3 / 37
O que são grafos
Tipicamente um grafo é representado como um conjunto não vazio de
pontos ou vértices ligados por retas, que são chamadas de arestas
Ferramenta de modelagem
Abstração matemática que representa situações reais através de um
diagrama.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 4 / 37
As pontes de Königsberg
O rio Pregel divide o centro da cidade de Königsberg (Prússia no século
XVII, atual Kaliningrado, Rússia) em quatro regiões. Essas regiões são
ligadas por um complexo de sete (7) pontes, conforme mostra a figura.
Discutia-se nas ruas da cidade a possibilidade de atravessar todas as
pontes, voltando ao lugar de onde se saiu, sem repetir alguma. Havia-se
tornado uma lenda popular a possibilidade da façanha quando Euler, em
1736, provou que não existia caminho que possibilitasse tais restrições.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 5 / 37
As pontes de Königsberg
Resolvido em 1736 por Leonhard Euler
Necessário um modelo para representar o problema
Abstração de detalhes irrelevantes:
I Área de cada ilha
I Formato de cada ilha
I Tipo da ponte, etc.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 6 / 37
As pontes de Königsberg
Euler generalizou o problema através de um modelo de grafos
Euler mostrou que não existe o trajeto proposto utilizando o modelo em
grafos
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 7 / 37
Problemas comuns
O problema das 3 casas
É possível conectar os 3 serviços às 3 casas sem haver cruzamento de
tubulação?
Coloração
Quantas cores são necessárias para colorir o mapa do Brasil, sendo que
estados adjacentes não podem ter a mesma cor?
Caminho mínimo
De forma a reduzir seus custos operacionais, uma empresa de transporte de
cargas deseja oferecer aos motoristas de sua frota um mecanismo que os
auxilie a selecionar o melhor caminho (o de menor distância) entre
quaisquer duas cidades por ela servidas, de forma a que sejam minimizados
os custos de transporte.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 8 / 37
Modelagem com grafos
Estamos interessados em objetos e nas relações entre eles
Quem são eles nos problemas apresentados?
Como representar graficamente?
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 9 / 37
Modelagem com grafos
No problema das casas
Vértices são casas e serviços
Arestas são as tubulações entre casas e serviços
No problema da coloração de mapas
Vértices são estados
Arestas relacionam estados vizinhos
No problema do caminho mais curto
Vértices são as cidades
Arestas são as ligações entre as cidades
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 10 / 37
Definição
Um grafo G=(V,E) consiste em V, um conjunto não vazio de vértices (ou
nós), e E, um conjunto de arestas.
Cada aresta tem um ou dois vértices associados a ela, chamados de suas
extremidades.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 11 / 37
Definição
Grafo Simples
Um grafo no qual cada aresta conecta dois vértices diferentes e duas
arestas nunca conectam o mesmo par de vértices.
Multigrafos
Os grafos que podem ter arestas múltiplas conectando os mesmos vértices
Pseudografos
Os grafos que incluem laços.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 12 / 37
Definição
Digrafo
Um grafo orientado (V,E) consite em um conjunto não vazio de vértices V
e um conjunto de arestas orientadas(ou arcos) E.
Cada aresta orientada está associada a um par ordenado de vértices. É dito
que aresta orientada associada a par ordenado (u,v) começa em u e
termina em v.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 13 / 37
Definição 1
Definição 1
Dois vértices u e v em um grafo não orientado G são ditos adjacentes (ou
vizinhos) em G se u e v são extremidades de uma aresta de G.
Se e estiver associado a {u, v}, a aresta e é dita incidente aos vértices u e
v.
Diz-se também que a aresta e conecta u e v. Os vértices u e v são
chamados extremidades de uma aresta associada a {u, v}.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 14 / 37
Exemplo
e1, e2 ee3 são incidentes a v1.
v2 e v3 são adjacentes a v1.
e2, e3 e e4 são adjacentes a e1.
e6 e e7 são laços.
e2 e e3 são paralelas.
v5 e v6 são adjacentes entre si.
v4 é um vértice isolado.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 15 / 37
Definição 2
Grau
O grau de um vértice de um grafo não orientado é o número de arestas
incidentes a ele, exceto que um laço em um vértice contribui duas vezes ao
grau daquele vértice. O grau do vértice v é indicado por gr(v)
Grau (grafo dirgido)
Em um grafo com arestas orientadas, o grau de entrada de um vértice v ,
indicado por gr−(v), e o número de arestas que tem v como seu vértice
final.
O grau de saída de um vértice v indicado por gr+(v), é o número de
arestas que tem v como seu vértice inicial.
Observe que um laço em um vértice contribui com 1 tanto para o grau de
entrada quanto para saída desse vértice.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 16 / 37
Definição 2
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 17 / 37
Definição 2
Vértice isolado,pendente, par e impar)
Quando o grau de um vértice é 0(isolado), 1(pendente), 2(par) e 3 (impar).
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 18 / 37
Definição 2
Grafo Regular (k-regular)
todos os vértices têm o mesmo grau (k)
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 19 / 37
Teorema
Aperto de mãos
Seja G = (V,E) um grafo não orientado com e arestas. Então
2e =
∑
v∈V gr(v)
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 20 / 37
Exemplo
Exemplo
Quantas arestas existem em um grafo com 10 vértices, cada um de grau 6?
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 21 / 37
Exemplo
Exemplo
Quantas arestas existem em um grafo com 10 vértices, cada um de grau 6?
Resposta
6× 10 = 60
2e = 60 −→ e = 30
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 22 / 37
Grafo Completo
Definição
Um grafo completo de n vértices, denominado K ∗n , é um grafo simples com
n vértices v1, v2, . . . , vn , cujo conjunto de arestas contém exatamente uma
aresta para cada par de vértices distintos.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 23 / 37
Grafo Completo
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 24 / 37
Quantidade de grafos distintos com n vértices
O número total de grafos distintos com n vértices(|V |) é
2
n2−n
2 = 2
|V |2−|V |
2
que representa a quantidade de maneiras diferentes de escolher um
subconjunto a partir de
n2−n
2 =
|V |2−|V |
2
possíveis arestas de um grafo com n vértices.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 25 / 37
Exemplo
Exemplo
Quantosgrafos distintos com 3 vértices existem?
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 26 / 37
Exemplo
Exemplo
Quantos grafos distintos com 3 vértices existem?
2
n2−n
2 = 2
32−3
2 = 8
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 27 / 37
Grafo Ciclo
Definição
Um grafo ciclo de n vértices, denominado Cn , n ≥ 3, é um grafo simples
com n vértices v1, v2, . . . , vn , e arestas v1v2, v2v3, . . . , vn−1vn, vnv1.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 28 / 37
Grafo Roda
Definição
Um grafo roda, denominado Wn, é um grafo simples com n + 1 vértices
que é obtido acrescentado um vértice ao grafo ciclo Cn, n ≥ 3, e
conectando este novo vértice a cada um dos n vértices de Cn.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 29 / 37
Grafo Cubo-n
Definição
Um grafo cubo-n de 2n vértices, denominado Qn , é um grafo simples que
representa os 2n strings de n bits. Dois vértices são adjacentes sse osstrings
que eles representam diferem em exatamente uma posição.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 30 / 37
Grafo Bipartido
Definição
Um grafo simples G é dito bipartido se o seu conjunto V de vértices pode
ser dividido em dois cunjuntos disjuntos V1 e V2 tal que cada aresta do
grafo conecta um vértice em V1 e um vértice em V2.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 31 / 37
Grafo Bipartido Completo
Definição
O grafo bipartido completo Km,n é um grafo que tem seu conjunto de
vértices divididos em dois subconjuntos de m e n vértices, respectivamente.
Existe uma aresta entre dois vértices se e somente se um vértice estiver no
primeiro conjunto e o outro vértice no segundo subconjunto.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 32 / 37
Complemento de um Grafo
Definição
Seja G um grafo simples com um conjunto de vértices V. G’ é
complemento de G se V’ = V e dois vértices são adjacentes em G’, se e
somente se, não o são em G
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 33 / 37
Hipergrafo
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 34 / 37
Grafo Valorado
Definição
Um grafo valorado é um grafo em que cada aresta tem um valor associado.
Formalmente, um grafo valorado G = (V, E) consiste de um conjunto V de
vértices, um conjunto E de arestas, e uma função f de E para P , onde P
representa o conjunto de valores (pesos) associados às arestas.
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 35 / 37
subgrafo
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 36 / 37
The End
Renato Ramos da Silva (UFLA) Short title 10 de novembro de 2014 37 / 37
	Grafos
	Terminologia dos Grafos