Componentes conexas

1 / 26
Componentes conexas

Dado um grafo G = (V , E ). Dizemos que dois vértices u e v de

um grafo G = (V , E ) estão na mesma componente conexa se
existe um caminho em G que liga u até v .

1 / 26
Componentes conexas

Dado um grafo G = (V , E ). Dizemos que dois vértices u e v de

um grafo G = (V , E ) estão na mesma componente conexa se
existe um caminho em G que liga u até v .

Dado um grafo G = (V , E ). A relação de pertencer a mesma

componente conexa é transitiva.

1 / 26
Grafos conexos e desconexos

2 / 26
Grafos conexos e desconexos

Dado um grafo G = (V , E ). Dizemos que G é conexo

se G possui uma única componente conexa.

2 / 26
Grafos conexos e desconexos

Dado um grafo G = (V , E ). Dizemos que G é conexo

se G possui uma única componente conexa. Caso contrário G é
dito ser desconexo .

2 / 26
Cortes

3 / 26
Cortes

Dado G = (V , E ) um grafo conexo. Um grafo trivial tem um único

vértice.

3 / 26
Cortes

Dado G = (V , E ) um grafo conexo. Um grafo trivial tem um único

vértice. Um corte de vértices S ⊂ V de G satisfaz que G − S é
desconexo ou trivial.

3 / 26
Cortes

Dado G = (V , E ) um grafo conexo. Um grafo trivial tem um único

vértice. Um corte de vértices S ⊂ V de G satisfaz que G − S é
desconexo ou trivial. Analogamente, um corte de arestas R ⊂ E
de G satisfaz que G − S é desconexo ou trivial. A conectividade
de vértices cv (G) de G é o tamanho |S| = cv (G) do menor corte
de vértices S de G.

3 / 26
Cortes

Dado G = (V , E ) um grafo conexo. Um grafo trivial tem um único

vértice. Um corte de vértices S ⊂ V de G satisfaz que G − S é
desconexo ou trivial. Analogamente, um corte de arestas R ⊂ E
de G satisfaz que G − S é desconexo ou trivial. A conectividade
de vértices cv (G) de G é o tamanho |S| = cv (G) do menor corte
de vértices S de G. A conectividade de arestas ce(G) de G é o
tamanho ce(G) = |R| do menor corte de arestas R de G.

3 / 26
Articulações e pontes

4 / 26
Articulações e pontes

Dado G = (V , E ) um grafo conexo.

4 / 26
Articulações e pontes

Dado G = (V , E ) um grafo conexo. Dizemos que v de V é uma

articulação de G = (V , E ) se G − v é desconexo ou trivial.

4 / 26
Articulações e pontes

Dado G = (V , E ) um grafo conexo. Dizemos que v de V é uma

articulação de G = (V , E ) se G − v é desconexo ou trivial.
Dizemos que e de E é uma ponte de G = (V , E ) se G − e é
desconexo.

4 / 26
Exemplos de articulações e pontes

5 / 26
Exemplos de articulações e pontes

1. Kn com n > 1 só admite cortes de vértices e de arestas de

tamanho n − 1.

5 / 26
Exemplos de articulações e pontes

1. Kn com n > 1 só admite cortes de vértices e de arestas de

tamanho n − 1. E portanto cv (Kn ) = n − 1.

5 / 26
Exemplos de articulações e pontes

1. Kn com n > 1 só admite cortes de vértices e de arestas de

tamanho n − 1. E portanto cv (Kn ) = n − 1.
2. G é um grafo desconexo, se e somente se cv (G) = ce(G) = 0.

5 / 26
Exemplos de articulações e pontes

1. Kn com n > 1 só admite cortes de vértices e de arestas de

tamanho n − 1. E portanto cv (Kn ) = n − 1.
2. G é um grafo desconexo, se e somente se cv (G) = ce(G) = 0.

3. Se δ é o grau mı́nimo de G, então cv (G) ≤ δ e ce(G) ≤ δ.

5 / 26
Exemplos de articulações e pontes

1. Kn com n > 1 só admite cortes de vértices e de arestas de

tamanho n − 1. E portanto cv (Kn ) = n − 1.
2. G é um grafo desconexo, se e somente se cv (G) = ce(G) = 0.

3. Se δ é o grau mı́nimo de G, então cv (G) ≤ δ e ce(G) ≤ δ.

4.

5 / 26
Exemplos de articulações e pontes

1. Kn com n > 1 só admite cortes de vértices e de arestas de

tamanho n − 1. E portanto cv (Kn ) = n − 1.
2. G é um grafo desconexo, se e somente se cv (G) = ce(G) = 0.

3. Se δ é o grau mı́nimo de G, então cv (G) ≤ δ e ce(G) ≤ δ.

4.

5 / 26
Exemplos de articulações e pontes

1. Kn com n > 1 só admite cortes de vértices e de arestas de

tamanho n − 1. E portanto cv (Kn ) = n − 1.
2. G é um grafo desconexo, se e somente se cv (G) = ce(G) = 0.

3. Se δ é o grau mı́nimo de G, então cv (G) ≤ δ e ce(G) ≤ δ.

cv (casinha) = 2,
4.
ce(casinha) = 2.

5 / 26
k-conexo

Definição

6 / 26
k-conexo

Definição
Um grafo G = (V , E ) é k-conexo em vértices

6 / 26
k-conexo

Definição
Um grafo G = (V , E ) é k-conexo em vértices [em arestas]

6 / 26
k-conexo

Definição
Um grafo G = (V , E ) é k-conexo em vértices [em arestas] se
cv (G) ≥ k [ce(G) ≥ k].

6 / 26
k-conexo

Definição
Um grafo G = (V , E ) é k-conexo em vértices [em arestas] se
cv (G) ≥ k [ce(G) ≥ k]. Se G é 2-conexo em vértices

6 / 26
k-conexo

Definição
Um grafo G = (V , E ) é k-conexo em vértices [em arestas] se
cv (G) ≥ k [ce(G) ≥ k]. Se G é 2-conexo em vértices [em
arestas]

6 / 26
k-conexo

Definição
Um grafo G = (V , E ) é k-conexo em vértices [em arestas] se
cv (G) ≥ k [ce(G) ≥ k]. Se G é 2-conexo em vértices [em
arestas] dizemos que G é biconexo em vértices

6 / 26
k-conexo

Definição
Um grafo G = (V , E ) é k-conexo em vértices [em arestas] se
cv (G) ≥ k [ce(G) ≥ k]. Se G é 2-conexo em vértices [em
arestas] dizemos que G é biconexo em vértices [em arestas].

6 / 26
k-conexo

Theorem
G é um grafo conexo, não trivial que não possui articulações, se e
somente se, G é um grafo biconexo em vértices.

Proof.
Suponha G conexo, não trivial e sem articulações. Se G não é
biconexo em vértices, então cv (G) ≤ 1. Se cv (G) = 0, então G é
desconexo, se cv (G) = 1, então G tem uma articulação. Suponha
que G é um grafo biconexo em vértices. Então, cv (G) ≥ 2. Daı́ G
não tem articulações.

7 / 26
k-conexo

Theorem
G é um grafo conexo, não trivial que não possui pontes, se e
somente se, G é um grafo biconexo em arestas.

Proof.
Suponha G conexo, não trivial e sem pontes. Se G não é biconexo
em arestas, então ce(G) ≤ 1. Se ce(G) = 0, então G é desconexo,
se cv (G) = 1, então G tem uma ponte. Suponha que G é um
grafo biconexo em arestas. Então, ce(G) ≥ 2. Daı́ G não tem
pontes.

8 / 26
Busca em largura

9 / 26
Busca em largura
1. Dado um grafo G = (V , E )
e um vértice fonte v ,

9 / 26
Busca em largura
1. Dado um grafo G = (V , E )
e um vértice fonte v ,
2. O algoritmo de busca em
largura explora as arestas
de G para descobrir cada
vértice de G que é atingido
a partir de v .

9 / 26
Busca em largura
1. Dado um grafo G = (V , E )
e um vértice fonte v ,
2. O algoritmo de busca em
largura explora as arestas
de G para descobrir cada
vértice de G que é atingido
a partir de v .
3. Uma árvore de busca em
largura T é produzida que
contem todos os vértices
atingidos a partir de v .

9 / 26
Busca em largura
1. Dado um grafo G = (V , E )
e um vértice fonte v ,
2. O algoritmo de busca em
largura explora as arestas
de G para descobrir cada
vértice de G que é atingido
a partir de v .
3. Uma árvore de busca em
largura T é produzida que
contem todos os vértices
atingidos a partir de v .
4. Para qualquer vértice u
atingido a partir de v , o
caminho na árvore T entre
u e v é um caminho mais
curto entre u e v em G.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E )
e um vértice fonte v ,
2. O algoritmo de busca em
largura explora as arestas
de G para descobrir cada
vértice de G que é atingido
a partir de v .
3. Uma árvore de busca em
largura T é produzida que
contem todos os vértices
atingidos a partir de v .
4. Para qualquer vértice u
atingido a partir de v , o
caminho na árvore T entre
u e v é um caminho mais
curto entre u e v em G.
5. O algoritmo pode ser
implementado em ambos
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
2. O algoritmo de busca em
largura explora as arestas
de G para descobrir cada
vértice de G que é atingido
a partir de v .
3. Uma árvore de busca em
largura T é produzida que
contem todos os vértices
atingidos a partir de v .
4. Para qualquer vértice u
atingido a partir de v , o
caminho na árvore T entre
u e v é um caminho mais
curto entre u e v em G.
5. O algoritmo pode ser
implementado em ambos
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em
largura explora as arestas
de G para descobrir cada
vértice de G que é atingido
a partir de v .
3. Uma árvore de busca em
largura T é produzida que
contem todos os vértices
atingidos a partir de v .
4. Para qualquer vértice u
atingido a partir de v , o
caminho na árvore T entre
u e v é um caminho mais
curto entre u e v em G.
5. O algoritmo pode ser
implementado em ambos
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em
largura explora as arestas
de G para descobrir cada
vértice de G que é atingido
a partir de v .
3. Uma árvore de busca em
largura T é produzida que
contem todos os vértices
atingidos a partir de v .
4. Para qualquer vértice u
atingido a partir de v , o
caminho na árvore T entre
u e v é um caminho mais
curto entre u e v em G.
5. O algoritmo pode ser
implementado em ambos
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em 1.1 [Link] ←Branco;
largura explora as arestas
de G para descobrir cada
vértice de G que é atingido
a partir de v .
3. Uma árvore de busca em
largura T é produzida que
contem todos os vértices
atingidos a partir de v .
4. Para qualquer vértice u
atingido a partir de v , o
caminho na árvore T entre
u e v é um caminho mais
curto entre u e v em G.
5. O algoritmo pode ser
implementado em ambos
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em 1.1 [Link] ←Branco;
largura explora as arestas 1.2 u.d ← ∞;
de G para descobrir cada
vértice de G que é atingido
a partir de v .
3. Uma árvore de busca em
largura T é produzida que
contem todos os vértices
atingidos a partir de v .
4. Para qualquer vértice u
atingido a partir de v , o
caminho na árvore T entre
u e v é um caminho mais
curto entre u e v em G.
5. O algoritmo pode ser
implementado em ambos
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em 1.1 [Link] ←Branco;
largura explora as arestas 1.2 u.d ← ∞;
de G para descobrir cada 1.3 u.p ← NIL;
vértice de G que é atingido
a partir de v .
3. Uma árvore de busca em
largura T é produzida que
contem todos os vértices
atingidos a partir de v .
4. Para qualquer vértice u
atingido a partir de v , o
caminho na árvore T entre
u e v é um caminho mais
curto entre u e v em G.
5. O algoritmo pode ser
implementado em ambos
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em 1.1 [Link] ←Branco;
largura explora as arestas 1.2 u.d ← ∞;
de G para descobrir cada 1.3 u.p ← NIL;
vértice de G que é atingido
2. v .cor ←Cinza;
a partir de v .
3. v .d ← 0;
3. Uma árvore de busca em
largura T é produzida que
contem todos os vértices
atingidos a partir de v .
4. Para qualquer vértice u
atingido a partir de v , o
caminho na árvore T entre
u e v é um caminho mais
curto entre u e v em G.
5. O algoritmo pode ser
implementado em ambos
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em 1.1 [Link] ←Branco;
largura explora as arestas 1.2 u.d ← ∞;
de G para descobrir cada 1.3 u.p ← NIL;
vértice de G que é atingido
2. v .cor ←Cinza;
a partir de v .
3. v .d ← 0;
3. Uma árvore de busca em
largura T é produzida que 4. Q ← ∅;
contem todos os vértices
atingidos a partir de v .
4. Para qualquer vértice u
atingido a partir de v , o
caminho na árvore T entre
u e v é um caminho mais
curto entre u e v em G.
5. O algoritmo pode ser
implementado em ambos
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em 1.1 [Link] ←Branco;
largura explora as arestas 1.2 u.d ← ∞;
de G para descobrir cada 1.3 u.p ← NIL;
vértice de G que é atingido
2. v .cor ←Cinza;
a partir de v .
3. v .d ← 0;
3. Uma árvore de busca em
largura T é produzida que 4. Q ← ∅;
contem todos os vértices
5. Enfile(Q, v );
atingidos a partir de v .
4. Para qualquer vértice u
atingido a partir de v , o
caminho na árvore T entre
u e v é um caminho mais
curto entre u e v em G.
5. O algoritmo pode ser
implementado em ambos
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em 1.1 [Link] ←Branco;
largura explora as arestas 1.2 u.d ← ∞;
de G para descobrir cada 1.3 u.p ← NIL;
vértice de G que é atingido
2. v .cor ←Cinza;
a partir de v .
3. v .d ← 0;
3. Uma árvore de busca em
largura T é produzida que 4. Q ← ∅;
contem todos os vértices
5. Enfile(Q, v );
atingidos a partir de v .
4. Para qualquer vértice u 6. Enquanto Q 6= ∅ faça
atingido a partir de v , o
caminho na árvore T entre
u e v é um caminho mais
curto entre u e v em G.
5. O algoritmo pode ser
implementado em ambos
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em 1.1 [Link] ←Branco;
largura explora as arestas 1.2 u.d ← ∞;
de G para descobrir cada 1.3 u.p ← NIL;
vértice de G que é atingido
2. v .cor ←Cinza;
a partir de v .
3. v .d ← 0;
3. Uma árvore de busca em
largura T é produzida que 4. Q ← ∅;
contem todos os vértices
5. Enfile(Q, v );
atingidos a partir de v .
4. Para qualquer vértice u 6. Enquanto Q 6= ∅ faça
6.1 u ←desenfile(Q);
atingido a partir de v , o
caminho na árvore T entre
u e v é um caminho mais
curto entre u e v em G.
5. O algoritmo pode ser
implementado em ambos
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em 1.1 [Link] ←Branco;
largura explora as arestas 1.2 u.d ← ∞;
de G para descobrir cada 1.3 u.p ← NIL;
vértice de G que é atingido
2. v .cor ←Cinza;
a partir de v .
3. v .d ← 0;
3. Uma árvore de busca em
largura T é produzida que 4. Q ← ∅;
contem todos os vértices
5. Enfile(Q, v );
atingidos a partir de v .
4. Para qualquer vértice u 6. Enquanto Q 6= ∅ faça
6.1 u ←desenfile(Q);
atingido a partir de v , o 6.2 Para cada s ∈ N(u) faça
caminho na árvore T entre
Se [Link] == Branco, então
u e v é um caminho mais
curto entre u e v em G.
5. O algoritmo pode ser
implementado em ambos
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em 1.1 [Link] ←Branco;
largura explora as arestas 1.2 u.d ← ∞;
de G para descobrir cada 1.3 u.p ← NIL;
vértice de G que é atingido
2. v .cor ←Cinza;
a partir de v .
3. v .d ← 0;
3. Uma árvore de busca em
largura T é produzida que 4. Q ← ∅;
contem todos os vértices
5. Enfile(Q, v );
atingidos a partir de v .
4. Para qualquer vértice u 6. Enquanto Q 6= ∅ faça
6.1 u ←desenfile(Q);
atingido a partir de v , o 6.2 Para cada s ∈ N(u) faça
caminho na árvore T entre
Se [Link] == Branco, então
u e v é um caminho mais
6.2.1 [Link] ←Cinza;
curto entre u e v em G.
5. O algoritmo pode ser
implementado em ambos
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em 1.1 [Link] ←Branco;
largura explora as arestas 1.2 u.d ← ∞;
de G para descobrir cada 1.3 u.p ← NIL;
vértice de G que é atingido
2. v .cor ←Cinza;
a partir de v .
3. v .d ← 0;
3. Uma árvore de busca em
largura T é produzida que 4. Q ← ∅;
contem todos os vértices
5. Enfile(Q, v );
atingidos a partir de v .
4. Para qualquer vértice u 6. Enquanto Q 6= ∅ faça
6.1 u ←desenfile(Q);
atingido a partir de v , o 6.2 Para cada s ∈ N(u) faça
caminho na árvore T entre
Se [Link] == Branco, então
u e v é um caminho mais
6.2.1 [Link] ←Cinza;
curto entre u e v em G. 6.2.2 s.d :← u.d + 1;
5. O algoritmo pode ser
implementado em ambos
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em 1.1 [Link] ←Branco;
largura explora as arestas 1.2 u.d ← ∞;
de G para descobrir cada 1.3 u.p ← NIL;
vértice de G que é atingido
2. v .cor ←Cinza;
a partir de v .
3. v .d ← 0;
3. Uma árvore de busca em
largura T é produzida que 4. Q ← ∅;
contem todos os vértices
5. Enfile(Q, v );
atingidos a partir de v .
4. Para qualquer vértice u 6. Enquanto Q 6= ∅ faça
6.1 u ←desenfile(Q);
atingido a partir de v , o 6.2 Para cada s ∈ N(u) faça
caminho na árvore T entre
Se [Link] == Branco, então
u e v é um caminho mais
6.2.1 [Link] ←Cinza;
curto entre u e v em G. 6.2.2 s.d :← u.d + 1;
6.2.3 s.p ← u;
5. O algoritmo pode ser
implementado em ambos
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em 1.1 [Link] ←Branco;
largura explora as arestas 1.2 u.d ← ∞;
de G para descobrir cada 1.3 u.p ← NIL;
vértice de G que é atingido
2. v .cor ←Cinza;
a partir de v .
3. v .d ← 0;
3. Uma árvore de busca em
largura T é produzida que 4. Q ← ∅;
contem todos os vértices
5. Enfile(Q, v );
atingidos a partir de v .
4. Para qualquer vértice u 6. Enquanto Q 6= ∅ faça
6.1 u ←desenfile(Q);
atingido a partir de v , o 6.2 Para cada s ∈ N(u) faça
caminho na árvore T entre
Se [Link] == Branco, então
u e v é um caminho mais
6.2.1 [Link] ←Cinza;
curto entre u e v em G. 6.2.2 s.d :← u.d + 1;
6.2.3 s.p ← u;
5. O algoritmo pode ser
implementado em ambos 6.2.4 Enfile(Q, s);
grafos direcionados ou não
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em 1.1 [Link] ←Branco;
largura explora as arestas 1.2 u.d ← ∞;
de G para descobrir cada 1.3 u.p ← NIL;
vértice de G que é atingido
2. v .cor ←Cinza;
a partir de v .
3. v .d ← 0;
3. Uma árvore de busca em
largura T é produzida que 4. Q ← ∅;
contem todos os vértices
5. Enfile(Q, v );
atingidos a partir de v .
4. Para qualquer vértice u 6. Enquanto Q 6= ∅ faça
6.1 u ←desenfile(Q);
atingido a partir de v , o 6.2 Para cada s ∈ N(u) faça
caminho na árvore T entre
Se [Link] == Branco, então
u e v é um caminho mais
6.2.1 [Link] ←Cinza;
curto entre u e v em G. 6.2.2 s.d :← u.d + 1;
6.2.3 s.p ← u;
5. O algoritmo pode ser
implementado em ambos 6.2.4 Enfile(Q, s);
grafos direcionados ou não 6.3 [Link] ←Preta;
direcionados.

9 / 26
Busca em largura
1. Dado um grafo G = (V , E ) Algoritmo de Busca em Largura
e um vértice fonte v ,
1. Para cada vértice u ∈ G.V − v faça
2. O algoritmo de busca em 1.1 [Link] ←Branco;
largura explora as arestas 1.2 u.d ← ∞;
de G para descobrir cada 1.3 u.p ← NIL;
vértice de G que é atingido
2. v .cor ←Cinza;
a partir de v .
3. v .d ← 0;
3. Uma árvore de busca em
largura T é produzida que 4. Q ← ∅;
contem todos os vértices
5. Enfile(Q, v );
atingidos a partir de v .
4. Para qualquer vértice u 6. Enquanto Q 6= ∅ faça
6.1 u ←desenfile(Q);
atingido a partir de v , o 6.2 Para cada s ∈ N(u) faça
caminho na árvore T entre
Se [Link] == Branco, então
u e v é um caminho mais
6.2.1 [Link] ←Cinza;
curto entre u e v em G. 6.2.2 s.d :← u.d + 1;
6.2.3 s.p ← u;
5. O algoritmo pode ser
implementado em ambos 6.2.4 Enfile(Q, s);
grafos direcionados ou não 6.3 [Link] ←Preta;
direcionados.
7. Retorne(V .p, V .d);

9 / 26
Exemplo de Busca em Largura
Algoritmo de Busca em Largura
e c e c
b g b g 1. Para cada vértice u ∈ G.V − v faça
a a
1.1 [Link] ←Branco;
1.2 u.d ← ∞;
d h d h
f
i
f
i
1.3 u.p ← NIL;
2. v .cor ←Cinza;
a b c d e 3. v .d ← 0;
.p NIL NIL NIL NIL NIL 4. Q ← ∅;
.cor C B B B B
.d 0 +∞ +∞ +∞ +∞ 5. Enfile(Q, v );

6. Enquanto Q 6= ∅ faça
f g h i 6.1 u ←desenfile(Q);
.p NIL NIL NIL NIL 6.2 Para cada s ∈ N(u) faça
.cor B B B B Se [Link] == Branco, então
.d +∞ +∞ +∞ +∞
6.2.1 [Link] ←Cinza;
6.2.2 s.d :← u.d + 1;
u 6.2.3 s.p ← u;
s 6.2.4 Enfile(Q, s);

Q ∅ 6.3 [Link] ←Preta;

7. Retorne(V .p, V .d);

10 / 26
Exemplo de Busca em Largura
Algoritmo de Busca em Largura
e c e c
b g b g 1. Para cada vértice u ∈ G.V − v faça
a a
1.1 [Link] ←Branco;
1.2 u.d ← ∞;
d h d h
f
i
f
i
1.3 u.p ← NIL;
2. v .cor ←Cinza;
a b c d e 3. v .d ← 0;
.p NIL NIL NIL NIL NIL 4. Q ← ∅;
.cor C B B B B
.d 0 +∞ +∞ +∞ +∞ 5. Enfile(Q, v );

6. Enquanto Q 6= ∅ faça
f g h i 6.1 u ←desenfile(Q);
.p NIL NIL NIL NIL 6.2 Para cada s ∈ N(u) faça
.cor B B B B Se [Link] == Branco, então
.d +∞ +∞ +∞ +∞
6.2.1 [Link] ←Cinza;
6.2.2 s.d :← u.d + 1;
u 6.2.3 s.p ← u;
s 6.2.4 Enfile(Q, s);

Q a 6.3 [Link] ←Preta;

7. Retorne(V .p, V .d);

11 / 26
Exemplo de Busca em Largura
Algoritmo de Busca em Largura
e c e c
b g b g 1. Para cada vértice u ∈ G.V − v faça
a a
1.1 [Link] ←Branco;
1.2 u.d ← ∞;
d h d h
f
i
f
i
1.3 u.p ← NIL;
2. v .cor ←Cinza;
a b c d e 3. v .d ← 0;
.p NIL NIL NIL NIL NIL 4. Q ← ∅;
.cor C B B B B
.d 0 +∞ +∞ +∞ +∞ 5. Enfile(Q, v );

6. Enquanto Q 6= ∅ faça
f g h i 6.1 u ←desenfile(Q);
.p NIL NIL NIL NIL 6.2 Para cada s ∈ N(u) faça
.cor B B B B Se [Link] == Branco, então
.d +∞ +∞ +∞ +∞
6.2.1 [Link] ←Cinza;
6.2.2 s.d :← u.d + 1;
u a 6.2.3 s.p ← u;
s b 6.2.4 Enfile(Q, s);

Q a 6.3 [Link] ←Preta;

7. Retorne(V .p, V .d);

12 / 26
Exemplo de Busca em Largura
Algoritmo de Busca em Largura
e c e c
b g b g 1. Para cada vértice u ∈ G.V − v faça
a a
1.1 [Link] ←Branco;
1.2 u.d ← ∞;
d h d h
f
i
f
i
1.3 u.p ← NIL;
2. v .cor ←Cinza;
a b c d e 3. v .d ← 0;
.p NIL a NIL a NIL 4. Q ← ∅;
.cor P C B C B
.d 0 1 +∞ 1 +∞ 5. Enfile(Q, v );

6. Enquanto Q 6= ∅ faça
f g h i 6.1 u ←desenfile(Q);
.p NIL a a NIL 6.2 Para cada s ∈ N(u) faça
.cor B C C B Se [Link] == Branco, então
.d +∞ 1 1 +∞
6.2.1 [Link] ←Cinza;
6.2.2 s.d :← u.d + 1;
u a 6.2.3 s.p ← u;
s b d g h 6.2.4 Enfile(Q, s);

Q abdgh 6.3 [Link] ←Preta;

7. Retorne(V .p, V .d);

13 / 26
Exemplo de Busca em Largura
Algoritmo de Busca em Largura
e c e c
b g b g 1. Para cada vértice u ∈ G.V − v faça
a a
1.1 [Link] ←Branco;
1.2 u.d ← ∞;
d h d h
f
i
f
i
1.3 u.p ← NIL;
2. v .cor ←Cinza;
a b c d e 3. v .d ← 0;
.p NIL a NIL a NIL 4. Q ← ∅;
.cor P C B C B
.d 0 1 +∞ 1 +∞ 5. Enfile(Q, v );

6. Enquanto Q 6= ∅ faça
f g h i 6.1 u ←desenfile(Q);
.p NIL a a NIL 6.2 Para cada s ∈ N(u) faça
.cor B C C B Se [Link] == Branco, então
.d +∞ 1 1 +∞
6.2.1 [Link] ←Cinza;
6.2.2 s.d :← u.d + 1;
u a b 6.2.3 s.p ← u;
s b d g h 6.2.4 Enfile(Q, s);

Q abdgh 6.3 [Link] ←Preta;

7. Retorne(V .p, V .d);

14 / 26
Exemplo de Busca em Largura
Algoritmo de Busca em Largura
e c e c
b g b g 1. Para cada vértice u ∈ G.V − v faça
a a
1.1 [Link] ←Branco;
1.2 u.d ← ∞;
d h d h
f
i
f
i
1.3 u.p ← NIL;
2. v .cor ←Cinza;
a b c d e 3. v .d ← 0;
.p NIL a NIL a b 4. Q ← ∅;
.cor P P B C C
.d 0 1 +∞ 1 2 5. Enfile(Q, v );

6. Enquanto Q 6= ∅ faça
f g h i 6.1 u ←desenfile(Q);
.p NIL a a NIL 6.2 Para cada s ∈ N(u) faça
.cor B C C B Se [Link] == Branco, então
.d +∞ 1 1 +∞
6.2.1 [Link] ←Cinza;
6.2.2 s.d :← u.d + 1;
u a b 6.2.3 s.p ← u;
s b d g h e 6.2.4 Enfile(Q, s);

Q abdghe 6.3 [Link] ←Preta;

7. Retorne(V .p, V .d);

15 / 26
Exemplo de Busca em Largura
Algoritmo de Busca em Largura
e c e c
b g b g 1. Para cada vértice u ∈ G.V − v faça
a a
1.1 [Link] ←Branco;
1.2 u.d ← ∞;
d h d h
f
i
f
i
1.3 u.p ← NIL;
2. v .cor ←Cinza;
a b c d e 3. v .d ← 0;
.p NIL a NIL a b 4. Q ← ∅;
.cor P P B P C
.d 0 1 +∞ 1 2 5. Enfile(Q, v );

6. Enquanto Q 6= ∅ faça
f g h i 6.1 u ←desenfile(Q);
.p d a a NIL 6.2 Para cada s ∈ N(u) faça
.cor C C C B Se [Link] == Branco, então
.d 2 1 1 +∞
6.2.1 [Link] ←Cinza;
6.2.2 s.d :← u.d + 1;
u a b d 6.2.3 s.p ← u;
s b d g h e f 6.2.4 Enfile(Q, s);

Q abdghef 6.3 [Link] ←Preta;

7. Retorne(V .p, V .d);

16 / 26
Exemplo de Busca em Largura
Algoritmo de Busca em Largura
e c e c
b g b g 1. Para cada vértice u ∈ G.V − v faça
a a
1.1 [Link] ←Branco;
1.2 u.d ← ∞;
d h d h
f
i
f
i
1.3 u.p ← NIL;
2. v .cor ←Cinza;
a b c d e 3. v .d ← 0;
.p NIL a g a b 4. Q ← ∅;
.cor P P C P C
.d 0 1 2 1 2 5. Enfile(Q, v );

6. Enquanto Q 6= ∅ faça
f g h i 6.1 u ←desenfile(Q);
.p d a a NIL 6.2 Para cada s ∈ N(u) faça
.cor C P C B Se [Link] == Branco, então
.d 2 1 1 +∞
6.2.1 [Link] ←Cinza;
6.2.2 s.d :← u.d + 1;
u a b d g 6.2.3 s.p ← u;
s b d g h e f c 6.2.4 Enfile(Q, s);

Q abdghefc 6.3 [Link] ←Preta;

7. Retorne(V .p, V .d);

17 / 26
Exemplo de Busca em Largura
Algoritmo de Busca em Largura
e c e c
b g b g 1. Para cada vértice u ∈ G.V − v faça
a a
1.1 [Link] ←Branco;
1.2 u.d ← ∞;
d h d h
f
i
f
i
1.3 u.p ← NIL;
2. v .cor ←Cinza;
a b c d e 3. v .d ← 0;
.p NIL a g a b 4. Q ← ∅;
.cor P P C P C
.d 0 1 2 1 2 5. Enfile(Q, v );

6. Enquanto Q 6= ∅ faça
f g h i 6.1 u ←desenfile(Q);
.p d a a h 6.2 Para cada s ∈ N(u) faça
.cor C P P C Se [Link] == Branco, então
.d 2 1 1 2
6.2.1 [Link] ←Cinza;
6.2.2 s.d :← u.d + 1;
u a b d g h 6.2.3 s.p ← u;
s b d g h e f c i 6.2.4 Enfile(Q, s);

Q abdghefci 6.3 [Link] ←Preta;

7. Retorne(V .p, V .d);

18 / 26
Exemplo de Busca em Largura
Algoritmo de Busca em Largura
e c e c
b g b g 1. Para cada vértice u ∈ G.V − v faça
a a
1.1 [Link] ←Branco;
1.2 u.d ← ∞;
d h d h
f
i
f
i
1.3 u.p ← NIL;
2. v .cor ←Cinza;
a b c d e 3. v .d ← 0;
.p NIL a g a b 4. Q ← ∅;
.cor P P C P P
.d 0 1 2 1 2 5. Enfile(Q, v );

6. Enquanto Q 6= ∅ faça
f g h i 6.1 u ←desenfile(Q);
.p d a a h 6.2 Para cada s ∈ N(u) faça
.cor C P P C Se [Link] == Branco, então
.d 2 1 1 2
6.2.1 [Link] ←Cinza;
6.2.2 s.d :← u.d + 1;
u a b d g h e 6.2.3 s.p ← u;
s b d g h e f c i 6.2.4 Enfile(Q, s);

Q abdghefci 6.3 [Link] ←Preta;

7. Retorne(V .p, V .d);

19 / 26
Exemplo de Busca em Largura
Algoritmo de Busca em Largura
e c e c
b g b g 1. Para cada vértice u ∈ G.V − v faça
a a
1.1 [Link] ←Branco;
1.2 u.d ← ∞;
d h d h
f
i
f
i
1.3 u.p ← NIL;
2. v .cor ←Cinza;
a b c d e 3. v .d ← 0;
.p NIL a g a b 4. Q ← ∅;
.cor P P C P P
.d 0 1 2 1 2 5. Enfile(Q, v );

6. Enquanto Q 6= ∅ faça
f g h i 6.1 u ←desenfile(Q);
.p d a a h 6.2 Para cada s ∈ N(u) faça
.cor P P P C Se [Link] == Branco, então
.d 2 1 1 2
6.2.1 [Link] ←Cinza;
6.2.2 s.d :← u.d + 1;
u a b d g h e 6.2.3 s.p ← u;
s b d g h e f c i 6.2.4 Enfile(Q, s);

Q abdghefci 6.3 [Link] ←Preta;

7. Retorne(V .p, V .d);

20 / 26
Exemplo de Busca em Largura
Algoritmo de Busca em Largura
e c e c
b g b g 1. Para cada vértice u ∈ G.V − v faça
a a
1.1 [Link] ←Branco;
1.2 u.d ← ∞;
d h d h
f
i
f
i
1.3 u.p ← NIL;
2. v .cor ←Cinza;
a b c d e 3. v .d ← 0;
.p NIL a g a b 4. Q ← ∅;
.cor P P P P P
.d 0 1 2 1 2 5. Enfile(Q, v );

6. Enquanto Q 6= ∅ faça
f g h i 6.1 u ←desenfile(Q);
.p d a a h 6.2 Para cada s ∈ N(u) faça
.cor P P P C Se [Link] == Branco, então
.d 2 1 1 2
6.2.1 [Link] ←Cinza;
6.2.2 s.d :← u.d + 1;
u a b d g h e 6.2.3 s.p ← u;
s b d g h e f c i 6.2.4 Enfile(Q, s);

Q abdghefci 6.3 [Link] ←Preta;

7. Retorne(V .p, V .d);

21 / 26
Exemplo de Busca em Largura
Algoritmo de Busca em Largura
e c e c
b g b g 1. Para cada vértice u ∈ G.V − v faça
a a
1.1 [Link] ←Branco;
1.2 u.d ← ∞;
d h d h
f
i
f
i
1.3 u.p ← NIL;
2. v .cor ←Cinza;
a b c d e 3. v .d ← 0;
.p NIL a g a b 4. Q ← ∅;
.cor P P P P P
.d 0 1 2 1 2 5. Enfile(Q, v );

6. Enquanto Q 6= ∅ faça
f g h i 6.1 u ←desenfile(Q);
.p d a a h 6.2 Para cada s ∈ N(u) faça
.cor P P P P Se [Link] == Branco, então
.d 2 1 1 2
6.2.1 [Link] ←Cinza;
6.2.2 s.d :← u.d + 1;
u a b d g h e 6.2.3 s.p ← u;
s b d g h e f c i 6.2.4 Enfile(Q, s);

Q abdghefci 6.3 [Link] ←Preta;

7. Retorne(V .p, V .d);

22 / 26
Pontes versus Articulações

23 / 26
Pontes versus Articulações

Grafo

23 / 26
Pontes versus Articulações

Grafo

cv (G)

23 / 26
Pontes versus Articulações

Grafo

cv (G)

ce(G)

23 / 26
Pontes versus Articulações

Grafo

cv (G)

ce(G)

23 / 26
Pontes versus Articulações

Grafo

valor
cv (G)

ce(G)

23 / 26
Pontes versus Articulações

Grafo

valor certificado
cv (G)

ce(G)

23 / 26
Pontes versus Articulações

Grafo

valor certificado
cv (G)
1

ce(G)

23 / 26
Pontes versus Articulações

Grafo

valor certificado
cv (G)
1 {b}

ce(G)

23 / 26
Pontes versus Articulações

Grafo

valor certificado
cv (G)
1 {b} «articulação»

ce(G)

23 / 26
Pontes versus Articulações

Grafo

valor certificado
cv (G)
1 {b} «articulação»
valor
ce(G)

23 / 26
Pontes versus Articulações

Grafo

valor certificado
cv (G)
1 {b} «articulação»
valor certificado
ce(G)

23 / 26
Pontes versus Articulações

Grafo

valor certificado
cv (G)
1 {b} «articulação»
valor certificado
ce(G) « sem »

23 / 26
Pontes versus Articulações

Grafo

valor certificado
cv (G)
1 {b} «articulação»
valor certificado
ce(G) « sem »

«ponte»

23 / 26
Pontes versus Articulações

Grafo

valor certificado
cv (G)
1 {b} «articulação»
valor certificado
ce(G) « sem »
2
«ponte»

23 / 26
Pontes versus Articulações

Grafo

valor certificado
cv (G)
1 {b} «articulação»
valor certificado
ce(G) « sem »
2 {bc, be}
«ponte»

23 / 26
Pontes versus Articulações

Grafo

valor certificado
cv (G)
1 {b} «articulação»
valor certificado
ce(G) « sem »
2 {bc, be}
«ponte»

23 / 26
Pontes versus Articulações

Grafo

valor certificado valor

cv (G)
1 {b} «articulação»
valor certificado
ce(G) « sem »
2 {bc, be}
«ponte»

23 / 26
Pontes versus Articulações

Grafo

valor certificado valor certificado

cv (G)
1 {b} «articulação»
valor certificado
ce(G) « sem »
2 {bc, be}
«ponte»

23 / 26
Pontes versus Articulações

Grafo

valor certificado valor certificado

cv (G)
1 {b} «articulação» 1
valor certificado
ce(G) « sem »
2 {bc, be}
«ponte»

23 / 26
Pontes versus Articulações

Grafo

valor certificado valor certificado

cv (G)
1 {b} «articulação» 1 {3}
valor certificado
ce(G) « sem »
2 {bc, be}
«ponte»

23 / 26
Pontes versus Articulações

Grafo

valor certificado valor certificado

cv (G)
1 {b} «articulação» 1 {3} «articulação»
valor certificado
ce(G) « sem »
2 {bc, be}
«ponte»

23 / 26
Pontes versus Articulações

Grafo

valor certificado valor certificado

cv (G)
1 {b} «articulação» 1 {3} «articulação»
valor certificado
valor
ce(G) « sem »
2 {bc, be}
«ponte»

23 / 26
Pontes versus Articulações

Grafo

valor certificado valor certificado

cv (G)
1 {b} «articulação» 1 {3} «articulação»
valor certificado
valor certificado
ce(G) « sem »
2 {bc, be}
«ponte»

23 / 26
Pontes versus Articulações

Grafo

valor certificado valor certificado

cv (G)
1 {b} «articulação» 1 {3} «articulação»
valor certificado
valor certificado
ce(G) « sem »
2 {bc, be} « ponte »
«ponte»

23 / 26
Pontes versus Articulações

Grafo

valor certificado valor certificado

cv (G)
1 {b} «articulação» 1 {3} «articulação»
valor certificado
valor certificado
ce(G) « sem »
2 {bc, be} 1 « ponte »
«ponte»

23 / 26
Pontes versus Articulações

Grafo

valor certificado valor certificado

cv (G)
1 {b} «articulação» 1 {3} «articulação»
valor certificado
valor certificado
ce(G) « sem »
2 {bc, be} 1 {34} « ponte »
«ponte»

23 / 26
Ponte ⇒ Articulação
Teorema

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ).

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,
então G tem uma articulação.

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,
então G tem uma articulação.
Prova:

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,
então G tem uma articulação.
Prova: Suponha que G é um grafo
conexo.

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,
então G tem uma articulação.
Prova: Suponha que G é um grafo
conexo. Suponha que G tem uma
ponte uv .

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,
então G tem uma articulação.
Prova: Suponha que G é um grafo
conexo. Suponha que G tem uma
ponte uv . Se G = K2 , então
G tem 2 articulações.

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,
então G tem uma articulação.
Prova: Suponha que G é um grafo
conexo. Suponha que G tem uma
ponte uv . Se G = K2 , então
G tem 2 articulações. Se G não
é o K2 , como G tem pelo menos 1
aresta, então existe pelo menos mais
um vértice w em G.

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,
então G tem uma articulação.
Prova: Suponha que G é um grafo
conexo. Suponha que G tem uma
ponte uv . Se G = K2 , então
G tem 2 articulações. Se G não
é o K2 , como G tem pelo menos 1
aresta, então existe pelo menos mais
um vértice w em G. Como G é
conexo, podemos assumir que w é um
vértice especial,

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,
então G tem uma articulação.
Prova: Suponha que G é um grafo
conexo. Suponha que G tem uma
ponte uv . Se G = K2 , então
G tem 2 articulações. Se G não
é o K2 , como G tem pelo menos 1
aresta, então existe pelo menos mais
um vértice w em G. Como G é
conexo, podemos assumir que w é um
vértice especial, podemos assumir
que wu ∈ E .

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,
então G tem uma articulação.
Prova: Suponha que G é um grafo
conexo. Suponha que G tem uma
ponte uv . Se G = K2 , então
G tem 2 articulações. Se G não
é o K2 , como G tem pelo menos 1
aresta, então existe pelo menos mais
um vértice w em G. Como G é
conexo, podemos assumir que w é um
vértice especial, podemos assumir
que wu ∈ E . Vou mostrar que u
é uma articulação de de G. Vamos
olhar para G − u.

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,
então G tem uma articulação.
Prova: Suponha que G é um grafo Primeiro veja que G − uv tem 2 com-
conexo. Suponha que G tem uma ponentes conexas C 1 contendo u e
ponte uv . Se G = K2 , então C 2 contendo v .
G tem 2 articulações. Se G não
é o K2 , como G tem pelo menos 1
aresta, então existe pelo menos mais
um vértice w em G. Como G é
conexo, podemos assumir que w é um
vértice especial, podemos assumir
que wu ∈ E . Vou mostrar que u
é uma articulação de de G. Vamos
olhar para G − u.

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,
então G tem uma articulação.
Prova: Suponha que G é um grafo Primeiro veja que G − uv tem 2 com-
conexo. Suponha que G tem uma ponentes conexas C 1 contendo u e
ponte uv . Se G = K2 , então C 2 contendo v . Assim, u, w
G tem 2 articulações. Se G não pertencem a C 1 e v pertence a C 2 .
é o K2 , como G tem pelo menos 1
aresta, então existe pelo menos mais
um vértice w em G. Como G é
conexo, podemos assumir que w é um
vértice especial, podemos assumir
que wu ∈ E . Vou mostrar que u
é uma articulação de de G. Vamos
olhar para G − u.

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,
então G tem uma articulação.
Prova: Suponha que G é um grafo Primeiro veja que G − uv tem 2 com-
conexo. Suponha que G tem uma ponentes conexas C 1 contendo u e
ponte uv . Se G = K2 , então C 2 contendo v . Assim, u, w
G tem 2 articulações. Se G não pertencem a C 1 e v pertence a C 2 .
é o K2 , como G tem pelo menos 1 Veja que todos os caminhos que
aresta, então existe pelo menos mais ligam w até v em G usam uv e assim
um vértice w em G. Como G é passam por u.
conexo, podemos assumir que w é um
vértice especial, podemos assumir
que wu ∈ E . Vou mostrar que u
é uma articulação de de G. Vamos
olhar para G − u.

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,
então G tem uma articulação.
Prova: Suponha que G é um grafo Primeiro veja que G − uv tem 2 com-
conexo. Suponha que G tem uma ponentes conexas C 1 contendo u e
ponte uv . Se G = K2 , então C 2 contendo v . Assim, u, w
G tem 2 articulações. Se G não pertencem a C 1 e v pertence a C 2 .
é o K2 , como G tem pelo menos 1 Veja que todos os caminhos que
aresta, então existe pelo menos mais ligam w até v em G usam uv e assim
um vértice w em G. Como G é passam por u. Portanto, em G − u
conexo, podemos assumir que w é um nao existe caminho que ligue w até
vértice especial, podemos assumir v.
que wu ∈ E . Vou mostrar que u
é uma articulação de de G. Vamos
olhar para G − u.

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,
então G tem uma articulação.
Prova: Suponha que G é um grafo Primeiro veja que G − uv tem 2 com-
conexo. Suponha que G tem uma ponentes conexas C 1 contendo u e
ponte uv . Se G = K2 , então C 2 contendo v . Assim, u, w
G tem 2 articulações. Se G não pertencem a C 1 e v pertence a C 2 .
é o K2 , como G tem pelo menos 1 Veja que todos os caminhos que
aresta, então existe pelo menos mais ligam w até v em G usam uv e assim
um vértice w em G. Como G é passam por u. Portanto, em G − u
conexo, podemos assumir que w é um nao existe caminho que ligue w até
vértice especial, podemos assumir v. Assim, u é uma articulação de
que wu ∈ E . Vou mostrar que u G.
é uma articulação de de G. Vamos
olhar para G − u.

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,
então G tem uma articulação.
Prova: Suponha que G é um grafo Primeiro veja que G − uv tem 2 com-
conexo. Suponha que G tem uma ponentes conexas C 1 contendo u e
ponte uv . Se G = K2 , então C 2 contendo v . Assim, u, w
G tem 2 articulações. Se G não pertencem a C 1 e v pertence a C 2 .
é o K2 , como G tem pelo menos 1 Veja que todos os caminhos que
aresta, então existe pelo menos mais ligam w até v em G usam uv e assim
um vértice w em G. Como G é passam por u. Portanto, em G − u
conexo, podemos assumir que w é um nao existe caminho que ligue w até
vértice especial, podemos assumir v. Assim, u é uma articulação de
que wu ∈ E . Vou mostrar que u G. Dessa forma, se G tem uma
é uma articulação de de G. Vamos ponte, então G tem uma articulação.
olhar para G − u.

24 / 26
Ponte ⇒ Articulação
Teorema
Dado um grafo conexo G = (V , E ). Se G tem uma ponte,
então G tem uma articulação.
Prova: Suponha que G é um grafo Primeiro veja que G − uv tem 2 com-
conexo. Suponha que G tem uma ponentes conexas C 1 contendo u e
ponte uv . Se G = K2 , então C 2 contendo v . Assim, u, w
G tem 2 articulações. Se G não pertencem a C 1 e v pertence a C 2 .
é o K2 , como G tem pelo menos 1 Veja que todos os caminhos que
aresta, então existe pelo menos mais ligam w até v em G usam uv e assim
um vértice w em G. Como G é passam por u. Portanto, em G − u
conexo, podemos assumir que w é um nao existe caminho que ligue w até
vértice especial, podemos assumir v. Assim, u é uma articulação de
que wu ∈ E . Vou mostrar que u G. Dessa forma, se G tem uma
é uma articulação de de G. Vamos ponte, então G tem uma articulação.
olhar para G − u.

24 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney)

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova:

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial,

então 0 = cv (G) = ce(G) ≤ δ.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial,

então 0 = cv (G) = ce(G) ≤ δ. Assim,

supomos que G é conexo não trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial,

então 0 = cv (G) = ce(G) ≤ δ. Assim,

supomos que G é conexo não trivial. Seja

v um vértice com grau mı́nimo em G e N(v ) =

{v1 , . . . , vδ }.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial,

então 0 = cv (G) = ce(G) ≤ δ. Assim,

supomos que G é conexo não trivial. Seja

v um vértice com grau mı́nimo em G e N(v ) =

{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v }

é um corte de arestas de G porque G − R tem

o vértice isolado v .

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial,

então 0 = cv (G) = ce(G) ≤ δ. Assim,

supomos que G é conexo não trivial. Seja

v um vértice com grau mı́nimo em G e N(v ) =

{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v }

é um corte de arestas de G porque G − R tem

o vértice isolado v . E pela definição de

ce(G) temos que ce(G) ≤ |R| = δ.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial,

então 0 = cv (G) = ce(G) ≤ δ. Assim,

supomos que G é conexo não trivial. Seja

v um vértice com grau mı́nimo em G e N(v ) =

{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v }

é um corte de arestas de G porque G − R tem

o vértice isolado v . E pela definição de

ce(G) temos que ce(G) ≤ |R| = δ. Va-

mos mostrar agora a primeira desigualdade que

cv (G) ≤ ce(G).

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial,

então 0 = cv (G) = ce(G) ≤ δ. Assim,

supomos que G é conexo não trivial. Seja

v um vértice com grau mı́nimo em G e N(v ) =

{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v }

é um corte de arestas de G porque G − R tem

o vértice isolado v . E pela definição de

ce(G) temos que ce(G) ≤ |R| = δ. Va-

mos mostrar agora a primeira desigualdade que

cv (G) ≤ ce(G). Faremos uma prova por

indução em ce(G) ≥ 0. Se ce(G) = 0, então G

é desconexo ou trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial, Assim cv (G) = 0 e 0 = cv (G) ≤ ce(G) = 0
(Base).
então 0 = cv (G) = ce(G) ≤ δ. Assim,

supomos que G é conexo não trivial. Seja

v um vértice com grau mı́nimo em G e N(v ) =

{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v }

é um corte de arestas de G porque G − R tem

o vértice isolado v . E pela definição de

ce(G) temos que ce(G) ≤ |R| = δ. Va-

mos mostrar agora a primeira desigualdade que

cv (G) ≤ ce(G). Faremos uma prova por

indução em ce(G) ≥ 0. Se ce(G) = 0, então G

é desconexo ou trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial, Assim cv (G) = 0 e 0 = cv (G) ≤ ce(G) = 0
(Base). Suponha que para algum k ≥ 0,
então 0 = cv (G) = ce(G) ≤ δ. Assim, cv (G) ≤ ce(G) (Hipótese de Indução).

supomos que G é conexo não trivial. Seja

v um vértice com grau mı́nimo em G e N(v ) =

{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v }

é um corte de arestas de G porque G − R tem

o vértice isolado v . E pela definição de

ce(G) temos que ce(G) ≤ |R| = δ. Va-

mos mostrar agora a primeira desigualdade que

cv (G) ≤ ce(G). Faremos uma prova por

indução em ce(G) ≥ 0. Se ce(G) = 0, então G

é desconexo ou trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial, Assim cv (G) = 0 e 0 = cv (G) ≤ ce(G) = 0
(Base). Suponha que para algum k ≥ 0,
então 0 = cv (G) = ce(G) ≤ δ. Assim, cv (G) ≤ ce(G) (Hipótese de Indução). Seja
G um grafo com ce(G) = k + 1.
supomos que G é conexo não trivial. Seja

v um vértice com grau mı́nimo em G e N(v ) =

{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v }

é um corte de arestas de G porque G − R tem

o vértice isolado v . E pela definição de

ce(G) temos que ce(G) ≤ |R| = δ. Va-

mos mostrar agora a primeira desigualdade que

cv (G) ≤ ce(G). Faremos uma prova por

indução em ce(G) ≥ 0. Se ce(G) = 0, então G

é desconexo ou trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial, Assim cv (G) = 0 e 0 = cv (G) ≤ ce(G) = 0
(Base). Suponha que para algum k ≥ 0,
então 0 = cv (G) = ce(G) ≤ δ. Assim, cv (G) ≤ ce(G) (Hipótese de Indução). Seja
G um grafo com ce(G) = k + 1. Tome R =
supomos que G é conexo não trivial. Seja {e1 , . . . , ek , ek+1 } um corte de arestas de G.

v um vértice com grau mı́nimo em G e N(v ) =

{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v }

é um corte de arestas de G porque G − R tem

o vértice isolado v . E pela definição de

ce(G) temos que ce(G) ≤ |R| = δ. Va-

mos mostrar agora a primeira desigualdade que

cv (G) ≤ ce(G). Faremos uma prova por

indução em ce(G) ≥ 0. Se ce(G) = 0, então G

é desconexo ou trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial, Assim cv (G) = 0 e 0 = cv (G) ≤ ce(G) = 0
(Base). Suponha que para algum k ≥ 0,
então 0 = cv (G) = ce(G) ≤ δ. Assim, cv (G) ≤ ce(G) (Hipótese de Indução). Seja
G um grafo com ce(G) = k + 1. Tome R =
supomos que G é conexo não trivial. Seja {e1 , . . . , ek , ek+1 } um corte de arestas de G.
Considere H = G −e1 . Pela definição ce(H) = k.
v um vértice com grau mı́nimo em G e N(v ) =

{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v }

é um corte de arestas de G porque G − R tem

o vértice isolado v . E pela definição de

ce(G) temos que ce(G) ≤ |R| = δ. Va-

mos mostrar agora a primeira desigualdade que

cv (G) ≤ ce(G). Faremos uma prova por

indução em ce(G) ≥ 0. Se ce(G) = 0, então G

é desconexo ou trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial, Assim cv (G) = 0 e 0 = cv (G) ≤ ce(G) = 0
(Base). Suponha que para algum k ≥ 0,
então 0 = cv (G) = ce(G) ≤ δ. Assim, cv (G) ≤ ce(G) (Hipótese de Indução). Seja
G um grafo com ce(G) = k + 1. Tome R =
supomos que G é conexo não trivial. Seja {e1 , . . . , ek , ek+1 } um corte de arestas de G.
Considere H = G −e1 . Pela definição ce(H) = k.
v um vértice com grau mı́nimo em G e N(v ) = Pela Hipótese de Indução, cv (H) ≤ ce(H).

{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v }

é um corte de arestas de G porque G − R tem

o vértice isolado v . E pela definição de

ce(G) temos que ce(G) ≤ |R| = δ. Va-

mos mostrar agora a primeira desigualdade que

cv (G) ≤ ce(G). Faremos uma prova por

indução em ce(G) ≥ 0. Se ce(G) = 0, então G

é desconexo ou trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial, Assim cv (G) = 0 e 0 = cv (G) ≤ ce(G) = 0
(Base). Suponha que para algum k ≥ 0,
então 0 = cv (G) = ce(G) ≤ δ. Assim, cv (G) ≤ ce(G) (Hipótese de Indução). Seja
G um grafo com ce(G) = k + 1. Tome R =
supomos que G é conexo não trivial. Seja {e1 , . . . , ek , ek+1 } um corte de arestas de G.
Considere H = G −e1 . Pela definição ce(H) = k.
v um vértice com grau mı́nimo em G e N(v ) = Pela Hipótese de Indução, cv (H) ≤ ce(H).
Tome S = {v1 , . . . , vk } um corte de vértices de
{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v } H.
é um corte de arestas de G porque G − R tem

o vértice isolado v . E pela definição de

ce(G) temos que ce(G) ≤ |R| = δ. Va-

mos mostrar agora a primeira desigualdade que

cv (G) ≤ ce(G). Faremos uma prova por

indução em ce(G) ≥ 0. Se ce(G) = 0, então G

é desconexo ou trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial, Assim cv (G) = 0 e 0 = cv (G) ≤ ce(G) = 0
(Base). Suponha que para algum k ≥ 0,
então 0 = cv (G) = ce(G) ≤ δ. Assim, cv (G) ≤ ce(G) (Hipótese de Indução). Seja
G um grafo com ce(G) = k + 1. Tome R =
supomos que G é conexo não trivial. Seja {e1 , . . . , ek , ek+1 } um corte de arestas de G.
Considere H = G −e1 . Pela definição ce(H) = k.
v um vértice com grau mı́nimo em G e N(v ) = Pela Hipótese de Indução, cv (H) ≤ ce(H).
Tome S = {v1 , . . . , vk } um corte de vértices de
{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v } H. Vamos olhar para G − S.
é um corte de arestas de G porque G − R tem

o vértice isolado v . E pela definição de

ce(G) temos que ce(G) ≤ |R| = δ. Va-

mos mostrar agora a primeira desigualdade que

cv (G) ≤ ce(G). Faremos uma prova por

indução em ce(G) ≥ 0. Se ce(G) = 0, então G

é desconexo ou trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial, Assim cv (G) = 0 e 0 = cv (G) ≤ ce(G) = 0
(Base). Suponha que para algum k ≥ 0,
então 0 = cv (G) = ce(G) ≤ δ. Assim, cv (G) ≤ ce(G) (Hipótese de Indução). Seja
G um grafo com ce(G) = k + 1. Tome R =
supomos que G é conexo não trivial. Seja {e1 , . . . , ek , ek+1 } um corte de arestas de G.
Considere H = G −e1 . Pela definição ce(H) = k.
v um vértice com grau mı́nimo em G e N(v ) = Pela Hipótese de Indução, cv (H) ≤ ce(H).
Tome S = {v1 , . . . , vk } um corte de vértices de
{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v } H. Vamos olhar para G − S. Temos 2
possibilidades:
é um corte de arestas de G porque G − R tem

o vértice isolado v . E pela definição de

ce(G) temos que ce(G) ≤ |R| = δ. Va-

mos mostrar agora a primeira desigualdade que

cv (G) ≤ ce(G). Faremos uma prova por

indução em ce(G) ≥ 0. Se ce(G) = 0, então G

é desconexo ou trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial, Assim cv (G) = 0 e 0 = cv (G) ≤ ce(G) = 0
(Base). Suponha que para algum k ≥ 0,
então 0 = cv (G) = ce(G) ≤ δ. Assim, cv (G) ≤ ce(G) (Hipótese de Indução). Seja
G um grafo com ce(G) = k + 1. Tome R =
supomos que G é conexo não trivial. Seja {e1 , . . . , ek , ek+1 } um corte de arestas de G.
Considere H = G −e1 . Pela definição ce(H) = k.
v um vértice com grau mı́nimo em G e N(v ) = Pela Hipótese de Indução, cv (H) ≤ ce(H).
Tome S = {v1 , . . . , vk } um corte de vértices de
{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v } H. Vamos olhar para G − S. Temos 2
possibilidades:
é um corte de arestas de G porque G − R tem
1. G é desconexo ou trivial.
o vértice isolado v . E pela definição de

ce(G) temos que ce(G) ≤ |R| = δ. Va-

mos mostrar agora a primeira desigualdade que

cv (G) ≤ ce(G). Faremos uma prova por

indução em ce(G) ≥ 0. Se ce(G) = 0, então G

é desconexo ou trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial, Assim cv (G) = 0 e 0 = cv (G) ≤ ce(G) = 0
(Base). Suponha que para algum k ≥ 0,
então 0 = cv (G) = ce(G) ≤ δ. Assim, cv (G) ≤ ce(G) (Hipótese de Indução). Seja
G um grafo com ce(G) = k + 1. Tome R =
supomos que G é conexo não trivial. Seja {e1 , . . . , ek , ek+1 } um corte de arestas de G.
Considere H = G −e1 . Pela definição ce(H) = k.
v um vértice com grau mı́nimo em G e N(v ) = Pela Hipótese de Indução, cv (H) ≤ ce(H).
Tome S = {v1 , . . . , vk } um corte de vértices de
{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v } H. Vamos olhar para G − S. Temos 2
possibilidades:
é um corte de arestas de G porque G − R tem
1. G é desconexo ou trivial. Assim,
o vértice isolado v . E pela definição de cv (G) ≤ k < k + 1 = ce(G).
2. G é conexo não trivial.
ce(G) temos que ce(G) ≤ |R| = δ. Va-

mos mostrar agora a primeira desigualdade que

cv (G) ≤ ce(G). Faremos uma prova por

indução em ce(G) ≥ 0. Se ce(G) = 0, então G

é desconexo ou trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial, Assim cv (G) = 0 e 0 = cv (G) ≤ ce(G) = 0
(Base). Suponha que para algum k ≥ 0,
então 0 = cv (G) = ce(G) ≤ δ. Assim, cv (G) ≤ ce(G) (Hipótese de Indução). Seja
G um grafo com ce(G) = k + 1. Tome R =
supomos que G é conexo não trivial. Seja {e1 , . . . , ek , ek+1 } um corte de arestas de G.
Considere H = G −e1 . Pela definição ce(H) = k.
v um vértice com grau mı́nimo em G e N(v ) = Pela Hipótese de Indução, cv (H) ≤ ce(H).
Tome S = {v1 , . . . , vk } um corte de vértices de
{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v } H. Vamos olhar para G − S. Temos 2
possibilidades:
é um corte de arestas de G porque G − R tem
1. G é desconexo ou trivial. Assim,
o vértice isolado v . E pela definição de cv (G) ≤ k < k + 1 = ce(G).
2. G é conexo não trivial. Nesse caso,
ce(G) temos que ce(G) ≤ |R| = δ. Va- temos que G − S = H − S ∪ {e1 }.
mos mostrar agora a primeira desigualdade que

cv (G) ≤ ce(G). Faremos uma prova por

indução em ce(G) ≥ 0. Se ce(G) = 0, então G

é desconexo ou trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial, Assim cv (G) = 0 e 0 = cv (G) ≤ ce(G) = 0
(Base). Suponha que para algum k ≥ 0,
então 0 = cv (G) = ce(G) ≤ δ. Assim, cv (G) ≤ ce(G) (Hipótese de Indução). Seja
G um grafo com ce(G) = k + 1. Tome R =
supomos que G é conexo não trivial. Seja {e1 , . . . , ek , ek+1 } um corte de arestas de G.
Considere H = G −e1 . Pela definição ce(H) = k.
v um vértice com grau mı́nimo em G e N(v ) = Pela Hipótese de Indução, cv (H) ≤ ce(H).
Tome S = {v1 , . . . , vk } um corte de vértices de
{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v } H. Vamos olhar para G − S. Temos 2
possibilidades:
é um corte de arestas de G porque G − R tem
1. G é desconexo ou trivial. Assim,
o vértice isolado v . E pela definição de cv (G) ≤ k < k + 1 = ce(G).
2. G é conexo não trivial. Nesse caso,
ce(G) temos que ce(G) ≤ |R| = δ. Va- temos que G − S = H − S ∪ {e1 }.
Como H − S é desconexo ou trivial,
mos mostrar agora a primeira desigualdade que temos que G − S tem uma ponte e1 .
cv (G) ≤ ce(G). Faremos uma prova por

indução em ce(G) ≥ 0. Se ce(G) = 0, então G

é desconexo ou trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial, Assim cv (G) = 0 e 0 = cv (G) ≤ ce(G) = 0
(Base). Suponha que para algum k ≥ 0,
então 0 = cv (G) = ce(G) ≤ δ. Assim, cv (G) ≤ ce(G) (Hipótese de Indução). Seja
G um grafo com ce(G) = k + 1. Tome R =
supomos que G é conexo não trivial. Seja {e1 , . . . , ek , ek+1 } um corte de arestas de G.
Considere H = G −e1 . Pela definição ce(H) = k.
v um vértice com grau mı́nimo em G e N(v ) = Pela Hipótese de Indução, cv (H) ≤ ce(H).
Tome S = {v1 , . . . , vk } um corte de vértices de
{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v } H. Vamos olhar para G − S. Temos 2
possibilidades:
é um corte de arestas de G porque G − R tem
1. G é desconexo ou trivial. Assim,
o vértice isolado v . E pela definição de cv (G) ≤ k < k + 1 = ce(G).
2. G é conexo não trivial. Nesse caso,
ce(G) temos que ce(G) ≤ |R| = δ. Va- temos que G − S = H − S ∪ {e1 }.
Como H − S é desconexo ou trivial,
mos mostrar agora a primeira desigualdade que temos que G − S tem uma ponte e1 .
Pelo Teorema prévio G − S tem uma
cv (G) ≤ ce(G). Faremos uma prova por articulação a.
indução em ce(G) ≥ 0. Se ce(G) = 0, então G

é desconexo ou trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial, Assim cv (G) = 0 e 0 = cv (G) ≤ ce(G) = 0
(Base). Suponha que para algum k ≥ 0,
então 0 = cv (G) = ce(G) ≤ δ. Assim, cv (G) ≤ ce(G) (Hipótese de Indução). Seja
G um grafo com ce(G) = k + 1. Tome R =
supomos que G é conexo não trivial. Seja {e1 , . . . , ek , ek+1 } um corte de arestas de G.
Considere H = G −e1 . Pela definição ce(H) = k.
v um vértice com grau mı́nimo em G e N(v ) = Pela Hipótese de Indução, cv (H) ≤ ce(H).
Tome S = {v1 , . . . , vk } um corte de vértices de
{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v } H. Vamos olhar para G − S. Temos 2
possibilidades:
é um corte de arestas de G porque G − R tem
1. G é desconexo ou trivial. Assim,
o vértice isolado v . E pela definição de cv (G) ≤ k < k + 1 = ce(G).
2. G é conexo não trivial. Nesse caso,
ce(G) temos que ce(G) ≤ |R| = δ. Va- temos que G − S = H − S ∪ {e1 }.
Como H − S é desconexo ou trivial,
mos mostrar agora a primeira desigualdade que temos que G − S tem uma ponte e1 .
Pelo Teorema prévio G − S tem uma
cv (G) ≤ ce(G). Faremos uma prova por articulação a. E assim,
{v1 , . . . , vk , a} é um corte de vértices
indução em ce(G) ≥ 0. Se ce(G) = 0, então G
para G e dessa forma,
cv (G) ≤ k + 1 = ce(G).
é desconexo ou trivial.

25 / 26
cv (G) ≤ ce(G) ≤ δ

Teorema
(Teorema de Whitney) Dado um grafo G = (V , E ) e δ o grau
mı́nimo de G. Então, cv (G) ≤ ce(G) ≤ δ.
Prova: Veja que se G é desconexo ou trivial, Assim cv (G) = 0 e 0 = cv (G) ≤ ce(G) = 0
(Base). Suponha que para algum k ≥ 0,
então 0 = cv (G) = ce(G) ≤ δ. Assim, cv (G) ≤ ce(G) (Hipótese de Indução). Seja
G um grafo com ce(G) = k + 1. Tome R =
supomos que G é conexo não trivial. Seja {e1 , . . . , ek , ek+1 } um corte de arestas de G.
Considere H = G −e1 . Pela definição ce(H) = k.
v um vértice com grau mı́nimo em G e N(v ) = Pela Hipótese de Indução, cv (H) ≤ ce(H).
Tome S = {v1 , . . . , vk } um corte de vértices de
{v1 , . . . , vδ }. Assim, R = {v1 v , . . . , vδ v } H. Vamos olhar para G − S. Temos 2
possibilidades:
é um corte de arestas de G porque G − R tem
1. G é desconexo ou trivial. Assim,
o vértice isolado v . E pela definição de cv (G) ≤ k < k + 1 = ce(G).
2. G é conexo não trivial. Nesse caso,
ce(G) temos que ce(G) ≤ |R| = δ. Va- temos que G − S = H − S ∪ {e1 }.
Como H − S é desconexo ou trivial,
mos mostrar agora a primeira desigualdade que temos que G − S tem uma ponte e1 .
Pelo Teorema prévio G − S tem uma
cv (G) ≤ ce(G). Faremos uma prova por articulação a. E assim,
{v1 , . . . , vk , a} é um corte de vértices
indução em ce(G) ≥ 0. Se ce(G) = 0, então G
para G e dessa forma,
cv (G) ≤ k + 1 = ce(G).
é desconexo ou trivial.

25 / 26
Índice Remissivo I

articulação, 12–15
Busca em Largura, 34–57
componente conexa, 1–3
conectividade de arestas ce(G), 7–11
conectividade de vértices cv (G), 7–11
conexo, 4–6
corte de arestas, 7–11
corte de vértices, 7–11
desconexo, 4–6
grafo k-conexo em arestas, 24–31
grafo k-conexo em vértices, 24–31
ponte, 12–15
trivial, 7–11

26 / 26