Grafos
Introdução
Grafos
Grafos
Prof. Dr. Julio Arakaki
www.pucsp.br/~jarakaki ([email protected])
Depto. Ciência da Computação
© Julio Arakaki
1
Ciência da Computação
Grafos
Introdução
Grafos
Grafos --Definições
Definições
Abstração
(relacionamento entre pares de elementos)
Como representar formalmente?
Conjuntos
(vértices-elementos e arestas-relacionamentos)
© Julio Arakaki
2
Ciência da Computação
1
Grafos
Introdução
Grafos
Grafos --Definições
Definições
G = (V, E), onde:
V = conjunto de vértices
(elementos)
E = conjunto de arestas
(relacionamentos entre pares – ordenados ou não ordenados)
Vértice – “Vertex”
Aresta – “Edge”
Exemplo de grafo: G = (V, E)
V = {ana, joão, maria, zé}
E = {(ana,joão), (ana,maria),(joão,maria),(maria,zé)}
© Julio Arakaki
3
Ciência da Computação
Grafos
Introdução
Grafos
Grafos ––Definições
Definições––Representação
RepresentaçãoGráfica
Gráfica
Exemplo de grafo: G = (V, E)
V = {Ana, João, Maria, Zé}
E = {(Ana,João), (Ana,Maria),(João,Maria),(Maria,Zé)}
João
Ana
Maria
Zé
© Julio Arakaki
4
Ciência da Computação
2
Grafos
Introdução
Grafos
Grafos ––Definições
Definições
Adjacência – dois vértices são adjacentes, se eles forem “vizinhos”
Ou seja, seja G = (V, E), a e b são adjacentes se existir a aresta
e = (a, b) no conjunto E.
Incidência – a aresta e é incidente a a e b
No exemplo:
V = {Ana, João, Maria, Zé}
E = {(Ana,João), (Ana,Maria),(João,Maria),(Maria,Zé)}
Os vértices Zé e Ana são adjacentes?
Os vértices Maria e João são adjacentes?
© Julio Arakaki
5
Ciência da Computação
Grafos
Introdução
Grafos
Grafos ––Definições
Definições
Grau de um vértice v - número de vértices adjacentes a v
É representado por r.
Exemplo: G = (V, E)
V = {Ana, João, Maria, Zé}
E = {(Ana,João), (Ana,Maria),(João,Maria),(Maria,Zé)}
grau(Ana) = ?
grau(Zé) = ?
Exercício: Dado G = (V, E)
Grau mínimo de um vértice?
Grau máximo de um vértice?
© Julio Arakaki
6
Ciência da Computação
3
Grafos
Introdução
Grafos
Grafos ––Definições
Definições
Grafo Regular – um grafo é regular, quando todos os seus
vértices tem o mesmo grau. Ou seja, ele é r-regular.
Exemplo: G = (V, E)
G é 2-regular, n = 3
V = {11, 22, 33}
E = {(11,22), (11,33), (22,33)}
11
22
33
© Julio Arakaki
7
Ciência da Computação
Grafos
Introdução
Grafos
Grafos ––Definições
Definições
Grafo Regular – Outros exemplos:
Grafo Cúbico
- Como seria uma possível
definição?
© Julio Arakaki
8
Ciência da Computação
4
Grafos
Introdução
Grafos
Grafos ––Exercício
Exercício
Dado um grafo G = (V, E). Sabendo se que G é r-regular e n
corresponde ao número de vértices de G
Determinar uma “fórmula” para calcular o número de arestas
de um grafo G.
Exemplo:
G é 2-regular, n = 3
V = {11, 22, 33}
E = {(11,22), (11,33), (22,33)}
11
22
33
© Julio Arakaki
9
Ciência da Computação
Grafos
Introdução
Grafos
Grafos ––Exercício
Exercício
Estes grafos são regulares?
Porque?
Verifique se a “fórmula”
determinada no exercício
anterior permite o cálculo
do número de arestas destes
Grafos.
© Julio Arakaki
10
Ciência da Computação
5
Grafos
Introdução
Grafos
Grafos ––Definições
Definições
Grafo Completo – um grafo onde todos os seus vértices tem o
grau máximo. Ou seja, existe aresta presente entre todos os
pares de vértices.
Dê exemplos:
Quantas arestas possuem um grafo completo Kn ?
n(n − 1)
2
onde, n é o número de vértices
© Julio Arakaki
11
Ciência da Computação
Grafos
Introdução
Grafos
Grafos ––Definições
Definições
Grafo Completo
Outros exemplos
© Julio Arakaki
12
Ciência da Computação
6
Grafos
Introdução
Grafos
Grafos ––Definições
Definições
Caminho de um Grafo – seqüência de vértices conectados por
arestas.
O comprimento de um caminho é dado pela quantidade de
arestas que formam este caminho.
- Caminho Simples: os vértices do caminho são distintos. Ou
seja, não existe “voltas”.
© Julio Arakaki
13
Ciência da Computação
Grafos
Introdução
Grafos
Grafos ––Definições
Definições
Caminho de um Grafo – seqüência de vértices conectados por
arestas.
O comprimento de um caminho é dado pela quantidade de
arestas que formam este caminho.
- Caminho Simples: os vértices do caminho são distintos. Ou
seja, não existe “voltas”.
© Julio Arakaki
14
Ciência da Computação
7