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
Operações com grafos
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)}
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.
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: v,yv: u,y,ww: v,x,yx: w,yy: u,v,w,x
u
y v
x w
Representação de grafos
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.
• 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
Cadeias, caminhos, ciclos...
Cadeia elementar (= caminho = path) Uma cadeia é dita ser elementar se não passa duas vezes pelo mesmo vértice
1 2
3 4
1 2
3 4
Cadeia de tamanho 21 2 4
Cadeia de tamanho 33 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
1 2
3 4
Cadeia de tamanho 41 2 4 1 3
Cadeia de tamanho 51 2 4 1 3 2
• Caminho– Um caminho é uma cadeia na qual todos os
arcos possuem a mesma orientação. Aplica-se, portanto, somente a grafos orientados
A seqüência de vértices (x1, x2, x5, x6,
x3)
é um exemplo de caminho
• 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
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
Conectividade
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 corteUm 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
PonteUma aresta é dita ser uma ponte se sua remoção provoca uma redução na conectividade do grafo.
(X1,X4) é uma ponte
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
Outros tipos de grafos
C6
Grafo caminhoO 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 rodaO 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 W6
• 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 conexaUm 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
Um grafo conectado G(V,A) é dito ser euleriano se existe um ciclo que contém todas as arestas de G.
Grafos Eulerianos
cadeia simples fechada – que não passa 2 vezes pela mesma aresta e termina no mesmo vértice
Grafo semi-eulerianoUm 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 v i
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 HierholzerAlgoritmo 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