Slide - Componentes Conexas - 2022-2

Componentes conexas Dado um grafo G = (V, E). Dizemos que dois v´ertices u e v de um grafo G = (V, E) est˜ao na mesma componente conexa se existe um caminho em G que liga u at´e v. Dado um grafo G = (V, E). A relac¸˜ao de pertencer a mesma componente conexa ´e transitiva. 1 / 26 Grafos conexos e desconexos Dado um grafo G = (V, E). Dizemos que G ´e conexo se G possui uma unica componente conexa. ´ Caso contr´ario G ´e dito ser desconexo . 2 / 26 Cortes Dado G = (V, E) um grafo conexo. Um grafo trivial tem um unico ´ v´ertice. Um corte de v´ertices S ⊂ V de G satisfaz que G − S ´e desconexo ou trivial. Analogamente, um corte de arestas R ⊂ E de G satisfaz que G − S ´e desconexo ou trivial. A conectividade de v´ertices cv(G) de G ´e o tamanho |S| = cv(G) do menor corte de v´ertices S de G. A conectividade de arestas ce(G) de G ´e o tamanho ce(G) = |R| do menor corte de arestas R de G. 3 / 26 Articulac¸˜oes e pontes Dado G = (V, E) um grafo conexo. Dizemos que v de V ´e uma articulac¸˜ao de G = (V, E) se G − v ´e desconexo ou trivial. Dizemos que e de E ´e uma ponte de G = (V, E) se G − e ´e desconexo. 4 / 26 Exemplos de articulac¸˜oes e pontes 1. Kn com n > 1 s´o admite cortes de v´ertices e de arestas de tamanho n − 1. E portanto cv(Kn) = n − 1. 2. G ´e um grafo desconexo, se e somente se cv(G) = ce(G) = 0. 3. Se δ ´e o grau m´ınimo de G, ent˜ao cv(G) ≤ δ e ce(G) ≤ δ. 4. 5 / 26 cv(casinha) ce(casinha k-conexo Definic¸˜ao Um grafo G = (V, E) ´e k-conexo em v´ertices [em arestas] se cv(G) ≥ k [ce(G) ≥ k]. Se G ´e 2-conexo em v´ertices [em arestas] dizemos que G ´e biconexo em v´ertices [em arestas]. 6 / 26 k-conexo Theorem G ´e um grafo conexo, n˜ao trivial que n˜ao possui articulac¸˜oes, se e somente se, G ´e um grafo biconexo em v´ertices. Proof. Suponha G conexo, n˜ao trivial e sem articulac¸˜oes. Se G n˜ao ´e biconexo em v´ertices, ent˜ao cv(G) ≤ 1. Se cv(G) = 0, ent˜ao G ´e desconexo, se cv(G) = 1, ent˜ao G tem uma articulac¸˜ao. Suponha que G ´e um grafo biconexo em v´ertices. Ent˜ao, cv(G) ≥ 2. Da´ı G n˜ao tem articulac¸˜oes. 7 / 26 k-conexo Theorem G ´e um grafo conexo, n˜ao trivial que n˜ao possui pontes, se e somente se, G ´e um grafo biconexo em arestas. Proof. Suponha G conexo, n˜ao trivial e sem pontes. Se G n˜ao ´e biconexo em arestas, ent˜ao ce(G) ≤ 1. Se ce(G) = 0, ent˜ao G ´e desconexo, se cv(G) = 1, ent˜ao G tem uma ponte. Suponha que G ´e um grafo biconexo em arestas. Ent˜ao, ce(G) ≥ 2. Da´ı G n˜ao tem pontes. Busca em largura 8 / 26 1. Dado um grafo G = (V , E) e um v´ertice fonte v, 2. O algoritmo de busca em largura explora as arestas de G para descobrir cada v´ertice de G que ´e atingido a partir de v. 3. Uma ´arvore de busca em largura T ´e produzida que contem todos os v´ertices atingidos a partir de v. 4. Para qualquer v´ertice u atingido a partir de v, o caminho na ´arvore T entre u e v ´e um caminho mais curto entre u e v em G. 5. O algoritmo pode ser implementado em ambos grafos direcionados ou n˜ao direcionados. Algoritmo de Busca em Largura 1. Para cada v´ertice u ∈ G.V − v fac¸a 1.1 u.cor ←Branco; 1.2 u.d ← ∞; 1.3 u.p ← NIL; 2. v.cor ←Cinza; 3. v.d ← 0; 4. Q ← ∅; 5. Enfile(Q, v); 6. Enquanto Q = ∅ fac¸a 6.1 u ←desenfile(Q); 6.2 Para cada s ∈ N(u) fac¸a Se s.cor == Branco, ent˜ao 6.2.1 s.cor ←Cinza; 6.2.2 s.d :← u.d + 1; 6.2.3 s.p ← u; 6.2.4 Enfile(Q, s); 6.3 u.cor ←Preta; 7. Retorne(V .p, V .d); 9 / 26 Exemplo de Busca em Largura e c e c b g b g a a d h d h f i f i a b c d e .p NIL NIL NIL NIL NIL .cor C B B B B .d 0 +∞ +∞ +∞ +∞ f g h i .p NIL NIL NIL NIL .cor B B B B .d +∞ +∞ +∞ +∞ u s Algoritmo de Busca em Largura 1. Para cada v´ertice u ∈ G.V − v fac¸a 1.1 u.cor ←Branco; 1.2 u.d ← ∞; 1.3 u.p ← NIL; 2. v.cor ←Cinza; 3. v.d ← 0; 4. Q ← ∅; 5. Enfile(Q, v); 6. Enquanto Q = ∅ fac¸a 6.1 u ←desenfile(Q); 6.2 Para cada s ∈ N(u) fac¸a Se s.cor == Branco, ent˜ao 6.2.1 s.cor ←Cinza; 6.2.2 s.d :← u.d + 1; 6.2.3 s.p ← u; 6.2.4 Enfile(Q, s); 6.3 u.cor ←Preta; 7. Retorne(V .p, V .d); Q ∅ 10 / 26 Exemplo de Busca em Largura e c e c b g b g a a d h d h f i f i a b c d e .p NIL NIL NIL NIL NIL .cor C B B B B .d 0 +∞ +∞ +∞ +∞ f g h i .p NIL NIL NIL NIL .cor B B B B .d +∞ +∞ +∞ +∞ u s Q a Algoritmo de Busca em Largura 1. Para cada v´ertice u ∈ G.V − v fac¸a 1.1 u.cor ←Branco; 1.2 u.d ← ∞; 1.3 u.p ← NIL; 2. v.cor ←Cinza; 3. v.d ← 0; 4. Q ← ∅; 5. Enfile(Q, v); 6. Enquanto Q = ∅ fac¸a 6.1 u ←desenfile(Q); 6.2 Para cada s ∈ N(u) fac¸a Se s.cor == Branco, ent˜ao 6.2.1 s.cor ←Cinza; 6.2.2 s.d :← u.d + 1; 6.2.3 s.p ← u; 6.2.4 Enfile(Q, s); 6.3 u.cor ←Preta; 7. Retorne(V .p, V .d); 11 / 26 Exemplo de Busca em Largura e c e c b g b g a a d h d h f i f i a b c d e .p NIL NIL NIL NIL NIL .cor C B B B B .d 0 +∞ +∞ +∞ +∞ f g h i .p NIL NIL NIL NIL .cor B B B B .d +∞ +∞ +∞ +∞ u a s b Q a Algoritmo de Busca em Largura 1. Para cada v´ertice u ∈ G.V − v fac¸a 1.1 u.cor ←Branco; 1.2 u.d ← ∞; 1.3 u.p ← NIL; 2. v.cor ←Cinza; 3. v.d ← 0; 4. Q ← ∅; 5. Enfile(Q, v); 6. Enquanto Q = ∅ fac¸a 6.1 u ←desenfile(Q); 6.2 Para cada s ∈ N(u) fac¸a Se s.cor == Branco, ent˜ao 6.2.1 s.cor ←Cinza; 6.2.2 s.d :← u.d + 1; 6.2.3 s.p ← u; 6.2.4 Enfile(Q, s); 6.3 u.cor ←Preta; 7. Retorne(V .p, V .d); 12 / 26 Exemplo de Busca em Largura e c e c b g b g a a d h d h f i f i a b c d e .p NIL a NIL a NIL .cor P C B C B .d 0 1 +∞ 1 +∞ f g h i .p NIL a a NIL .cor B C C B .d +∞ 1 1 +∞ u a s b d g h Algoritmo de Busca em Largura 1. Para cada v´ertice u ∈ G.V − v fac¸a 1.1 u.cor ←Branco; 1.2 u.d ← ∞; 1.3 u.p ← NIL; 2. v.cor ←Cinza; 3. v.d ← 0; 4. Q ← ∅; 5. Enfile(Q, v); 6. Enquanto Q = ∅ fac¸a 6.1 u ←desenfile(Q); 6.2 Para cada s ∈ N(u) fac¸a Se s.cor == Branco, ent˜ao 6.2.1 s.cor ←Cinza; 6.2.2 s.d :← u.d + 1; 6.2.3 s.p ← u; 6.2.4 Enfile(Q, s); 6.3 u.cor ←Preta; 7. Retorne(V .p, V .d); Q abdgh 13 / 26 Exemplo de Busca em Largura e c e c b g b g a a d h d h f i f i a b c d e .p NIL a NIL a NIL .cor P C B C B .d 0 1 +∞ 1 +∞ f g h i .p NIL a a NIL .cor B C C B .d +∞ 1 1 +∞ u a b s b d g h Q abdgh Algoritmo de Busca em Largura 1. Para cada v´ertice u ∈ G.V − v fac¸a 1.1 u.cor ←Branco; 1.2 u.d ← ∞; 1.3 u.p ← NIL; 2. v.cor ←Cinza; 3. v.d ← 0; 4. Q ← ∅; 5. Enfile(Q, v); 6. Enquanto Q = ∅ fac¸a 6.1 u ←desenfile(Q); 6.2 Para cada s ∈ N(u) fac¸a Se s.cor == Branco, ent˜ao 6.2.1 s.cor ←Cinza; 6.2.2 s.d :← u.d + 1; 6.2.3 s.p ← u; 6.2.4 Enfile(Q, s); 6.3 u.cor ←Preta; 7. Retorne(V .p, V .d); 14 / 26 Exemplo de Busca em Largura e c e c b g b g a a d h d h f i f i a b c d e .p NIL a NIL a b .cor P P B C C .d 0 1 +∞ 1 2 f g h i .p NIL a a NIL .cor B C C B .d +∞ 1 1 +∞ u a b s b d g h e Q abdghe Algoritmo de Busca em Largura 1. Para cada v´ertice u ∈ G.V − v fac¸a 1.1 u.cor ←Branco; 1.2 u.d ← ∞; 1.3 u.p ← NIL; 2. v.cor ←Cinza; 3. v.d ← 0; 4. Q ← ∅; 5. Enfile(Q, v); 6. Enquanto Q = ∅ fac¸a 6.1 u ←desenfile(Q); 6.2 Para cada s ∈ N(u) fac¸a Se s.cor == Branco, ent˜ao 6.2.1 s.cor ←Cinza; 6.2.2 s.d :← u.d + 1; 6.2.3 s.p ← u; 6.2.4 Enfile(Q, s); 6.3 u.cor ←Preta; 7. Retorne(V .p, V .d); 15 / 26 Exemplo de Busca em Largura e c e c b g b g a a d h d h f i f i a b c d e .p NIL a NIL a b .cor P P B P C .d 0 1 +∞ 1 2 f g h i .p d a a NIL .cor C C C B .d 2 1 1 +∞ u a b d Algoritmo de Busca em Largura 1. Para cada v´ertice u ∈ G.V − v fac¸a 1.1 u.cor ←Branco; 1.2 u.d ← ∞; 1.3 u.p ← NIL; 2. v.cor ←Cinza; 3. v.d ← 0; 4. Q ← ∅; 5. Enfile(Q, v); 6. Enquanto Q = ∅ fac¸a 6.1 u ←desenfile(Q); 6.2 Para cada s ∈ N(u) fac¸a Se s.cor == Branco, ent˜ao 6.2.1 s.cor ←Cinza; 6.2.2 s.d :← u.d + 1; 6.2.3 s.p ← u; 6.2.4 Enfile(Q, s); 6.3 u.cor ←Preta; s b d g h e f Q abdghef 7. Retorne(V .p, V .d); 16 / 26 Exemplo de Busca em Largura e c e c b g b g a a d h d h f i f i a b c d e .p NIL a g a b .cor P P C P C .d 0 1 2 1 2 f g h i .p d a a NIL .cor C P C B .d 2 1 1 +∞ u a b d g s b d g h e f c Q abdghefc Algoritmo de Busca em Largura 1. Para cada v´ertice u ∈ G.V − v fac¸a 1.1 u.cor ←Branco; 1.2 u.d ← ∞; 1.3 u.p ← NIL; 2. v.cor ←Cinza; 3. v.d ← 0; 4. Q ← ∅; 5. Enfile(Q, v); 6. Enquanto Q = ∅ fac¸a 6.1 u ←desenfile(Q); 6.2 Para cada s ∈ N(u) fac¸a Se s.cor == Branco, ent˜ao 6.2.1 s.cor ←Cinza; 6.2.2 s.d :← u.d + 1; 6.2.3 s.p ← u; 6.2.4 Enfile(Q, s); 6.3 u.cor ←Preta; 7. Retorne(V .p, V .d); 17 / 26 Exemplo de Busca em Largura e c e c b g b g a a d h d h f i f i a b c d e .p NIL a g a b .cor P P C P C .d 0 1 2 1 2 f g h i .p d a a h .cor C P P C .d 2 1 1 2 u a b d g h s b d g h e f c i Q abdghefci Algoritmo de Busca em Largura 1. Para cada v´ertice u ∈ G.V − v fac¸a 1.1 u.cor ←Branco; 1.2 u.d ← ∞; 1.3 u.p ← NIL; 2. v.cor ←Cinza; 3. v.d ← 0; 4. Q ← ∅; 5. Enfile(Q, v); 6. Enquanto Q = ∅ fac¸a 6.1 u ←desenfile(Q); 6.2 Para cada s ∈ N(u) fac¸a Se s.cor == Branco, ent˜ao 6.2.1 s.cor ←Cinza; 6.2.2 s.d :← u.d + 1; 6.2.3 s.p ← u; 6.2.4 Enfile(Q, s); 6.3 u.cor ←Preta; 7. Retorne(V .p, V .d); 18 / 26 Exemplo de Busca em Largura e c e c b g b g a a d h d h f i f i a b c d e .p NIL a g a b .cor P P C P P .d 0 1 2 1 2 f g h i .p d a a h .cor C P P C .d 2 1 1 2 u a b d g h e Algoritmo de Busca em Largura 1. Para cada v´ertice u ∈ G.V − v fac¸a 1.1 u.cor ←Branco; 1.2 u.d ← ∞; 1.3 u.p ← NIL; 2. v.cor ←Cinza; 3. v.d ← 0; 4. Q ← ∅; 5. Enfile(Q, v); 6. Enquanto Q = ∅ fac¸a 6.1 u ←desenfile(Q); 6.2 Para cada s ∈ N(u) fac¸a Se s.cor == Branco, ent˜ao 6.2.1 s.cor ←Cinza; 6.2.2 s.d :← u.d + 1; 6.2.3 s.p ← u; 6.2.4 Enfile(Q, s); 6.3 u.cor ←Preta; s b d g h e f c i Q abdghefci 7. Retorne(V .p, V .d); 19 / 26 Exemplo de Busca em Largura e c e c b g b g a a d h d h f i f i a b c d e .p NIL a g a b .cor P P C P P .d 0 1 2 1 2 f g h i .p d a a h .cor P P P C .d 2 1 1 2 u a b d g h e s b d g h e f c i Q abdghefci Algoritmo de Busca em Largura 1. Para cada v´ertice u ∈ G.V − v fac¸a 1.1 u.cor ←Branco; 1.2 u.d ← ∞; 1.3 u.p ← NIL; 2. v.cor ←Cinza; 3. v.d ← 0; 4. Q ← ∅; 5. Enfile(Q, v); 6. Enquanto Q = ∅ fac¸a 6.1 u ←desenfile(Q); 6.2 Para cada s ∈ N(u) fac¸a Se s.cor == Branco, ent˜ao 6.2.1 s.cor ←Cinza; 6.2.2 s.d :← u.d + 1; 6.2.3 s.p ← u; 6.2.4 Enfile(Q, s); 6.3 u.cor ←Preta; 7. Retorne(V .p, V .d); 20 / 26 Exemplo de Busca em Largura e c e c b g b g a a d h d h f i f i a b c d e .p NIL a g a b .cor P P P P P .d 0 1 2 1 2 f g h i .p d a a h .cor P P P C .d 2 1 1 2 u a b d g h e s b d g h e f c i Q abdghefci Algoritmo de Busca em Largura 1. Para cada v´ertice u ∈ G.V − v fac¸a 1.1 u.cor ←Branco; 1.2 u.d ← ∞; 1.3 u.p ← NIL; 2. v.cor ←Cinza; 3. v.d ← 0; 4. Q ← ∅; 5. Enfile(Q, v); 6. Enquanto Q = ∅ fac¸a 6.1 u ←desenfile(Q); 6.2 Para cada s ∈ N(u) fac¸a Se s.cor == Branco, ent˜ao 6.2.1 s.cor ←Cinza; 6.2.2 s.d :← u.d + 1; 6.2.3 s.p ← u; 6.2.4 Enfile(Q, s); 6.3 u.cor ←Preta; 7. Retorne(V .p, V .d); 21 / 26 Exemplo de Busca em Largura e c e c b g b g a a d h d h f i f i a b c d e .p NIL a g a b .cor P P P P P .d 0 1 2 1 2 f g h i .p d a a h .cor P P P P .d 2 1 1 2 u a b d g h e Algoritmo de Busca em Largura 1. Para cada v´ertice u ∈ G.V − v fac¸a 1.1 u.cor ←Branco; 1.2 u.d ← ∞; 1.3 u.p ← NIL; 2. v.cor ←Cinza; 3. v.d ← 0; 4. Q ← ∅; 5. Enfile(Q, v); 6. Enquanto Q = ∅ fac¸a 6.1 u ←desenfile(Q); 6.2 Para cada s ∈ N(u) fac¸a Se s.cor == Branco, ent˜ao 6.2.1 s.cor ←Cinza; 6.2.2 s.d :← u.d + 1; 6.2.3 s.p ← u; 6.2.4 Enfile(Q, s); 6.3 u.cor ←Preta; s b d g h e f c i Q abdghefci 7. Retorne(V .p, V .d); 22 / 26 Pontes versus Articulac¸˜oes Grafo cv(G) valor 1 certificado {b} «articulac¸˜ao» valor 1 certificado {3} «articulac¸˜ao» ce(G) valor 2 certificado {bc, be}« sem » «ponte» valor certificado 1 {34}« ponte » 23 / 26 Ponte ⇒ Articulac¸˜ao Teorema Dado um grafo conexo G = (V, E). Se G tem uma ponte, ent˜ao G tem uma articulac¸˜ao. Prova: Suponha que G ´e um grafo conexo. Suponha que G tem uma ponte uv. Se G = K2, ent˜ao G tem 2 articulac¸˜oes. Se G n˜ao ´e o K2, como G tem pelo menos 1 aresta, ent˜ao existe pelo menos mais um v´ertice w em G. Como G ´e conexo, podemos assumir que w ´e um v´ertice especial, podemos assumir que wu ∈ E. Vou mostrar que u ´e uma articulac¸˜ao de de G. Vamos olhar para G − u. Primeiro veja que G −uv tem 2 com ponentes conexas C1 contendo u e C2 contendo v. Assim, u, w pertencem a C1 e v pertence a C2. Veja que todos os caminhos que ligam w at´e v em G usam uv e assim passam por u. Portanto, em G − u nao existe caminho que ligue w at´e v. Assim, u ´e uma articulac¸˜ao de G. Dessa forma, se G tem uma ponte, ent˜ao G tem uma articulac¸˜ao. 24 / 26 cv(G) ≤ ce(G) ≤ δ Teorema (Teorema de Whitney) Dado um grafo G = (V, E) e δ o grau m´ınimo de G. Ent˜ao, cv(G) ≤ ce(G) ≤ δ. Prova: Veja que se G ´e desconexo ou trivial, ent˜ao 0 = cv(G) = ce(G) ≤ δ. Assim, supomos que G ´e conexo n˜ao trivial. Seja v um v´ertice com grau m´ınimo em G e N(v) = {v1, . . . , vδ}. Assim, R = {v1v, . . . , vδv} ´e um corte de arestas de G porque G − R tem o v´ertice isolado v. E pela definic¸˜ao de ce(G) temos que ce(G) ≤ |R| = δ. Va mos mostrar agora a primeira desigualdade que cv(G) ≤ ce(G). Faremos uma prova por induc¸˜ao em ce(G) ≥ 0. Se ce(G) = 0, ent˜ao G ´e desconexo ou trivial. Assim cv(G) = 0 e 0 = cv(G) ≤ ce(G) = 0 (Base). Suponha que para algum k ≥ 0, cv(G) ≤ ce(G) (Hip´otese de Induc¸˜ao). Seja G um grafo com ce(G) = k + 1. Tome R = {e1, . . . , ek, ek+1} um corte de arestas de G. Considere H = G−e1. Pela definic¸˜ao ce(H) = k. Pela Hip´otese de Induc¸˜ao, cv(H) ≤ ce(H). Tome S = {v1, . . . , vk} um corte de v´ertices de H. Vamos olhar para G − S. Temos 2 possibilidades: 1. G ´e desconexo ou trivial. Assim, cv(G) ≤ k < k + 1 = ce(G). 2. G ´e conexo n˜ao trivial. Nesse caso, temos que G − S = H − S ∪ {e1}. Como H − S ´e desconexo ou trivial, temos que G − S tem uma ponte e1. Pelo Teorema pr´evio G − S tem uma articulac¸˜ao a. E assim, {v1, . . . , vk, a} ´e um corte de v´ertices para G e dessa forma, cv(G) ≤ k + 1 = ce(G). 25 / 26 ´Indice Remissivo I articulac¸˜ao, 4 Busca em Largura, 9 componente conexa, 1 conectividade de arestas ce(G), 3 conectividade de v´ertices cv(G), 3 conexo, 2 corte de arestas, 3 corte de v´ertices, 3 desconexo, 2 grafo k-conexo em arestas, 6 grafo k-conexo em v´ertices, 6 ponte, 4 trivial, 3 26 / 26