Slide - Geodésica e Diâmetro - 2022-2

Geod´esica e Diˆametro Definic¸˜ao Dado um grafo G = (V, E) e u, v ∈ V . Uma geod´esica de u, v em G ´e um menor caminho P = (u, v1, v2, ..., vk , v) que liga u at´e v em G. O diˆametro de G ´e o comprimento de sua maior geod´esica. 1 / 15 Exemplo de geod´esica e diˆametro a b c d e f G0 Definic¸˜ao Dado um grafo G = (V , E) e u, v ∈ V . Uma geod´esica de u, v em G ´e um menor caminho g h P = (u, v1, v2, ..., vk , v) que liga u at´e v em G. O diˆametro de G ´e o comprimento de sua maior geod´esica. geod´esic a comprime nto a b c d e f g h a (a) 0 (a,b) 1 (a,c) 1 (a,c,d) 2 (a,c,e) 2 (a,c,d,f) 3 (a,g) 1 (a,g,h) 2 b (b.a) 1 (b) 0 (b,d,c) 2 (b,d) 1 (b.d.c.e) 3 (b,h,f) 2 (b,a,g) 2 (b,h) 1 c (a,c) 1 (c,a,b) 2 (c) 0 (c,d) 1 (c,e) 1 (c,d,f) 2 (c,a,g) 2 (c,a,g,h) 3 d (d,b,a) (d,b) (d,c) (d) (d,c,e) (d,f) (d,b,h,g) (d,b,h) 2 1 1 0 2 1 3 2 e (e,c,a) 2 (e,c,a,b) 3 (e,c) 1 (e,c,d) 2 (e) 0 (e,f) 1 (e,g) 1 (e,f,h) 2 f (f,d,c,a) 3 (f,d,b) 2 (f,d,c) 2 (f,d) 1 (f,e) 1 (f) 0 (f,e,g) 2 (f,h) 1 g (g,a) 1 (g,a,b) 2 (g,a,c) 2 (g,a,c,d) 3 (g,e) 1 (g,e,f) 2 (g) 0 (g,h) 1 h (h,b,a) 2 (h,b) 1 (h,b,a,c) 3 (h,b,d) 2 (h,f,e) 2 (h,f) 1 (h,g) 1 (h) 0 2 / 15 Geod´esica e Diˆametro Definic¸˜ao Dado um grafo G = (V, E) e u, v ∈ V . Uma geod´esica de u, v em G ´e um menor caminho P = (u, v1, v2, ..., vk , v) que liga u at´e v em G. O diˆametro de G ´e o comprimento de sua maior geod´esica. Valores nas classes G Kn Kn1,n2 Pn Sn Cn Wn Qn Diˆametro de G 0, se n = 1 1, se n > 1 se n1 = 1, n2 = 1 se n1 > 1 2, ou n2 > 1 n − 1 1, se n = 1 2, se n > 1 n2 1, se n = 3 2, se n > 3 n Geod´esica que realiza o diˆametro (u1, u2) (u1, u2) (u1, v1, u2) (u1 , . . . , un) (u1, c) (u1, c, u2) (u1 , . . . , un 2) (u1, u2) (u1, c, u3) 00 ... 0 11 . . . 1 3 / 15 Caracterizac¸˜ao dos grafos bipartidos Theorem Um grafo ´e bipartido, se e somente se todos os ciclos s˜ao pares. Prova: (=⇒) Suponha que G ´e um grafo bipar tido. Ent˜ao, se G tem um ciclo impar da forma (x1, x2, x3, . . . , x(n−1), xn, x1), isso significa que x1xn ´e uma aresta ligando v´ertices na mesma partic¸˜ao, o que contraria o fato de G ser bipartido. (⇐=) Suponha que todos os ciclos de G s˜ao pares. Considere o algoritmo: Para cada componente conexa Ci de G fac¸a 1. Selecione vi de Ci, 2. Selecione todos os v´ertices a distˆancia par de v para V2 e todos os v´ertices a distˆancia impar de vi para V1. Retorne(V1, V2); Vamos provar que V1 e V2 s˜ao independentes. Vamos provar que V1 ´e independente, a prova que V2 ´e indepen dente ´e an´aloga. Suponha que existem dois v´ertices de u, w ∈ V1 adja centes isto ´e uw de Ci com u, w de V1. Considere g1[u, v] e g2[w, v] duas geod´esicas de u e v e de w e v. Seja z o ultimo v ´ ´ertice a partir de v na intersec¸˜ao destas duas geod´esicas. Primeiro de tudo |g1(v, z)| = |g2(v, z)|. Afirmamos que a paridade de |g1[z, u]| ´e igual a paridade de |g2[z, v]|. Porque u, w ∈ V1, 1. se |g1[v, z]| ´e par, ent˜ao |g1[z, u]| ´e ´ımpar e |g1[z, w]| ´e ´ımpar. 2. se |g1[v, z]| ´e ´ımpar, ent˜ao |g1[z, u]| ´e par e |g1[z, w]| ´e par. Dos 2 casos, temos um ciclo ´ımpar contendo z, u, w, um absurdo. Logo, (V1, V 2) formam uma partic¸˜ao em conjuntos independentes para G, e G ´e um grafo bipar tido. v z u w 4 / 15 Arvores e Florestas ´ Dado um grafo G = (V, E). Dizemos que G ´e uma floresta se G ´e ac´ıclico. G ´e uma ´arvore se G ´e conexo e ac´ıclico. Dado G = (V, E) uma ´arvore e v ∈ V. Dizemos que v ´e uma folha se d(v) = 1 e que v ´e um v´ertice interno se d(v) > 1. 5 / 15 Arvore ´ ←→ ∃! caminho entre cada par u, v de v´ertices TeoremaG = (V , E) ´e uma ´arvore, se e somente se para todo par u, v ∈ V , existe um unico caminho que liga u at ´ ´e v. Prova: (=⇒) Suponha que G ´e uma ´arvore. Pela definic¸˜ao G ´e ac´ıclico e conexo. Sejam u, v ∈ V . Como G ´e conexo existe P = (u = p0, p1, p2, ..., pr−1, pr = v), ligando u at´e v, que vamos mostrar que ´e unico. ´ Suponha que existe Q = (u = q0, q1, q2, ..., qs−1, qs = v) ligando u at´e v com Q = P. Afirma¸c˜ao 1: Como Q = P, ent˜ao existe um menor inteiro positivo i, 1 ≤ i ≤ r − 1, tal que pi = qi. Afirma¸c˜ao 2: Como Q e P ligam u at´e v, ent˜ao existe um menor inteiro j com i < j, e um menor inteiro k com i < k tal que pj = qk . Assim, existe um ci clo (qi−1, qi, qi+1, . . . , qk , pj−1, pj−2, . . . , pi, pi−1) em G, uma contradic¸˜ao porque G ´e ac´ıclico. Logo, existe um unico caminho em ´ G que liga u at´e v. u=p0p1p2p3pr-1v=pr pi p p p p i-1 j-1 j r-2 u=p0p1p2p3pr-1v=pr p p p p p j-1 j r-2 u=q0q1 i-1 i 6 / 15 Arvore ´ ←→ ∃! caminho entre cada par u, v de v´ertices TeoremaG = (V , E) ´e uma ´arvore, se e somente se para todo par u, v ∈ V , existe um unico caminho que liga u at ´ ´e v. Prova: (⇐=) Suponha que para todo par u, v ∈ V , exista um unico caminho ´ que liga u at´e v. Logo, para todo par u, v ∈ V , existe um caminho que liga u at´e v. Assim, G ´e conexo. Suponha, por um momento que G tem um ciclo C = (v0, v1, v2, . . . , vk−1, vk ) como subgrafo. Ent˜ao cada par de v´ertices vi, vj, i = j, de C tem pelo menos dois caminhos que os ligam em G. Uma contradic¸˜ao. Logo, G ´e ac´ıclico. E portanto, G ´e uma ´arvore. 7 / 15 Se uv ∈ Arvore ´ ⇒ uv ´e uma ponte Teorema Se G = (V, E) ´e uma ´arvore e uv ∈ E, ent˜ao uv ´e uma ponte. Prova: Pelo Teorema pr´evio o caminho P = (u, v) que liga u at´e v ´e unico. ´ Assim, em G − uv n˜ao tem um caminho que liga u at´e v. Portanto, G − uv ´e desconexo. Logo, uv ´e uma ponte. 8 / 15 Arvore ´ ⇒ m = n − 1 Teorema Se G = (V, E) ´e uma ´arvore com n = |V| e m = |E|, ent˜ao m = n − 1. Prova: Suponha que G = (V , E) ´e uma ´arvore, que n = |V | e m = |E|. Prova por induc¸˜ao em n ≥ 1. Se n = 1, ent˜ao o numero de ´ arestas ´e zero. Assim, m = 0 = 1 − 1 = n − 1. (base) Suponha que o Teorema seja verdadeiro para toda ´arvore com n ≥ 1 v´ertices ou menos. (Hip´otese Forte de Induc¸˜ao) Tome uma ´arvore G = (V , E) com |V | = n + 1 v´ertices. Ob serve que n + 1 ≥ 2. Como G ´e conexo, tem que exi stir alguma aresta uv em E. Pelo Teorema pr´evio G − uv tem exatamente 2 componentes conexas C1 e C2. Cada uma dessas componentes tem numero de v ´ ´ertices n1 ≤ n e n2 ≤ n. Pela Hip´otese de Induc¸˜ao temos que os numeros de arestas de ´ C1 e de C2 satisfazem que m1 = n1 − 1 e m2 = n2 − 1. Mais ainda, temos que n + 1 = n1 + n2. E que m = m1 + m2 + 1. E assim, m = (n1−1)+(n2−1)+ 1 = (n1 + n2) − 1 = (n + 1) − 1. 9 / 15 Floresta F ⇒ m = n − cc(F) Teorema Se F = (V, E) ´e uma floresta com n = |V|, m = |E| com cc(F) componentes conexas ent˜ao m = n − cc(F). Proof. Suponha que F = (V, E) ´e uma floresta com n = |V| e m = |E|. Pela definic¸˜ao, F ´e um grafo ac´ıclico. Ent˜ao, cada componente conexa Ci de F ´e ac´ıclica e conexa. Cada componente Ci, i ∈ {1, . . . , cc(F)} ´e uma ´arvore com ni − 1 arestas pelo Teorema pr´evio. Onde n = n1 + . . . + ncc(F). Assim, cc(F) m = i=1 (ni − 1) = m = n − cc(F). 10 / 15 Um v´ertice u n˜ao folha de uma Arvore n ´ ˜ao trivial G ´e uma articulac¸˜ao Teorema Se G = (V, E) ´e uma ´arvore n˜ao trivial e u ∈ V , tal que u n˜ao ´e uma folha, ent˜ao u ´e uma articulac¸˜ao. Prova: Suponha que G = (V, E) ´e uma ´arvore n˜ao trivial e u ∈ V, onde u n˜ao ´e uma folha de G. Note que se u n˜ao ´e uma folha, ent˜ao d(u) ≥ 2. Por isso, o numero de arestas ´ m[G−u] de G − u ´e m[G−u] = |E(G − u)| ≤ |E(G)| − 2 = (n − 1) − 2 = |V(G − u)| − 2 < |V(G − u)| − 1 = n[G−u] − 1. Ou seja mG−u = nG−u − 1. Assim, pelo Teorema anterior, G − u n˜ao ´e uma ´arvore. Portanto, apesar de G − u ser ac´ıclico, G − u n˜ao pode ser conexo. 11 / 15 G = (V, E) Arvore n ´ ˜ao trivial ⇒ ∃ 2 folhas em G . Teorema Se G = (V, E) ´e uma ´arvore n˜ao trivial, ent˜ao existem pelo menos 2 folhas em G. Prova: Suponha que G ´e uma ´arvore n˜ao trivial. Nossa prova ser´a assim: G n˜ao pode ter 0 folhas e G n˜ao pode ter 1 folha. 1. Se G n˜ao tem folhas, ent˜ao para todo v´ertice v ∈ V, d(v) ≥ 2. Assim, 2m =v∈V d(v) ≥ 2n = 2n. Ent˜ao m ≥ n > n − 1. Uma contradic¸˜ao, porque G ´e uma ´arvore. 2. Se G tem 1 folha u, ent˜ao para todo v´ertice v = u ∈ V, d(v) ≥ 2. Assim, 2m = v∈V d(v) = v ∈ V v = u d(v)+ d(u) ≥ 2(n − 1) + 1 = 2n − 1. Ent˜ao m ≥ n −1 2 > n − 1. Uma contradic¸˜ao. . 12 / 15 G = (V, E) conexo ⇒ G tem uma ´arvore geradora Dado um grafo G = (V, E). Dizemos que H ´e um subgrafo gerador de G se H ´e subgrafo de G e V(H) = V(G). Teorema Se G = (V, E) ´e conexo, ent˜ao existe uma ´arvore geradora de G. Prova: Nossa prova ´e um algo ritmo que retorna a ´arvore ger adora Gi de G. 1. G0 ← G; 2. Se G ´e ac´ıclico, ent˜ao Retorne G0; 3. i ← 0; 3. Repita 3.1 Dada ei uma aresta em um ciclo Ci de Gi; 3.2 Gi+1 ← Gi − ei; {Esta operac¸˜ao n˜ao desconecta Gi+1} 3.3 i ← i + 1; At´e Gi ser ac´ıclico; 4. Retorne Gi; Qual o valor exato de i no final da execuc¸˜ao do algoritmo da ´arvore geradora em func¸˜ao de m e n? O Valor de i ser´a igual ao numero de arestas retiradas de ´ G para se obter a ´arvore geradora que ´e m − i = n − 1. Assim, i = m − n + 1. 13 / 15 Exemplo Arvore Geradora ´ a b a b c d c d a b c d e f g h G0 e f g h e f g h a b a b a b a b a b a b c d c d c d c d c d c d G0 G0 G0G1 G0G1 e f g h e f g h e f g h e f e f e f g h a b a b a b g h g h c d c d c d G0G1G2 e f g h e f e f g h g h a b a b a b a b c d c d c d14 / 15c d ´Indice Remissivo I diˆametro, 1 floresta, 5 folha, 5 geod´esica, 1 subgrafo gerador, 13 ´arvore, 5 15 / 15