Operações com grafos
União
– Considere 2 grafos G1(V1,E1) e G2(V2,E2) onde V1
e V2 são conjuntos distintos
– A união G1  G2 é formada pelo grafo com conjunto
de vértices V1  V2 e conjunto de arestas E1  E2
Exemplo
G: V1={1,2} e E1={(1,2)}
H: V2={3,4} e E2={ }
G  H: V={1,2,3,4} e E={(1,2)}
Soma
– Considere 2 grafos G1(V1,E1) e G2(V2,E2) onde V1
e V2 são conjuntos distintos
– A soma G1 + G2 é formada por G1  G2 e de
arestas ligando cada vértice de G1 a cada vértice de
G2.
Exemplo
G: V1 = {1,2} e E1 = {(1,2)}
H: V2 = {3,4} e E2 = { }
G + H: V={1,2,3,4} e
E={(1,2),(1,3),(1,4),(2,3),(2,4)}
Exemplo
1
2
3
G
H
GH
G+H
1
2
3
4
4
1
2
3
4
União e Soma
– Podem ser aplicadas a qualquer número finito de
grafos
– São operações associativas
– São operações comutativas
Remoção de Aresta
– Se e é uma aresta de um grafo G, denota-se G-e o
grafo obtido de G pela remoção da aresta e
– Genericamente, se F é um conjunto de arestas em
G, denota-se G-F ao grafo obtido pela remoção das
arestas em F.
Remoção de Vértice
– Se v é um vértice de um grafo G denota-se por G-v
o grafo obtido de G pela remoção do vértice v
conjuntamente com as arestas incidentes a v.
– Genericamente denota-se G-S ao grafo obtido pela
remoção dos vértices em S, sendo S um conjunto
qualquer de vértices de G.
Contração de aresta
– Denota-se por G/e o grafo obtido pela contração da
aresta e.
– Isto significa remover e de G e unir suas duas
extremidades v,w de tal forma que o vértice
resultante seja incidente às arestas originalmente
incidentes a v e w.
Representação de grafos
Embora seja conveniente a
representação de grafos através
de diagramas de pontos ligados
por linhas, tal representação é
inadequada se desejamos
armazenar grandes grafos em um
computador
Representação de grafos
Uma maneira simples de armazenar grafos,
é listando os vértices adjacentes a cada
vértice do grafo
u
y
v
x
w
u: v,y
v: u,y,w
w: v,x,y
x: w,y
y: u,v,w,x
Matriz de adjacência
Se G é um grafo com vértices {1,2,3,...,n}, sua
matriz de adjacência é a matriz n X n cujo
elemento ij é o número de arestas ligando o
vértice i ao vértice j
Matriz de incidência
Se G é um grafo com vértices {1,2,3,...,n} e
arestas {1,2,3,...,m}, sua matriz de incidência é a
matriz n X m cujo elemento ij é o número de vezes
em que o vértice i é incidente à aresta j.
Cadeias, caminhos, ciclos...
• Cadeia (= passeio)
– Uma cadeia (walk) é uma seqüência
qualquer de arestas adjacentes que ligam
dois vértices.
– O conceito de cadeia vale também para
grafos orientados, bastando que se ignore o
sentido da orientação dos arcos.
A seqüência de
vértices (x6, x5, x4,
x1) é um exemplo
de cadeia
Cadeia elementar (= caminho = path)
Uma cadeia é dita ser elementar se não passa
duas vezes pelo mesmo vértice
1
2
3
4
Cadeia de tamanho 2
124
1
2
3
4
Cadeia de tamanho 3
3142
Cadeia simples (= trilha = trail)
Uma cadeia é dita ser simples se não passa
duas vezes pela mesma aresta (arco).
1
2
3
4
Cadeia de tamanho 4
12413
1
2
3
4
Cadeia de tamanho 5
124132
• Caminho
– Um caminho é uma cadeia na qual todos os
arcos possuem a mesma orientação. Aplicase, portanto, somente a grafos orientados
A seqüência de
vértices (x1, x2, x5, x6,
x3)
é um exemplo de
caminho
• Ciclo
– Um ciclo é uma cadeia simples e fechada (o
vértice inicial é o mesmo que o vértice final).
• Circuito
– Um circuito é um caminho simples e fechado.
Aplica-se, portanto, somente a grafos orientados
A seqüência de
vértices (x1, x2, x5, x4,
x1)
é um exemplo de
circuito
Conectividade
Grafo Conexo
– Um grafo G(V,A) é dito ser conexo se há
pelo menos uma cadeia ligando cada par
de vértices deste grafo G. .
G1
G2
Grafo desconexo
– Um grafo G(V,A) é dito ser desconexo se
há pelo menos um par de vértices que não
está ligado por nenhuma cadeia. .
Componente conexa
–
–
Um grafo G(V,A) desconexo é formado por pelo
menos dois subgrafos conexos, disjuntos em
relação aos vértices
Cada um destes subgrafos conexos é dito ser uma
componente conexa de G.
Vértice de corte
Um vértice é dito ser um vértice de corte
se sua remoção (juntamente com as
arestas a ele conectadas) provoca uma
redução na conectividade do grafo.
X2 é um vértice de corte
Ponte
Uma aresta é dita ser uma ponte se sua
remoção provoca uma redução na
conectividade do grafo.
(X1,X4) é uma ponte
Outros tipos de grafos
Grafo cíclico (ou grafo circuito)
Um grafo conectado que é regular de grau
2 é um grafo cíclico (= ciclo)
Cn é um grafo cíclico com n vértices
C6
Grafo caminho
O grafo obtido a partir de Cn através da
remoção de um aresta é o grafo caminho
em n vértices, Pn
C5
P5
Grafo roda
O grafo obtido a partir de Cn-1 através da
ligação de cada vértice a um novo vértice
v é um grafo roda em n vértices, Wn
Corresponde à soma de N1 com Cn-1
C5
W
6
Grafos cúbicos
São grafos regulares de grau 3
O primeiro deles é conhecido
como Grafo de Petersen
Exemplos de ciclos
1
2
3
4
Ciclo de tamanho 3
1241
1
2
3
4
Ciclo de tamanho 3
1231
• Grafo fortemente conexo
– No caso de grafos orientados, um grafo é dito ser
fortemente conexo (f-conexo) se todo par de vértices
está ligado por pelo menos um caminho em cada
sentido
– ou seja, se cada par de vértices participa de um
circuito.
– Isto significa que cada vértice pode ser alcançável
partindo-se de qualquer outro vértice do grafo.
•Componente fortemente conexa
Um grafo G(V,A) que não é fortemente conexo
é formado por pelo menos dois subgrafos
fortemente conexos, disjuntos em relação aos
vértices
Cada um destes
subgrafos é dito ser
uma componente
fortemente conexa
de G
Grafos Eulerianos
Um grafo conectado G(V,A) é dito ser
euleriano se existe um ciclo que contém
todas as arestas de G.
cadeia simples fechada
– que não passa 2
vezes pela mesma
aresta e termina no
mesmo vértice
Grafo semi-euleriano
Um grafo conectado, não-euleriano G é
semi-euleriano se existe uma cadeia
simples contento todas as arestas de G
Teorema (Euler 1736)
Um grafo conectado G é euleriano se e
somente se o grau de cada vértice de G é par
Prova:
Ida: Seja G um grafo euleriano. Logo ele contém um
ciclo euleriano. Por cada ocorrência de vértice desse
ciclo, existe uma aresta que chega nesse vértice e
outra que sai desse vértice. Como toda aresta faz
parte do ciclo, isto é, nenhuma aresta fica fora do
ciclo, necessariamente o número de arestas por cada
vértice é par.
Volta: Suponhamos que todos os vértices possuem
grau par. Seja vi um vértice do grafo. Tentemos, a
partir de vi, construir uma cadeia que não passa
duas vezes pela mesma aresta, e até que não seja
possível continuar. Como todos os vértices
possuem um grau par, sempre será possível entrar
e sair de um vértice. A única exceção é o vértice vi
onde a cadeia vai terminar. Se essa cadeia, que
chamaremos C1, contém todas as arestas de G,
temos um ciclo euleriano. Senão, retiramos de G
todas as arestas que fazem parte de C1. No grafo
resultante G', todos os vértices também possuem
grau par e necessariamente um deles faz parte de
C1, senão o grafo não seria conexo.
Volta (cont.): Recomeçamos o mesmo processo
com o grafo G', partindo de um vértice comum com
C1, obtendo assim um novo ciclo C2. A figura
abaixo mostra que dois ciclos que têm um vértice
em comum podem formar um ciclo único:
chegando no vértice comum em um dos dois
ciclos, continuamos o percurso no outro ciclo.
Continuando esse processo, necessariamente
obteremos um ciclo único que contém todas as
arestas de G.
Algoritmo de Hierholzer
Algoritmo para a construção de um ciclo
euleriano sugerido a partir da prova do teorema
de Euler
Comece em qualquer vértice u e percorra
aleatoriamente as arestas ainda não visitadas a cada
vértice visitado até fechar um ciclo
Se sobrarem arestas não visitadas, recomece a partir
de um vértice do ciclo já formado
Se não existem mais arestas não visitadas, construa o
ciclo euleriano a partir dos ciclos formados, unindo-os
a partir de um vértice comum