View
280
Download
1
Category
Preview:
Citation preview
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.
Recommended