Grafos3

Prévia do material em texto

Grafos
Renato Ramos da Silva
Universidade Federal de Lavras
renato.ramos@dcc.ufla.br
20 de novembro de 2014
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 1 / 38
Overview
1 Circuito Euleriano
2 Circuito Hamiltoniano
3 Árvores
4 Grafos Planares
5 Coloração de Grafos
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 2 / 38
Circuito Euleriano
Definição
Seja G um grafo. Um circuito Euleriano é um circuito que contém cada
vértice e cada aresta de G . É uma sequência de vértices e arestas
adjacentes que começa e termina no mesmo vértice de G, passando pelo
menos uma vez por cada vértice e exatamente uma única vez por cada
aresta de G .
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 3 / 38
Circuito Euleriano
Problema
É possível que uma pessoa faça um percurso na cidade de tal forma que
inicie e volte a mesma posição passando por todas as pontes somente uma
única vez?
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 4 / 38
Circuito Euleriano
No entanto, se cada vértice de um grafo tem grau par, então o grafo tem
um circuito Euleriano?
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 5 / 38
Circuito Euleriano
No entanto, se cada vértice de um grafo tem grau par, então o grafo tem
um circuito Euleriano?
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 6 / 38
Algoritmo de Hierholzer
Passo 1
Escolha qualquer vértice v de G .
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 7 / 38
Algoritmo de Hierholzer
Passo 2
Escolha uma sequência qualquer de vértices e arestas adjacentes,
começando e terminando em v , sem repetir arestas. Chame o circuito
resultante de C .
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 8 / 38
Algoritmo de Hierholzer
Passo 3
Verifique se C contém cada aresta e vértice de G . Se sim, C é um circuito
Euleriano e o problema está terminado. Caso contrário, execute os passos
abaixo.
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 9 / 38
Algoritmo de Hierholzer
Passo 3a
Remova todas as arestas do circuito C do grafo G e quaisquer vértices
que se tornaram isolados quando as arestas de C são removidas.
Chame o grafo resultante de G’.
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 10 / 38
Algoritmo de Hierholzer
Passo 3b
Escolha qualquer vértice w comum a ambos C e G’.
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 11 / 38
Algoritmo de Hierholzer
Passo 3c
Escolha uma sequência qualquer de vértices e arestas adjacentes,
começando e terminando em w, sem repetir arestas. Chame o circuito
resultante de C’.
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 12 / 38
Algoritmo de Hierholzer
Passo 3d
Agrupe C e C’ para criar um novo circuito C” como segue:
Comece em v e siga em direção a w .
Percorra todo o circuito C’ e volte a w.
Caminhe pela parte de C’ não percorrida ainda até o vértice v.
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 13 / 38
Algoritmo de Hierholzer
Passo 3e
Seja c ← C” e retorne ao passo 3
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 14 / 38
Exercício
Determine se o grafo abaixo tem um circuito Euleriano. Em caso positivo
ache um circuito Euleriano para o grafo.
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 15 / 38
Exercício
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 16 / 38
Exercício
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 17 / 38
Circuito Hamiltoniano
Definição
Dado um grafo G , um Circuito Hamiltoniano para G é um circuito simples
que inclui cada vértice de G , ou seja, uma sequência de vértices adjacentes
e arestas distintas tal que cada vértice de G aparece exatamente uma única
vez.
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 18 / 38
Comentários sobre circuitos Euleriano e Hamiltoniano
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 19 / 38
Circuito Hamiltoniano
Definição
É possível determinar a priori se um grafo G possui um circuito
Euleriano.
Não existe um teorema que indique se um grafo possui um circuito
Hamiltoniano nem se conhece um algoritmo eficiente (polinomial) para
achar um circuito Hamiltoniano.
No entanto, existe uma técnica simples que pode ser usada em muitos
casos para mostrar que um grafo não possui um circuito Hamiltoniano.
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 20 / 38
Determinando se um grafo não possui um circuito
Hamiltoniano
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 21 / 38
O Problema do Caixeiro Viajante
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 22 / 38
O Problema do Caixeiro Viajante
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 23 / 38
O Problema do Caixeiro Viajante
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 24 / 38
Árvores
Definição
Uma árvore é um grafo conexo não orientado e sem circuitos simples.
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 25 / 38
Floresta
Definição
Uma floresta é um grafo cujas componentes conexas são árvores.
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 26 / 38
Árvore Enraizada
Definição
Uma árvore T = (V,E) é denominado enraizada quando algum vértice v é
escolhido como especial. Esse vértice v é a raiz da árvore.
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 27 / 38
Árvore Geradora Mínima
Algoritmos
Prim e Kruskal
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 28 / 38
Grafos Planares
Definição
Grafo que pode ser desenhado no plano sem cruzamentos, isto é, duas
arestas somente se encontram nos vértices onde são incidentes
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 29 / 38
Grafos Planares
Exemplos
k4 e Q4
Exemplos
k3,3 e k5
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 30 / 38
Grafos Planares
Definição
Todo subgrafo de um grafo planar é planar
Todo grafo que tem um subgrafo não planar é não planar
Todo grafo que contém o K3,3 ou K5 como subgrafos, é não planar
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 31 / 38
Grafos Homeomórficos
Definição
Dois grafos são homeomórficos se ambos podem ser obtidos a partir do
mesmo grafo através da inserção de novos vértices de grau 2 em suas
arestas (tal operação é chamada de subdivisão elementar)
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 32 / 38
Grafos Homeomórficos
Planaridade
A inserção ou exclusão de arestas de grau 2 é irrelevante para a
consideração de planaridade. Mas o conceito de grafo homeomórfico é
utilizado para a definição do teorema de Kuratowski:
Teorema de Kuratowski (1930)
Um grafo é planar se e somente se não contém nenhum subgrafo
homeomórfico a K3,3 ou K5
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 33 / 38
Coloração de Grafos
Definição
Colorir vértices de forma que vértices adjacentes possuam cores diferentes
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 34 / 38
Colorindo vértices
Se G é um grafo simples, então uma coloração para G é uma atribuição de
cores para cada vértice de forma que vértices adjacentes tenham diferentes
cores
Dizemos que G é k-colorível se podemos atribuir uma das k cores para
colorir G O número cromático de um grafo G é o menor número de cores
que é necessário para colorir G. Seja c o número cromático de G,
escrevemos crom(G)=c
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 35 / 38
Colorindo vérticesPropriedades
Cada mapa no plano pode ser representado por um grafo que é
chamado de grafo dual.
Podemos assumir que todos os grafos, para fins de coloração, são
simples e conectados, já que arestas múltiplas e vértices isolados são
irrelevantes para coloração de vértices
Está claro que crom(Kn) = n , então existem grafos com número
cromático arbitrariamente grande
Os grafos roda com número impar de vértices são 4-cromáticos
Teorema das 4 cores (Appel e Haken, 1976) - O número cromático de
um grafo planar não é maior que 4
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 36 / 38
Colorindo vértices
Algoritmo
Liste os nós em ordem decrescente de grau
Associe a cor 1 ao primeiro nó da lista e ao próximo nó da lista não
adjacente a ele, e sucessivamente para cada nó da lista não adjacente
a um nó com a cor 1.
Associe a cor 2 ao próximo nó da lista ainda sem cor. Sucessivamente
associe a cor 2 para o próximo nó da lista não adjacente aos nós com
cor 2 e que ainda não está colorido.
Continue com esse processo até que todos os nós sejam coloridos
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 37 / 38
The End
Renato Ramos da Silva (UFLA) Short title 20 de novembro de 2014 38 / 38
	Circuito Euleriano
	Circuito Hamiltoniano
	Árvores
	Grafos Planares
	Coloração de Grafos