Algoritmos e Teoria dos GrafosAula 02
Prof. Murilo V. G. da Silva
DINF/UFPR
Material da Disciplina:
Renato J. S. Carmo
Notacoes, definicoes e terminologia
Seja C e um conjunto e k e um inteiro
2C = {S ; S ⊆ C},(C
k
)= {S ⊆ C ; |S | = k}.
Exercıcio
Seja X = {a, b, c , d}. Digo qual e o conjunto 2X ,(X2
)e(X3
)
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Seja C e um conjunto e k e um inteiro
2C = {S ; S ⊆ C},
(C
k
)= {S ⊆ C ; |S | = k}.
Exercıcio
Seja X = {a, b, c , d}. Digo qual e o conjunto 2X ,(X2
)e(X3
)
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Seja C e um conjunto e k e um inteiro
2C = {S ; S ⊆ C},(C
k
)= {S ⊆ C ; |S | = k}.
Exercıcio
Seja X = {a, b, c , d}. Digo qual e o conjunto 2X ,(X2
)e(X3
)
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Seja C e um conjunto e k e um inteiro
2C = {S ; S ⊆ C},(C
k
)= {S ⊆ C ; |S | = k}.
Exercıcio
Seja X = {a, b, c , d}. Digo qual e o conjunto 2X ,(X2
)e(X3
)
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Definicao de Grafo
Um grafo G e um par (V (G ),E (G )) onde V (G ) e um conjuntofinito e E (G ) ⊆
(V (G)2
).
Note que a definicao acima se refere a grafos simples nao–direcionados
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Definicao de Grafo
Um grafo G e um par (V (G ),E (G )) onde V (G ) e um conjuntofinito e E (G ) ⊆
(V (G)2
).
Note que a definicao acima se refere a grafos simples nao–direcionados
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Dado um grafo G = (V (G ),E (G )),
Cada elemento de V (G ) e chamado de vertice de G
Cada elemento de E (G ) e chamado de aresta de G
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Dado um grafo G = (V (G ),E (G )),
Cada elemento de V (G ) e chamado de vertice de G
Cada elemento de E (G ) e chamado de aresta de G
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Dado um grafo G = (V (G ),E (G )),
Cada elemento de V (G ) e chamado de vertice de G
Cada elemento de E (G ) e chamado de aresta de G
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Seja G um grafo e u e v vertices de G
Se a = {u, v} e uma aresta de G , dizemos que u e v sao aspontas da aresta a.
Dizemos tambem que:
a e incidente em u e em vu e v sao vizinhos (ou adjacentes) em Gduas arestas sao adjacentes se tem uma ponta em comumum vertice de G e isolado se nao tem vizinhosa vizinhanca de um vertice v em G e o conjunto dos verticesque sao vizinhos de v em G
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Seja G um grafo e u e v vertices de G
Se a = {u, v} e uma aresta de G , dizemos que u e v sao aspontas da aresta a.
Dizemos tambem que:
a e incidente em u e em vu e v sao vizinhos (ou adjacentes) em Gduas arestas sao adjacentes se tem uma ponta em comumum vertice de G e isolado se nao tem vizinhosa vizinhanca de um vertice v em G e o conjunto dos verticesque sao vizinhos de v em G
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Seja G um grafo e u e v vertices de G
Se a = {u, v} e uma aresta de G , dizemos que u e v sao aspontas da aresta a.
Dizemos tambem que:
a e incidente em u e em vu e v sao vizinhos (ou adjacentes) em Gduas arestas sao adjacentes se tem uma ponta em comumum vertice de G e isolado se nao tem vizinhosa vizinhanca de um vertice v em G e o conjunto dos verticesque sao vizinhos de v em G
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Seja G um grafo e u e v vertices de G
Se a = {u, v} e uma aresta de G , dizemos que u e v sao aspontas da aresta a.
Dizemos tambem que:
a e incidente em u e em v
u e v sao vizinhos (ou adjacentes) em Gduas arestas sao adjacentes se tem uma ponta em comumum vertice de G e isolado se nao tem vizinhosa vizinhanca de um vertice v em G e o conjunto dos verticesque sao vizinhos de v em G
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Seja G um grafo e u e v vertices de G
Se a = {u, v} e uma aresta de G , dizemos que u e v sao aspontas da aresta a.
Dizemos tambem que:
a e incidente em u e em vu e v sao vizinhos (ou adjacentes) em G
duas arestas sao adjacentes se tem uma ponta em comumum vertice de G e isolado se nao tem vizinhosa vizinhanca de um vertice v em G e o conjunto dos verticesque sao vizinhos de v em G
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Seja G um grafo e u e v vertices de G
Se a = {u, v} e uma aresta de G , dizemos que u e v sao aspontas da aresta a.
Dizemos tambem que:
a e incidente em u e em vu e v sao vizinhos (ou adjacentes) em Gduas arestas sao adjacentes se tem uma ponta em comum
um vertice de G e isolado se nao tem vizinhosa vizinhanca de um vertice v em G e o conjunto dos verticesque sao vizinhos de v em G
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Seja G um grafo e u e v vertices de G
Se a = {u, v} e uma aresta de G , dizemos que u e v sao aspontas da aresta a.
Dizemos tambem que:
a e incidente em u e em vu e v sao vizinhos (ou adjacentes) em Gduas arestas sao adjacentes se tem uma ponta em comumum vertice de G e isolado se nao tem vizinhos
a vizinhanca de um vertice v em G e o conjunto dos verticesque sao vizinhos de v em G
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Seja G um grafo e u e v vertices de G
Se a = {u, v} e uma aresta de G , dizemos que u e v sao aspontas da aresta a.
Dizemos tambem que:
a e incidente em u e em vu e v sao vizinhos (ou adjacentes) em Gduas arestas sao adjacentes se tem uma ponta em comumum vertice de G e isolado se nao tem vizinhosa vizinhanca de um vertice v em G e o conjunto dos verticesque sao vizinhos de v em G
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Vizinhanca
A vizinhanca de um vertice v e
ΓG (v) = {u ∈ V (G ) ; u e vizinho de v}.
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
Vizinhanca
A vizinhanca de um vertice v e
ΓG (v) = {u ∈ V (G ) ; u e vizinho de v}.
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
A fronteira de um conjunto X de vertices de G e o conjunto dearestas de G com uma ponta em X e a outra fora de X
Ou seja,
Fronteira
Dado X ⊆ V (G )
∂G (X ) = {{x , y} ∈ E (G ) ; x ∈ X e y /∈ X}
Convencao: Dado v ∈ V (G), o conjunto ∂G ({v}) e denotado ∂G (v)
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
A fronteira de um conjunto X de vertices de G e o conjunto dearestas de G com uma ponta em X e a outra fora de X
Ou seja,
Fronteira
Dado X ⊆ V (G )
∂G (X ) = {{x , y} ∈ E (G ) ; x ∈ X e y /∈ X}
Convencao: Dado v ∈ V (G), o conjunto ∂G ({v}) e denotado ∂G (v)
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
A fronteira de um conjunto X de vertices de G e o conjunto dearestas de G com uma ponta em X e a outra fora de X
Ou seja,
Fronteira
Dado X ⊆ V (G )
∂G (X ) = {{x , y} ∈ E (G ) ; x ∈ X e y /∈ X}
Convencao: Dado v ∈ V (G), o conjunto ∂G ({v}) e denotado ∂G (v)
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
A fronteira de um conjunto X de vertices de G e o conjunto dearestas de G com uma ponta em X e a outra fora de X
Ou seja,
Fronteira
Dado X ⊆ V (G )
∂G (X ) = {{x , y} ∈ E (G ) ; x ∈ X e y /∈ X}
Convencao: Dado v ∈ V (G), o conjunto ∂G ({v}) e denotado ∂G (v)
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
grafo trivial: um grafo com um unico vertice e sem arestas
grafo completo: um grafo em que cada vertice e vizinho detodos os outros. E comum indicar por Kn um grafo completode n vertices.
O grau de um vertice v ∈ V (G ), denotado δG (v), e o numerode arestas de G incidentes a v
Mais precisamente
δG (v) = |∂G (v)|
grafo regular: todos os seus vertices tem o mesmo grau
grafo k–regular: todos os vertices tem grau k
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
grafo trivial: um grafo com um unico vertice e sem arestas
grafo completo: um grafo em que cada vertice e vizinho detodos os outros. E comum indicar por Kn um grafo completode n vertices.
O grau de um vertice v ∈ V (G ), denotado δG (v), e o numerode arestas de G incidentes a v
Mais precisamente
δG (v) = |∂G (v)|
grafo regular: todos os seus vertices tem o mesmo grau
grafo k–regular: todos os vertices tem grau k
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
grafo trivial: um grafo com um unico vertice e sem arestas
grafo completo: um grafo em que cada vertice e vizinho detodos os outros. E comum indicar por Kn um grafo completode n vertices.
O grau de um vertice v ∈ V (G ), denotado δG (v), e o numerode arestas de G incidentes a v
Mais precisamente
δG (v) = |∂G (v)|
grafo regular: todos os seus vertices tem o mesmo grau
grafo k–regular: todos os vertices tem grau k
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
grafo trivial: um grafo com um unico vertice e sem arestas
grafo completo: um grafo em que cada vertice e vizinho detodos os outros. E comum indicar por Kn um grafo completode n vertices.
O grau de um vertice v ∈ V (G ), denotado δG (v), e o numerode arestas de G incidentes a v
Mais precisamente
δG (v) = |∂G (v)|
grafo regular: todos os seus vertices tem o mesmo grau
grafo k–regular: todos os vertices tem grau k
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
grafo trivial: um grafo com um unico vertice e sem arestas
grafo completo: um grafo em que cada vertice e vizinho detodos os outros. E comum indicar por Kn um grafo completode n vertices.
O grau de um vertice v ∈ V (G ), denotado δG (v), e o numerode arestas de G incidentes a v
Mais precisamente
δG (v) = |∂G (v)|
grafo regular: todos os seus vertices tem o mesmo grau
grafo k–regular: todos os vertices tem grau k
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
grafo trivial: um grafo com um unico vertice e sem arestas
grafo completo: um grafo em que cada vertice e vizinho detodos os outros. E comum indicar por Kn um grafo completode n vertices.
O grau de um vertice v ∈ V (G ), denotado δG (v), e o numerode arestas de G incidentes a v
Mais precisamente
δG (v) = |∂G (v)|
grafo regular: todos os seus vertices tem o mesmo grau
grafo k–regular: todos os vertices tem grau k
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Notacoes, definicoes e terminologia
grafo trivial: um grafo com um unico vertice e sem arestas
grafo completo: um grafo em que cada vertice e vizinho detodos os outros. E comum indicar por Kn um grafo completode n vertices.
O grau de um vertice v ∈ V (G ), denotado δG (v), e o numerode arestas de G incidentes a v
Mais precisamente
δG (v) = |∂G (v)|
grafo regular: todos os seus vertices tem o mesmo grau
grafo k–regular: todos os vertices tem grau k
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Isomorfismo de grafos
Mais precisamente
Isomorfismo
Um isomorfismo entre os grafos G e H e uma bijecaof : V (G )→ V (H) satisfazendo
{u, v} ∈ E (G )⇔ {f (u), f (v)} ∈ E (H).
Ideia: Um isomorfismo entre dois grafos e uma bijecao entre os vertices
preservando vizinhancas.
Observe que:se f : V (G) → V (H) e isomorfismo, entao f −1 : V (H) → V (G) tambem e.
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Isomorfismo de grafos
Mais precisamente
Isomorfismo
Um isomorfismo entre os grafos G e H e uma bijecaof : V (G )→ V (H) satisfazendo
{u, v} ∈ E (G )⇔ {f (u), f (v)} ∈ E (H).
Ideia: Um isomorfismo entre dois grafos e uma bijecao entre os vertices
preservando vizinhancas.
Observe que:se f : V (G) → V (H) e isomorfismo, entao f −1 : V (H) → V (G) tambem e.
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Isomorfismo de grafos
Mais precisamente
Isomorfismo
Um isomorfismo entre os grafos G e H e uma bijecaof : V (G )→ V (H) satisfazendo
{u, v} ∈ E (G )⇔ {f (u), f (v)} ∈ E (H).
Ideia: Um isomorfismo entre dois grafos e uma bijecao entre os vertices
preservando vizinhancas.
Observe que:se f : V (G) → V (H) e isomorfismo, entao f −1 : V (H) → V (G) tambem e.
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Isomorfismo de grafos
Mais precisamente
Isomorfismo
Um isomorfismo entre os grafos G e H e uma bijecaof : V (G )→ V (H) satisfazendo
{u, v} ∈ E (G )⇔ {f (u), f (v)} ∈ E (H).
Ideia: Um isomorfismo entre dois grafos e uma bijecao entre os vertices
preservando vizinhancas.
Observe que:se f : V (G) → V (H) e isomorfismo, entao f −1 : V (H) → V (G) tambem e.
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Isomorfismo de grafos
Grafos isomorfos
Dizemos que os grafos G e H sao isomorfos se existe um isomorfismoentre eles.
Automorfismo
Um automorfismo sobre um grafo G e um isomorfismo entre G e G .
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Isomorfismo de grafos
Grafos isomorfos
Dizemos que os grafos G e H sao isomorfos se existe um isomorfismoentre eles.
Automorfismo
Um automorfismo sobre um grafo G e um isomorfismo entre G e G .
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Matrizes
Matriz de incidencia
A matriz de incidencia de um grafo G e a matriz MG , indexada porV (G )× E (G ) dada por
MG [v , a] = 0, se v /∈ a,
MG [v , a] = 1, se v ∈ a
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
O Lema do aperto de maos
Teorema
Para todo grafo G , ∑v∈V (G)
δG (v) = 2|E (G )|.
Prova: (em sala)
Corolario: (“handshaking lemma”)
Em todo grafo o numero de vertices de grau ımpar e par.
Prova: (em sala)
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
O Lema do aperto de maos
Teorema
Para todo grafo G , ∑v∈V (G)
δG (v) = 2|E (G )|.
Prova: (em sala)
Corolario: (“handshaking lemma”)
Em todo grafo o numero de vertices de grau ımpar e par.
Prova: (em sala)
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
O Lema do aperto de maos
Teorema
Para todo grafo G , ∑v∈V (G)
δG (v) = 2|E (G )|.
Prova: (em sala)
Corolario: (“handshaking lemma”)
Em todo grafo o numero de vertices de grau ımpar e par.
Prova: (em sala)
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
O Lema do aperto de maos
Teorema
Para todo grafo G , ∑v∈V (G)
δG (v) = 2|E (G )|.
Prova: (em sala)
Corolario: (“handshaking lemma”)
Em todo grafo o numero de vertices de grau ımpar e par.
Prova: (em sala)
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Sequencia de graus
Sequencia de graus
A sequencia de graus de um grafo G e a sequencia (δ(v1), . . . , δ(vn))satisfazendo
δ(v1) ≥ δ(v2) ≥ . . . ≥ δ(vn−1) ≥ δ(vn) e {v1, . . . , vn} = V (G ).
Sequencia grafica
Uma sequencia de inteiros S = (d1, d2, . . . , dn) e uma sequencia graficase existe um grafo de n vertices cuja sequencia de graus e S .
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Sequencia de graus
Sequencia de graus
A sequencia de graus de um grafo G e a sequencia (δ(v1), . . . , δ(vn))satisfazendo
δ(v1) ≥ δ(v2) ≥ . . . ≥ δ(vn−1) ≥ δ(vn) e {v1, . . . , vn} = V (G ).
Sequencia grafica
Uma sequencia de inteiros S = (d1, d2, . . . , dn) e uma sequencia graficase existe um grafo de n vertices cuja sequencia de graus e S .
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Graus maximo e mınimo
Grau maximo
O grau maximo de um grafo G :
∆(G ) = Max{δG (v) ; v ∈ V (G )}
Grau mınimo
O grau mınimo de um grafo G :
δ(G ) = Min{δG (v) ; v ∈ V (G )}.
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Graus maximo e mınimo
Grau maximo
O grau maximo de um grafo G :
∆(G ) = Max{δG (v) ; v ∈ V (G )}
Grau mınimo
O grau mınimo de um grafo G :
δ(G ) = Min{δG (v) ; v ∈ V (G )}.
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Complemento de um grafo
Complemento
O complemento de um grafo G e o grafo G = (V (G ),E (G )) dado por
V (G ) = V (G ),
E (G ) =
(V (G )
2
)− E (G ).
(tambem chamado de grafo complementar)
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Complemento de um grafo
Complemento
O complemento de um grafo G e o grafo G = (V (G ),E (G )) dado por
V (G ) = V (G ),
E (G ) =
(V (G )
2
)− E (G ).
(tambem chamado de grafo complementar)
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Matriz de Adjacencia
Matriz de Adjacencia
A matriz de adjacencia do grafo G e a matriz MG indexada porV (G )× V (G ) dada por
MG [u, v ] = 0, se {u, v} ∈ E (G )
MG [u, v ] = 1, se {u, v} /∈ E (G )
Note que:
MG e simetrica de |V (G)|2 posicoes
Os elementos da diagonal principal sao todos nulos
Dependendo do contexto, a matriz de adjacencia pode ser encarada comouma matriz inteira ou como uma matriz booleana.
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Matriz de Adjacencia
Matriz de Adjacencia
A matriz de adjacencia do grafo G e a matriz MG indexada porV (G )× V (G ) dada por
MG [u, v ] = 0, se {u, v} ∈ E (G )
MG [u, v ] = 1, se {u, v} /∈ E (G )
Note que:
MG e simetrica de |V (G)|2 posicoes
Os elementos da diagonal principal sao todos nulos
Dependendo do contexto, a matriz de adjacencia pode ser encarada comouma matriz inteira ou como uma matriz booleana.
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Matriz de Adjacencia
Matriz de Adjacencia
A matriz de adjacencia do grafo G e a matriz MG indexada porV (G )× V (G ) dada por
MG [u, v ] = 0, se {u, v} ∈ E (G )
MG [u, v ] = 1, se {u, v} /∈ E (G )
Note que:
MG e simetrica de |V (G)|2 posicoes
Os elementos da diagonal principal sao todos nulos
Dependendo do contexto, a matriz de adjacencia pode ser encarada comouma matriz inteira ou como uma matriz booleana.
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Matriz de Adjacencia
Matriz de Adjacencia
A matriz de adjacencia do grafo G e a matriz MG indexada porV (G )× V (G ) dada por
MG [u, v ] = 0, se {u, v} ∈ E (G )
MG [u, v ] = 1, se {u, v} /∈ E (G )
Note que:
MG e simetrica de |V (G)|2 posicoes
Os elementos da diagonal principal sao todos nulos
Dependendo do contexto, a matriz de adjacencia pode ser encarada comouma matriz inteira ou como uma matriz booleana.
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos
Matriz de Adjacencia
Matriz de Adjacencia
A matriz de adjacencia do grafo G e a matriz MG indexada porV (G )× V (G ) dada por
MG [u, v ] = 0, se {u, v} ∈ E (G )
MG [u, v ] = 1, se {u, v} /∈ E (G )
Note que:
MG e simetrica de |V (G)|2 posicoes
Os elementos da diagonal principal sao todos nulos
Dependendo do contexto, a matriz de adjacencia pode ser encarada comouma matriz inteira ou como uma matriz booleana.
Prof. Murilo V. G. da Silva Algoritmos e Teoria dos Grafos