Teoria dos GrafosConceitos Básicos

Profª. Alessandra Martins Coelho

fev/2014

Grafos com apelidos

Grafos com apelidos

diamante

Grafos com apelidos

diamante casinha

Grafos com apelidos

diamante casinha touro

Grafos com apelidos

diamante casinha touro pegada

Grafos com apelidos

diamante casinha touro pegada

Guarda-chuva

Grafos com apelidos

diamante casinha touro pegada

Guarda-chuva cadeira

Grafos com apelidos

diamante casinha touro pegada

Guarda-chuva cadeira gema

Grafos com apelidos

diamante casinha touro pegada

Guarda-chuva cadeira gema dominó

Grafos com apelidos

Grafos com apelidos

antena

Grafos com apelidos

antena balão

Grafos com apelidos

antena balão leque

Grafos com apelidos

antena balão leque bandeira

Grafos com apelidos

antena balão leque bandeira

grilo

Grafos com apelidos

antena balão leque bandeira

grilo borboleta

Grafos com apelidos

antena balão leque bandeira

grilo borboleta garra

Grafos com apelidos

antena balão leque bandeira

grilo borboleta garraTorre Eiffel

Grafos com apelidos

Grafos com apelidos

Gêmeos

Grafos com apelidos

Gêmeos Sunlet

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 15x5 = 75, que é um número ímpar. Sabe-se que o grau de qualquer grafo deve ser um número par.

Subgrafo

• um subgrafo de um grafo G é um grafo cujo conjunto de vértices é um subconjunto do conjunto de vértices G e o conjunto de arestas é um subconjunto do conjunto de arestas de G, ou seja, cuja relação de adjacência é um subconjunto de G restrita a esse subconjunto.

Subgrafo

Subgrafo

Grafo exemplo Subgrafo próprio Subgrafo parcial próprio

Subgrafo parcial próprio

Um grafo é subgrafo parcial dele mesmo

Subgrafo induzido por Arestas

• Um subgrafo G pode ser obtido por um subconjunto e arestas e seus respectivos vértices.

• Neste caso será denominado induzido por arestas.

Exemplo

• Subgrafo por indução de arestas

Grafo de referência Arestas removidas Subgrafo formado

Subgrafo induzido por Vértices

• Um subgrafo G pode ser obtido por um subconjunto de vértices e suas respectivas arestas.

• Neste caso será denominado induzido por vértices.

Exemplo

• Subgrafo por indução de vértices

Grafo de referência vértice removido Subgrafo formado

Supergrafo

• Se G’ é um subgrafo de G, então G também pode ser denominado um supergrafo de G’.

Exemplo

• Supergrafo• Se G’ é um subgrafo de G, então G

também pode ser denominado um supergrafo de G’.

Grafo de referência Acréscimo de vértices Supergrafo formado

Exercício 5

• Quantos subgrafos com pelo menos um vértice tem K3?

Resolução

• Quantos subgrafos com pelo menos um vértice tem K3?

• São os subgrafos com um, dois e três vértices:– Existem três subgrafos com um vértice e nenhuma

aresta;– Existem C(3; 2) = 3 possibilidades de escolher

subgrafos com dois vértices. Para cada possibilidade, podemos incluir ou não a aresta, i.e., 3x2 = 6 subgrafos com dois vértices;

– Com três vértices, temos 23 = 8 possibilidades de incluir ou não cada aresta.

– Assim, a quantidade total de subgrafos com pelo menos um vértice é a soma de 3 + 6 + 8 = 17.

Exercício 6

• Desenhe todos os subgrafos do grafo abaixo.

Exercício 8

• Para o grafo da figura abaixo, determine um subgrafopróprio, um subgrafo parcial, um subgrafo induzido por vértices, um subgrafo induzido por arestas e um supergrafo.