Grafos
Histórico, exemplos e problemas
Definições
• Dois tipos de elementos
– Vértices ou nós
– Arestas
v1
v3
v4
v5
v2
v6
Grafo Simples
• G = (V,E)
– V é um conjunto finito não-vazio de vértices
– E é um conjunto finito de arestas
– |V| é o número de vértices representado por n, se n=|V|
– |E| é o número de arestas representado por m, isto é
m=|E|
– Cada aresta e pertencente ao conjunto E será denotada
pelo par de vértices (x,y) que a forma
– Dizemos que os vértices x e y são extremos (ou
extremidades) da aresta e.
Grafo Simples
– Resumindo: um grafo é simples se entre
cada par de vértices distintos existir no
máximo uma aresta e se, além disso,
não contiver laços, ou seja existir uma
aresta que conecta um vértice a ele
mesmo.
G = (V,E)
Dois vértices x e y são ditos adjacentes ou
vizinhos se existe uma aresta e unindo-os.
Os vértices u e v são ditos incidentes na
aresta e, se eles são extremos de e.
Duas arestas são adjacentes se elas têm ao
menos um vértice em comum.
A aresta e=(x,y) é incidente a ambos os
vértices x e y.
Grafo simples
v1
v3
v4
v2
V = {v1, v2, v3, v4, v5, v6}
e1
v5
v6
E = {(v1,v2),(v1,v3),(v1,v4),(v2,v4),(v3,v4),(v4,v5)}
e1 é incidente a v4 e v5
Exemplo
Exercício
Desenhe a representação geométrica do
seguinte grafo:
V = {1,2,3,4,5,6};
E ={(1,2),(1,3),(3,2),(3,6),(5,3),(5,1),(5,6),(4,6),
(4,5),(6,1),(6,2),(3,4)}
Mais definições
• Laço
– É uma aresta formada por um par de vértices
idênticos
• Arestas múltiplas ou paralelas
– Quando existe mais de uma aresta entre o
mesmo par de vértices.
• Multigrafo
– Um grafo que permite a existência de arestas
múltiplas
Exercício
Defina formalmente o grafo abaixo e identifique
os conceitos de laço, aresta múltipla e multigrafo
no mesmo:
Grau de um vértice
Grau de um vértice v (grau(v))é o número de
arestas que incidem em v.
O grau de um vértice v também pode ser definido
como o número de arestas adjacentes a v.
Obs.: Um laço conta duas vezes para o grau de um
vértice
Grau(b) = 3
Grau(d) = 2
Grau(a) = 2
– Qualquer vértice de grau zero é um
vértice isolado
– Qualquer vértice de grau 1 é um
vértice terminal
– Um vértice ímpar tem um número ímpar de
arestas
– Um vértice par, tem um número par de arestas
Grafo Regular (k-regular)
– todos os vértices têm o mesmo grau (k)
v1
v2
v4
v3
Seqüência de graus de um grafo consiste
em escrever em ordem crescente o grau
de todos os seus vértices
V6 é um vértice isolado,
grau(v6)=0
v1
v3
v4
v2
V5 é um vértice terminal,
grau(v5)=1
e1
v5
v6
V2 é um vértice par,
grau(v2)=2
V1 é um vértice ímpar,
grau(v1)=3
Seqüência de graus = 0,1,2,2,3,4
Exercício
Identificar no grafo abaixo os vértices isolados,
terminais, impares, pares e a seqüência de graus
do grafo :
Reflexão
O que podemos concluir sobre a soma dos graus
de um grafo?
Soma dos graus de um grafo:
O resultado é sempre par, e corresponde à
formula abaixo:
A prova é inspirada no Teorema do Aperto de Mãos
que diz:
Se várias pessoas se apertam a mão o número total
de mãos apertadas tem que ser par. Precisamente
porque duas mãos estão envolvidas em cada aperto.
Soma dos graus de um grafo:
Em grafos, cada aresta contribui duas unidades para
o cômputo geral do grau dos vértices, pois cada
aresta possui dois extremos. Portanto, a soma total é
par e duas vezes o número de arestas do grafo.
Se o grafo for regular de grau r, a soma dos graus
dos vértices também é igual a r vezes o número de
vértices.
A soma dos graus de um grafo é sempre par:
Quando o grafo é regular de grau r, temos:
Corolário
Em qualquer grafo, o no de vértices com grau ímpar
deve ser PAR
Prova
Para a soma ser par, o primeiro somatório tem que
gerar um resultado par, portanto |Vímpar| é par.
Outros tipos de grafos
Grafo Nulo (vazio)
Grafo cujo número de arestas é zero. Ou, grafo
regular de grau zero.
Nn é um grafo nulo com n vértices
1
3
Exemplo: N4
V={1,2,3,4}; E={ }.
2
4
Grafo Completo
Grafo simples em que quaisquer vértices
distintos dois a dois são adjacentes. Ou, grafo
regular de grau n-1, onde n=|V|.
Kn é um grafo completo com n vértices.
Exemplo: K4
Quantas arestas tem o Kn?
Veja que |E| = ( r * |v| ) / 2, onde r é o grau e v o
número de vértices.
Logo |E| = (( n - 1 ) n ) / 2
Podemos provar também com análise
combinatória. O número de arestas é igual ao
número de combinações de n vértices dois a dois.
Cn,m = n! / ( m! (n – m)! )
Complemento de um grafo
Seja G um grafo simples com um conjunto de
vértices V.
G é complemento de G se
V=V
e
dois vértices são adjacentes em G, se e
somente se, não o são em G
Complemento de um grafo
Complemento de um grafo
Propriedade 1
Um grafo regular tem complemento
regular
Propriedade 2
O complemento de Kn é Nn
Exercício:
Dê exemplos que confirmem as
propriedades acima
Grafo Bipartido
Um grafo é dito ser bipartido quando seu
conjunto de vértices V puder ser particionado
em dois subconjuntos V1 e V2, tais que toda
aresta de G une um vértice de V1 a outro de V2.
5
1
V1
3
2
4
6
V2
Grafo Bipartido
Sejam os conjuntos H={h | h é um homem} e
M={m | m é um mulher} e o grafo G(V,A) onde:
V=HUM
A = {(v,w) | (v  H e w  M) ou (v  M e w  H)
e <v foi namorado de w>}
Grafo Bipartido Completo
É um grafo bipartido em V1 e V2, sendo que
cada elemento de V1 é adjacente a cada
elemento de V2.
V1
V2
K3,
3
Subgrafo
Um grafo Gs(Vs, As) é dito ser subgrafo de um
grafo G(V,A) quando Vs  V e As  A. O grafo
G2, por exemplo, é subgrafo de G1.
Denotamos por
G1
G2  G1
G2
Subgrafo Próprio
Um subgrafo G2 é dito próprio, quando G2 é
subgrafo distinto de G1
V(G2)  V(G1) ou A(G2)  A(G1)
Ou seja, G2  G1 e G2  G1, denotamos G2  G1 e
dizemos que G2 é subgrafo próprio de G1
Subgrafos podem ser obtidos através da
remoção de arestas e vértices.
Subgrafo Induzido
Se G2 é um subgrafo de G1 e possui toda a aresta
(v, w) de G1 tal que ambos, v e w, estejam em V2,
então G2 é o subgrafo induzido pelo subconjunto de
vértices V2.
3
G1
G2
1
4
3
2
5
V1= {1,2,3,4,5}
2
1
4
V2= {1,2,3,4}
V2 induz G2
Clique
Denomina-se clique de um grafo G a um subgrafo
(induzido) de G que seja completo
Grafo Rotulado
Um grafo G(V,A) é dito ser rotulado em vértices (ou
arestas) quando a cada vértice (ou aresta) estiver
associado um rótulo
Grafo Valorado
Um grafo G(V,A) é dito ser valorado quando
existe uma ou mais funções relacionando V
e/ou A com um conjunto de números.
V = {v | v é uma cidade com aeroporto}
A = {(v,w,t) | <há linha aérea ligando v a w, sendo t o
tempo esperado de vôo>}
Isomorfismo de Grafos
Dois grafos G1 e G2 são isomorfos se existe
uma correspondência um a um entre os vértices
de G1 e G2, com a propriedade de que o
número de arestas unindo os vértices em G1
é igual ao número de arestas unindo os
vértices correspondentes em G2.
Isomorfismo de Grafos
(em outras palavras)
Sejam dois grafos G1(V1,A1) e G2(V2,A2). Um
isomorfismo de G1 sobre G2 é um mapeamento
bijetivo f: V1  V2 tal que {x,y}  A1 se e
somente se {f(x),f(y)} A2, para todo x,y  V1.
Função:
{ (a2), (b  1), (c  3), (d  4), (e  6), (f  5) }
Isomorfismo de Grafos
u
v
w
x
y
z
(exemplo)
f(u) = azul, f(v) = lilás, f(w) = vermelho,
f(x) = verde, f(y) = amarelo, f(z) = rosa
Isomorfismo
• Qual não é isomorfo aos outros 3 ?
Isomorfismo
• Resposta
Os três primeiros grafos são isomorfos ao esqueleto de um
octaedro. Qualquer um dos três têm 8 vértices, todos de grau
4.
O quarto grafo tem um vértice de grau 5, tem um vértice de
grau 3 e os restantes vértices de grau 4. Logo não pode ser
isomorfo aos 3 primeiros grafos
Isomorfismo de Grafos
Preserva:
•Reflexividade: Todo o grafo é isomorfo a si mesmo.
•Simestria: Se grafo é isomorfo a um segundo grafo então
também o segundo é isomorfo ao primeiro.
•Transitividade: Se um grafo é isomorfo a um segundo, que
por sua vez é isomorfo a um terceiro grafo, então o o
primeiro é isomorfo ao terceiro.
•Proposições válidas se G1  G2
G1 e G2 têm o mesmo número de vértices
•G1 e G2 têm o mesmo número de arestas
•G1 e G2 têm a mesma sequência de graus
Grafos Orientados ou Dígrafos
Um dígrafo D(V,A) é um conjunto finito não vazio V
de vértices, e um conjunto A de pares ordenados de
elementos de V. Chamamos o conjunto A de arcos
Digrafo Simples
É um digrafo que não possui laços e os arcos são
todos distintos
Mais sobre dígrafos
• Conjunto finito não vazio de vértices
• Conjunto finito não vazio de arestas
– Arestas são chamadas de arcos
– Um arco (v,w) passa a ser vw
a
d
D = (V,A)
V = {a,b,c,d)
A = {ac,ba,bc,cb,cd,cd)
b
c
• Dígrafos Simples
– Todos os arcos são distintos
– Não existem auto-laços
• Para obter o grafo correspondente a um dígrafo
– Eliminar as direções dos arcos
– Não necessariamente um grafo
correspondente a um dígrafo simples é um
grafo simples Apresente um exemplo de um
dígrafo simples que quando
transformado em grafo, não é
simples
• Os vértices de um dígrafo possuem:
– Grau de entrada: número de arcos que chegam no
vértice (grauent(v))
– Grau de saída: número de arcos que partem do vértice
(grausai(v))
• Da mesma forma:
– Sequência de graus de entrada
– Sequência de graus de saída
Proposição
 grauent(vi) =  grausai(vi) = | A |
• Os dígrafos são isomórficos se:
– Existe um isomorfismo entre os respectivos
grafos correspondentes
– Preserva a ordem dos vértices em cada arco
Os grafos abaixo não são isomorfos
a
b
d
c
a
b
d
c