Caminhos
19 de abril de 2021
Caminhos
Seja G = (V, E) um grafo e w = v1 v2 . . . vn um sequências de vértices.
Diz-se que
• w é um caminho, se vi vi+1 ∈ E;
• O caminho w é um ciclo se ele começa e termina no mesmo vértice;
• w é um caminho simples ou ciclo simples se ele não contêm a
mesma aresta mais de uma vez.
Comprimento de um caminho
é o número de arestas desse caminho.
Caminhos
Seja G = (V, E) um grafo e w = v1 v2 . . . vn um sequências de vértices.
Diz-se que
• w é um caminho, se vi vi+1 ∈ E;
• O caminho w é um ciclo se ele começa e termina no mesmo vértice;
• w é um caminho simples ou ciclo simples se ele não contêm a
mesma aresta mais de uma vez.
Comprimento de um caminho
é o número de arestas desse caminho.
Caminhos
Seja G = (V, E) um grafo e w = v1 v2 . . . vn um sequências de vértices.
Diz-se que
• w é um caminho, se vi vi+1 ∈ E;
• O caminho w é um ciclo se ele começa e termina no mesmo vértice;
• w é um caminho simples ou ciclo simples se ele não contêm a
mesma aresta mais de uma vez.
Comprimento de um caminho
é o número de arestas desse caminho.
Caminhos
Seja G = (V, E) um grafo e w = v1 v2 . . . vn um sequências de vértices.
Diz-se que
• w é um caminho, se vi vi+1 ∈ E;
• O caminho w é um ciclo se ele começa e termina no mesmo vértice;
• w é um caminho simples ou ciclo simples se ele não contêm a
mesma aresta mais de uma vez.
Comprimento de um caminho
é o número de arestas desse caminho.
Caminhos
Seja G = (V, E) um grafo e w = v1 v2 . . . vn um sequências de vértices.
Diz-se que
• w é um caminho, se vi vi+1 ∈ E;
• O caminho w é um ciclo se ele começa e termina no mesmo vértice;
• w é um caminho simples ou ciclo simples se ele não contêm a
mesma aresta mais de uma vez.
Comprimento de um caminho
é o número de arestas desse caminho.
Caminhos
Exemplo 1. Considere o grafo G
• abcad não é um caminho;
• ae1 be3 ce4 d é um caminho simples de comprimento 3;
• ae1 be3 ce4 de6 a é um ciclo simples de comprimento 4.
Caminhos
Exemplo 1. Considere o grafo G
• abcad não é um caminho;
• ae1 be3 ce4 d é um caminho simples de comprimento 3;
• ae1 be3 ce4 de6 a é um ciclo simples de comprimento 4.
Caminhos
Exemplo 1. Considere o grafo G
• abcad não é um caminho;
• ae1 be3 ce4 d é um caminho simples de comprimento 3;
• ae1 be3 ce4 de6 a é um ciclo simples de comprimento 4.
Caminhos
Grafo conexo
Um grafo é dito conexo se houver um caminho entre quaisquer dois de
seus vértices.
Teorema
Seja A = (aij ) a matriz de adjacência de um grafo conexo G. Então o
elemento ij da matriz Ak dá o número de caminhos diferentes de
comprimento k entre vi e vj .
Invariante do isomorfismo
Grafos isomorfos têm:
• Mesma quantidade de caminhos de comprimento k.
Caminhos
Grafo conexo
Um grafo é dito conexo se houver um caminho entre quaisquer dois de
seus vértices.
Teorema
Seja A = (aij ) a matriz de adjacência de um grafo conexo G. Então o
elemento ij da matriz Ak dá o número de caminhos diferentes de
comprimento k entre vi e vj .
Invariante do isomorfismo
Grafos isomorfos têm:
• Mesma quantidade de caminhos de comprimento k.
Caminhos
Grafo conexo
Um grafo é dito conexo se houver um caminho entre quaisquer dois de
seus vértices.
Teorema
Seja A = (aij ) a matriz de adjacência de um grafo conexo G. Então o
elemento ij da matriz Ak dá o número de caminhos diferentes de
comprimento k entre vi e vj .
Invariante do isomorfismo
Grafos isomorfos têm:
• Mesma quantidade de caminhos de comprimento k.
Caminhos
Exemplo 2.
Existem 5 caminhos de compri-
mento 2 ligando b ao b, no-
meiadamente: be2 ce2 b, be2 ce3 b,
be3 ce3 b, be3 ce2 b e be1 ce1 b.
Grafos Eulerianos e Semi-eulerianos
Caminho e Ciclo de Euler
• Um caminho contenha cada aresta do grafo,exatamente uma vez
cada, é denominado caminho euleriano;
• Um ciclo que contenha cada aresta do grafo,exatamente uma vez
cada, é denominado ciclo euleriano;
• Um grafo diz euleriano se admite um ciclo euleriano e semi-euleriano
se admite um caminho de euler.
Teorema
• Um grafo conexo G é euleriano se e somente se todo o vértice de G
tem grau par;
• Um grafo conexo G, com |V| > 2 tem um caminho x − y euleriano
sse x e y são os únicos vértices de grau ı́mpar
Grafos Eulerianos e Semi-eulerianos
Caminho e Ciclo de Euler
• Um caminho contenha cada aresta do grafo,exatamente uma vez
cada, é denominado caminho euleriano;
• Um ciclo que contenha cada aresta do grafo,exatamente uma vez
cada, é denominado ciclo euleriano;
• Um grafo diz euleriano se admite um ciclo euleriano e semi-euleriano
se admite um caminho de euler.
Teorema
• Um grafo conexo G é euleriano se e somente se todo o vértice de G
tem grau par;
• Um grafo conexo G, com |V| > 2 tem um caminho x − y euleriano
sse x e y são os únicos vértices de grau ı́mpar
Grafos Eulerianos e Semi-eulerianos
Caminho e Ciclo de Euler
• Um caminho contenha cada aresta do grafo,exatamente uma vez
cada, é denominado caminho euleriano;
• Um ciclo que contenha cada aresta do grafo,exatamente uma vez
cada, é denominado ciclo euleriano;
• Um grafo diz euleriano se admite um ciclo euleriano e semi-euleriano
se admite um caminho de euler.
Teorema
• Um grafo conexo G é euleriano se e somente se todo o vértice de G
tem grau par;
• Um grafo conexo G, com |V| > 2 tem um caminho x − y euleriano
sse x e y são os únicos vértices de grau ı́mpar
Grafos Hamiltonianos
Grafo hamiltoniano
é aquele que possui ciclo hamiltoniano, isto é, um ciclo que contém cada
vértice do grafo exactamente uma vez.
Teorema
|V|
Seja G(V, E) um grafo com pelo menos 3 vértices e tal que d(v) > 2 ,
para todo vértice v ∈ V. Então G é hamiltoniano.
Grafos Hamiltonianos
Grafo hamiltoniano
é aquele que possui ciclo hamiltoniano, isto é, um ciclo que contém cada
vértice do grafo exactamente uma vez.
Teorema
|V|
Seja G(V, E) um grafo com pelo menos 3 vértices e tal que d(v) > 2 ,
para todo vértice v ∈ V. Então G é hamiltoniano.
Grafos Hamiltonianos
Grafo hamiltoniano
é aquele que possui ciclo hamiltoniano, isto é, um ciclo que contém cada
vértice do grafo exactamente uma vez.
Teorema
|V|
Seja G(V, E) um grafo com pelo menos 3 vértices e tal que d(v) > 2 ,
para todo vértice v ∈ V. Então G é hamiltoniano.
Caminhos
Grafo com pesos
é aquele em que cada aresta tem um número associado a ele,
reprentando um custo (peso, distância, tempo, etc). Em outras palavras,
está definida a função
w : E(G) → R+
que atribui um peso, a cada aresta de G.
Exemplo 3. Grafo com pesos
Caminhos
Grafo com pesos
é aquele em que cada aresta tem um número associado a ele,
reprentando um custo (peso, distância, tempo, etc). Em outras palavras,
está definida a função
w : E(G) → R+
que atribui um peso, a cada aresta de G.
Exemplo 3. Grafo com pesos
Caminhos
Observação:
Num grafos com pesos, o comprimento de um caminho é a soma dos
pesos das arestas do caminho, i.e, se c = e1 e2 . . . en
X
n
L(c) = w(ei ).
i=1
Exemplo 4.
• L(acfg) = w(ac) + w(cf) +
w(fg) = 2 + 55 + 21 = 78;
• L(abdeg) =
1 + 3 + 13 + 89 = 106.
Caminhos
Observação:
Num grafos com pesos, o comprimento de um caminho é a soma dos
pesos das arestas do caminho, i.e, se c = e1 e2 . . . en
X
n
L(c) = w(ei ).
i=1
Exemplo 4.
• L(acfg) = w(ac) + w(cf) +
w(fg) = 2 + 55 + 21 = 78;
• L(abdeg) =
1 + 3 + 13 + 89 = 106.
Caminho Mı́nimo
O caminho mı́nimo entre os vértices v e w de um grafo com pesos G
é aquele cuja soma dos pesos das arestas tem o menor valor possı́vel
dentre todos os caminhos existentes entre v e w.
Algoritmo de Dijkstra
Algoritmo de Dijkstra
• O algoritmo começa por etiquetar a com um zero e os outros
vértices com ∞, i.e L(a) = 0 e L(vi ) = ∞.
• Em cada passo, os vértices em S são aqueles para os quais já é
conhecida a distância mı́nima a partir de a.
• com a condição z 6∈ S, o algoritmo termina quando a distância
mı́nima de a a z for conhecida. Ao substituir a condição z 6∈ S por
V(G) 6= S, o algoritmo termina quando é conhecida a distância
mı́nima de a para os restantes vértices do grafo.
• A instrução if L(u) + w(u, v) < L(v) then L(v) = L(u) + w(u, v)
actualiza L(v), tendo sido assim identificado um percurso mais curto
de a para v.
Algoritmo de Dijkstra
• O algoritmo começa por etiquetar a com um zero e os outros
vértices com ∞, i.e L(a) = 0 e L(vi ) = ∞.
• Em cada passo, os vértices em S são aqueles para os quais já é
conhecida a distância mı́nima a partir de a.
• com a condição z 6∈ S, o algoritmo termina quando a distância
mı́nima de a a z for conhecida. Ao substituir a condição z 6∈ S por
V(G) 6= S, o algoritmo termina quando é conhecida a distância
mı́nima de a para os restantes vértices do grafo.
• A instrução if L(u) + w(u, v) < L(v) then L(v) = L(u) + w(u, v)
actualiza L(v), tendo sido assim identificado um percurso mais curto
de a para v.
Algoritmo de Dijkstra
• O algoritmo começa por etiquetar a com um zero e os outros
vértices com ∞, i.e L(a) = 0 e L(vi ) = ∞.
• Em cada passo, os vértices em S são aqueles para os quais já é
conhecida a distância mı́nima a partir de a.
• com a condição z 6∈ S, o algoritmo termina quando a distância
mı́nima de a a z for conhecida. Ao substituir a condição z 6∈ S por
V(G) 6= S, o algoritmo termina quando é conhecida a distância
mı́nima de a para os restantes vértices do grafo.
• A instrução if L(u) + w(u, v) < L(v) then L(v) = L(u) + w(u, v)
actualiza L(v), tendo sido assim identificado um percurso mais curto
de a para v.
Algoritmo de Dijkstra
• O algoritmo começa por etiquetar a com um zero e os outros
vértices com ∞, i.e L(a) = 0 e L(vi ) = ∞.
• Em cada passo, os vértices em S são aqueles para os quais já é
conhecida a distância mı́nima a partir de a.
• com a condição z 6∈ S, o algoritmo termina quando a distância
mı́nima de a a z for conhecida. Ao substituir a condição z 6∈ S por
V(G) 6= S, o algoritmo termina quando é conhecida a distância
mı́nima de a para os restantes vértices do grafo.
• A instrução if L(u) + w(u, v) < L(v) then L(v) = L(u) + w(u, v)
actualiza L(v), tendo sido assim identificado um percurso mais curto
de a para v.
Exemplo 5. Determine o caminho mı́nimo de a para g
S L(a) L(b) L(c) L(d) L(e) L(f) L(g) Caminhos
0 ∞ ∞ ∞ ∞ ∞ ∞
a - 1 2 1 ∞ ∞ ∞ ab, ac, ad
a,b - - 2 1 ∞ ∞ ∞
a,b,d - - 2 - 14 35 ∞ ade, adf
a,b,d,c - - - - 14 35 ∞
a,b,d,c,e - - - - - 35 103 adeg
a,b,d,c,e,f - - - - - - 56 adfg
a,b,d,c,e,f,g - - - - - - -
Exemplo 5. Determine o caminho mı́nimo de a para g
S L(a) L(b) L(c) L(d) L(e) L(f) L(g) Caminhos
0 ∞ ∞ ∞ ∞ ∞ ∞
a - 1 2 1 ∞ ∞ ∞ ab, ac, ad
a,b - - 2 1 ∞ ∞ ∞
a,b,d - - 2 - 14 35 ∞ ade, adf
a,b,d,c - - - - 14 35 ∞
a,b,d,c,e - - - - - 35 103 adeg
a,b,d,c,e,f - - - - - - 56 adfg
a,b,d,c,e,f,g - - - - - - -
Exemplo 5. Determine o caminho mı́nimo de a para g
S L(a) L(b) L(c) L(d) L(e) L(f) L(g) Caminhos
0 ∞ ∞ ∞ ∞ ∞ ∞
a - 1 2 1 ∞ ∞ ∞ ab, ac, ad
a,b - - 2 1 ∞ ∞ ∞
a,b,d - - 2 - 14 35 ∞ ade, adf
a,b,d,c - - - - 14 35 ∞
a,b,d,c,e - - - - - 35 103 adeg
a,b,d,c,e,f - - - - - - 56 adfg
a,b,d,c,e,f,g - - - - - - -
Exemplo 5. Determine o caminho mı́nimo de a para g
S L(a) L(b) L(c) L(d) L(e) L(f) L(g) Caminhos
0 ∞ ∞ ∞ ∞ ∞ ∞
a - 1 2 1 ∞ ∞ ∞ ab, ac, ad
a,b - - 2 1 ∞ ∞ ∞
a,b,d - - 2 - 14 35 ∞ ade, adf
a,b,d,c - - - - 14 35 ∞
a,b,d,c,e - - - - - 35 103 adeg
a,b,d,c,e,f - - - - - - 56 adfg
a,b,d,c,e,f,g - - - - - - -
Exemplo 5. Determine o caminho mı́nimo de a para g
S L(a) L(b) L(c) L(d) L(e) L(f) L(g) Caminhos
0 ∞ ∞ ∞ ∞ ∞ ∞
a - 1 2 1 ∞ ∞ ∞ ab, ac, ad
a,b - - 2 1 ∞ ∞ ∞
a,b,d - - 2 - 14 35 ∞ ade, adf
a,b,d,c - - - - 14 35 ∞
a,b,d,c,e - - - - - 35 103 adeg
a,b,d,c,e,f - - - - - - 56 adfg
a,b,d,c,e,f,g - - - - - - -
Exemplo 5. Determine o caminho mı́nimo de a para g
S L(a) L(b) L(c) L(d) L(e) L(f) L(g) Caminhos
0 ∞ ∞ ∞ ∞ ∞ ∞
a - 1 2 1 ∞ ∞ ∞ ab, ac, ad
a,b - - 2 1 ∞ ∞ ∞
a,b,d - - 2 - 14 35 ∞ ade, adf
a,b,d,c - - - - 14 35 ∞
a,b,d,c,e - - - - - 35 103 adeg
a,b,d,c,e,f - - - - - - 56 adfg
a,b,d,c,e,f,g - - - - - - -
Exemplo 5. Determine o caminho mı́nimo de a para g
S L(a) L(b) L(c) L(d) L(e) L(f) L(g) Caminhos
0 ∞ ∞ ∞ ∞ ∞ ∞
a - 1 2 1 ∞ ∞ ∞ ab, ac, ad
a,b - - 2 1 ∞ ∞ ∞
a,b,d - - 2 - 14 35 ∞ ade, adf
a,b,d,c - - - - 14 35 ∞
a,b,d,c,e - - - - - 35 103 adeg
a,b,d,c,e,f - - - - - - 56 adfg
a,b,d,c,e,f,g - - - - - - -
Exemplo 5. Determine o caminho mı́nimo de a para g
S L(a) L(b) L(c) L(d) L(e) L(f) L(g) Caminhos
0 ∞ ∞ ∞ ∞ ∞ ∞
a - 1 2 1 ∞ ∞ ∞ ab, ac, ad
a,b - - 2 1 ∞ ∞ ∞
a,b,d - - 2 - 14 35 ∞ ade, adf
a,b,d,c - - - - 14 35 ∞
a,b,d,c,e - - - - - 35 103 adeg
a,b,d,c,e,f - - - - - - 56 adfg
a,b,d,c,e,f,g - - - - - - -
Perguntas?
