TEMA_1 1_-_ARA0175_-_CARACTER_STICAS_E_DEFINI__ES

Prévia do material em texto

Prof. Marcelo Andrade Teixeira
Universidade Estácio de Sá
TEMA 1 – Conceituação e Formalização de Grafos
Prof. Marcelo Andrade Teixeira
Universidade Estácio de Sá
CONCEITOS EM TEORIA DOS GRAFOS
ALGORITMOS EM GRAFOS 3
• um conjunto de vér ces
• um conjunto de arestas
ALGORITMOS EM GRAFOS 4
• um conjunto de vér ces
• um conjunto de arestas
ALGORITMOS EM GRAFOS 5
• um conjunto de vér ces
• um conjunto de arestas
ALGORITMOS EM GRAFOS 6
Um grafo pode ser definido como: 
Grafo :
• = conjunto de objetos chamados de vér ces ou nós 
• = conjunto de pares relacionados chamados de arestas 
• Arestas são pares não ordenado: 
ALGORITMOS EM GRAFOS 7
ALGORITMOS EM GRAFOS 8
Grafos simples são grafos sem laços 
e sem arestas múl plas (paralelas)
Mul grafos são grafos com laços ou 
com arestas múl plas (paralelas)
ALGORITMOS EM GRAFOS 9
Grafos nulo é um grafo 
que não possui arestas.
3
1
2
4
ALGORITMOS EM GRAFOS 10
ALGORITMOS EM GRAFOS 11
ALGORITMOS EM GRAFOS 12
ALGORITMOS EM GRAFOS 13
2
3
4
1
Exemplo: 
•
•
Ou seja:
•
•
ALGORITMOS EM GRAFOS 14
ALGORITMOS EM GRAFOS 15
ALGORITMOS EM GRAFOS 16
ALGORITMOS EM GRAFOS 17
ALGORITMOS EM GRAFOS 18
ALGORITMOS EM GRAFOS 19
ALGORITMOS EM GRAFOS 20
ALGORITMOS EM GRAFOS 21
ALGORITMOS EM GRAFOS 22
ALGORITMOS EM GRAFOS 23
ALGORITMOS EM GRAFOS 24
Com 5 vértices?
Faça o cálculo e o desenho de todas as possíveis arestas de um 
grafo com 5 vér ces.
ALGORITMOS EM GRAFOS 25
ALGORITMOS EM GRAFOS 26
O grau máximo de um grafo é 
denotado por , e o grau mínimo de 
um grafo, denotado por 
São os graus máximos e mínimos de 
seus vértices. 
2
3
1
4
ALGORITMOS EM GRAFOS 27
ALGORITMOS EM GRAFOS 28
O grau máximo de um grafo é 
denotado por , e o grau mínimo de 
um grafo, denotado por 
São os graus máximos e mínimos de 
seus vértices. 
2
3
1
4
ALGORITMOS EM GRAFOS 29
ALGORITMOS EM GRAFOS 31
ALGORITMOS EM GRAFOS 32
Prova. Assuma que G(V,A) é um grafo não orientado qualquer, e seja P a propriedade 
𝑣∈𝑉 , onde m é tamanho de G:
Base. Para tem-se que o grau do único vértice é zero e que m é zero. Logo, a 
propriedade é verdadeira.
Passo de indução: Seja G(V,A) um grafo com a propriedade P acima, e G' um grafo 
obtido a partir de G por uma das operações que se seguem:
ALGORITMOS EM GRAFOS 33
Passo de indução: Seja G(V,A) um grafo com a propriedade P acima, e G' um grafo 
obtido a partir de G por uma das operações que se seguem:
inserção de vértice: O vértice inserido tem grau zero, pois não está conectado a 
nenhum outro vértice do grafo, de forma que a parcela à esquerda da igualdade não é 
alterada. Como o número m de arestas não é modificado, a parcela à direita da 
igualdade também não é alterada. Logo a propriedade P é mantida em G'.
ALGORITMOS EM GRAFOS 34
Passo de indução: Seja G(V,A) um grafo com a propriedade P acima, e G' um grafo 
obtido a partir de G por uma das operações que se seguem:
inserção de aresta: A aresta inserida conecta dois vértices de G'ou é um laço. No 
primeiro caso há o acréscimo de uma unidade no grau de cada um dos dois vértices,
enquanto que no segundo caso são acrescidas duas unidades no grau do vértice . Em
ambos casos a parcela da esquerda de P sofre um acréscimo de duas unidades. Como o 
número m de aresta aumenta em uma unidade, a parcela da direita de P sofre um 
acréscimo de 2 unidades. Logo, a propriedade P é mantida.
ALGORITMOS EM GRAFOS 35
ALGORITMOS EM GRAFOS 36
2
3
1
4
2
3
1
4
5
Exemplos:
ALGORITMOS EM GRAFOS 37
Prova direta:
Assuma que G(V,A) é um grafo não-orientado. Seja n o número de vértices de G com grau 
impar. Como o somatório dos graus dos vértices G é par (teorema 1), segue que n deve ser par. 
Logo, o número de vértices de grau ímpar de G é sempre par. 
ALGORITMOS EM GRAFOS 38
Prova direta:
Assuma que G(V,A) é um grafo não-orientado. Seja n o número de vértices de G com grau 
impar. Como o somatório dos graus dos vértices G é par (teorema 1), segue que n deve ser par. 
Logo, o número de vértices de grau ímpar de G é sempre par. 
Prova por contradição:
Assuma que G(V,A) é um grafo não-orientado. Seja n o número de vértices de G com grau 
ímpar. Suponha, agora, que n seja ímpar. Segue que o somatório dos graus dos vértices G é 
impar o que contradiz o Teorema 1. Logo, o número de vértices de grau ímpar de G é sempre 
par. 
ALGORITMOS EM GRAFOS 39
Teorema 3. Seja um grafo não orientado e conexo com vértices. Então contém 
pelo menos arestas.
Teorema 1.
2. Pode haver um grafo simples com 15 vértices, cada um com grau 5? 
3. Quantas arestas tem um grafo com vértices de graus 5, 2, 2, 2, 2, 1? 
Desenhe o grafo. 
ALGORITMOS EM GRAFOS 40
um possível grafo.
a) 3, 3, 3, 3, 2
b) 1, 2, 3, 4, 5
c) 1, 2, 3, 4, 4
d) 0, 1, 2, 2, 3
e) 3, 4, 3, 4, 3
ALGORITMOS EM GRAFOS 41
Dúvidas?
Bibliografia
• Fundamentos da teoria dos grafos para computação. Maria do Carmo 
Nicole (Autor), Estevam R. Hruschka Júnior. Editora LTC.
• Fundamentos Matemá cos para a Ciência da Computação. Judith 
Gers ng. Editora LTC.
• Grafos: Teoria, Modelos, Algoritmos. Paulo Oswaldo Boaventura Ne o. 
Editora Blucher.
Baseado no material da Prof. Simone Gama ALGORITMOS EM GRAFOS 42
Leitura Auxiliar
• Provas graus em grafos: h p://www.inf.ufsc.br/grafos/teo-prov/teoremas-de-
grafos.htm
• h ps://www.inf.ufrgs.br/~prestes/Courses/Graph%20Theory/Livro/LivroGrafos.pdf