Teoria dos GrafosAula 3 - Conceitos Básicos

Profª. Alessandra Martins Coelho

março/2013

Grafos com apelidos

diamante casinha touro pegada

Guarda-chuva cadeira gema dominó

Grafos com apelidos

antena

Grafos com apelidos

antena balão leque bandeira

grilo borboleta garraTorre Eiffel

Grafos com apelidos

Gêmeos Sunlet Peixe

Grafos com apelidos

• Grafo Pirâmide

Grafo pirâmide forte Grafo pirâmide dupla

Grafos com apelidos

• Grafo Escorpião• possui 4 tipos de vértice:

– Um vértice de grau 1 – ferrão. – Um vértice de grau 2 – calda.– Um vértice de grau n -1 – corpo– n - 3 vértices restantes - pés

Grafo Linha

• É denotado por L(G) e representa a adjacência entre as arestas do grafo G.– Cada vértice de L(G) representa uma aresta

em G

– Dois vértices de L(G) são adjacentes se e somente suas arestas correspondentes compartilham um mesmo vértice em G, ou seja, são adjacentes em G.

Grafo Linha

Grafo G Vértices associados às arestas

Ligação das arestas vizinhas

Grafo Linha – L(G)

Fecho Transitivo de um vértice

• O conjunto de vértices alcançáveis a partir de x.

Fecho Transitivo de um vértice

• O conjunto de vértices alcançáveis a partir de x.

Fecho transitivo direto do vértice 1 – {2,3,4,5,7,9,10,13}

Fecho Transitivo de um vértice

Fecho Transitivo de um grafo

• O grafo G construído a partir de G, incluindo-se um arco (x,y) para todo y alcançável a partir de x.

Fecho Transitivo de um grafo

Grafo de alcançabilidade de G ou grafo fecho transitivo

Exercício1 - Exemplo

Exercício 1

• você percebeu alguma relação entre os números obtidos? O que você observou?

• O que você observou é válido para TODOS os grafos? Construa um grafo (com pelo menos 6 vértices) e faça a tabela. A sua observação continua valendo?

• Escreva um argumento que explique a sua observação.

Grau

• grau (ou valência) de um vértice de um grafo éo número de arestas incidentes para com o vértice, com os laços contados duas vezes.

• Lema do Aperto de Mão [Euler (1735)] Se os convidados de uma festa apertarem as mãos quando se encontrarem pela primeira vez, o número de convidados que apertam a mão um número ímpar de vezes é par.

• A soma total dos graus de todos os vértices de um grafo é 2x o número de arestas.

Exercício 2

• Quantas arestas tem um grafo com vértices de graus 5; 2; 2; 2; 2; 1? Desenhe um possível grafo.

Resolução

• O grafo possui seis vértices e tem um grau total de 5 + 2 + 2 + 2 + 2 + 1 = 14. Isso significa que existem sete arestas.

Exercício 3

• Existe um grafo simples com cinco vértices dos seguintes graus? Se existir, desenhe um possível grafo.

(a) 3; 3; 3; 3; 2(b) 1; 2; 3; 4; 5(c) 1; 2; 3; 4; 4(d) 3; 4; 3; 4; 3(e) 0; 1; 2; 2; 3

Resolução

• O grafo tem um grau total de 3 + 3 + 3 + 3 + 2 = 14. Isso significa que existem 7 arestas.

Resolução

• O grafo tem um grau total de 1 + 2 + 3 + 4 + 5 = 15. Isso não é possível.

Resolução

• O grafo tem um grau total de 1+2+3+4+4 = 14. No entanto, como existem dois vértices com grau 4, todos os vértices devem ter pelo menos grau 2, como mostrado na figura abaixo. Como supostamente existe um vértice com grau 1, não é possível existir tal grafo.

Resolução

• O grafo tem um grau total de 3 + 4 + 3 + 4 + 3 = 17. Isso não é possível.

Resolução

• O grafo tem um grau total de 0 + 1 + 2 + 2 + 3 = 8. Isso significa que existem quatro arestas.

Exercício 4

• Pode haver um grafo simples com 15 vértices, cada um com grau 5?

Resolução

• Não. O grau desse suposto grafo seria 155 = 75, que é um número ímpar. Sabe-se que o grau de qualquer grafo deve ser um número par.