Teoria dos Grafos - Conectividade 

---

Definições Auxiliares

Passeio

Um passeio P de  v₀  a v_n  , é uma sequência finita e não vazia ( v₀ , ₁, v₁ , ₂ , v₂, ......,_n,  v_n  ), cujos elementos são alternadamente vértices e arestas de um grafo G, e tal que _i = (v_i-1, v_i). para  1 i n .
Passeio degenerado: Quando n = 0. /*Passeio com um único vértice*/
Passeio fechado: Quando n > 0 e v₀ = v_n . /* Começa e termina no mesmo vértice */
Comprimento do passeio = n  /* Total de arestas no passeio */

Dado o grafo Touro, um exemplo de passeio é a,(ab),b,(bc),c,(cd),d,(db),b,(bc),c,(cb),b.
Um passeio fechado poderia ser: a(ab)b(bd)d(db)b(ba)a  /* Começa e termina em a */

Dados dois passeios P = (v₀,(v_0,v₁),v₁,(v_1,v₂),...,(v_n-1,v_n),v^_n) e Q = (w_0,(w₀,w₁),w₁,(w₁,w₂),...,(w_m-1,w_m),w_m) tais que v_n = w₀, definimos PQ como sendo a justaposição do caminho P e Q. /* Acrescentamos o passeio Q "na frente" de P */

Trilha

Passeio em que as arestas são duas a duas distintas. (vertices podem ser repetidos)
Ex: (ainda no grafo Touro):  a,(a,b),b,(b,c),c,(c,d),d,(d,b),b
Trilha Fechada:  começa e termina no mesmo vértice.

Caminho

Trilha em que os vértices são dois a dois distintos. (e consequentemente as arestas)
(Não repete arestas nem vértices)

Dados dois vértices u e v de um grafo qualquer G, denomina-se caminho mínimo de u a v, o menor caminho, em G, ligando u a v.

Grafo Caminho - Pn

Grafo simples em que existe um caminho que passa por todos os vértices de G
 

P2	P3	P4	P5

Ciclo ou Circuito

Trilha fechada em que v₁,...,v_n-1 são dois a dois distintos. Note que, informalmente, poderiamos dizer que um ciclo é simplesmente um caminho fechado, mas então teríamos um problema com a definição de caminho, pois, um caminho não pode ter vértices repetidos.

Grafo simples em que existe um ciclo que passa por todos os vértices de G
 
 

C3	C4	C5	C6

Passeios em grafos simples

Em um grafo simples qualquer tipo de passeio pode ser representado apenas pelos vértices, uma vez que existe no máximo uma aresta ligando dois vértices.

Alguns Teoremas

Qualquer caminho "contido" em um caminho mínimo é também  mínimo

Teorema:

Seja P = ( u₀,u_1,...,u_n ) um caminho mínimo de u_o a u_n.
Então, o caminho Q =  (u_i,u_i+1,....,u_i+m ),  i0 e  i + m n, é um   caminho mínimo de  u_i a u_i+m

Prova:

Seja:

P = ( u₀,u_1,...,u_n ) um caminho mínimo de u_o a u_n  e
S = (u_i,u_i+1,....,u_i+k ),  0in  e   i + k n.

Vamos supor, por absurdo, que  S não seja um caminho mínimo  de u_i  a  u_i+k  ^.
LogoS'=(v₀,v₁,....,v_m ) ,v₀=u_i e  v_m =u_i+k  tal que, | S'| <| S |
Sejam R= ( u₀,...,u_i ) e T=(u_i+k,....,u_n ). Temos então que

| P |  = | R | + | S | + | T |

O passeio P'=( u₀,...,u_i , v₁,....,v_m , u_i+k+1  , .....,   u_n ) ,
ligando u₀ a u_n , existe, e tem comprimento igual a | R | + | S'| + | T |.
Como | S' | < | S | temos que | P' | < | P |.
Como  | P' | é um passeio e como todo passeio possui um caminho C' que tem comprimento menor que o comprimento do passeio (demonstrar), temos que | C'| <| P'|  , como
| P' | < | P |  e | C'| <| P'| , entao | C'| < | P |.
Absurdo, visto que P é um caminho mínimo.

Todo passeio contém um caminho

Teorema: Se  um passeio P de uv , então um caminho C de u v.

Demonstração: (exercício)

Sejam G um grafo e u, v dois vértices de G.
Dizemos que  u e v  são ligados, ou conectados, sse um caminho C de u a v em G.
 

Ligados: v1e v3, v3 e v4,                v6 e v8, v7 e v8     Não Ligados:v1e v6,                v7 e v4

Lema: Ligação é uma relação de equivalência sobre VG

Revisão: Um relação é de equivalência sse ela é reflexiva, simétrica e transitiva.

Demonstração:

Seja G um grafo qualquer com o conjunto VG de vértices e a relação L, de ligação, sobre este conjunto.

L é Reflexiva,  pois para todo vVG, o passeio degenerado <v> que é um caminho de v em v, e portanto: v é ligado a v.

L é Simétrica,  pois para todo  vVG, se um caminho C = < v₀  , v₁ , ......., v_n >, com u=v₀  e v_n  =v, ligando u a v então um Caminho C' = < v_n  , v_{n -1} , ..., v₀  > ligando v a u.

L é Transitiva,  pois para todo u, v, w VG temos , se um caminho P de uv e um caminho Q  de vw então existe um um passeio de uw. Demonstraremos essa afirmação da seguinte forma:

Sejam os caminhos

P = (u₀, ₁, u₁, ....., _p, u_p) ,  com u₀ = u e u_p = v.    e
Q = ( v₀, ₁, v₁,..., _q,v_q ) , com v₀ = v e v_q = w.

Seja i o menor inteiro tal que u_i = v_j ,  0  j q   e   0  i  p.

Temos então que  P₁ = (u₀,₁,  u₁,₂,...., _i, u_i ) é um caminho de u₀ a u_i  e
Q₁ = (v_j,v_j+1,...,v_q) é um caminho de v_j a v_q

Portanto, C = P₁Q₁ é um caminho de u a w. (Lembre-se que u₀ = u e  u_i = v_j e v_q = w.)

 

Teorema: Ligação induz Partição

Como toda relação de equivalência em um conjunto C induz uma partição nesse mesmo conjunto, a relação de ligação em VG induz uma partição em VG.

A partição induzida pela ligação é formada pelos conjunto V₁,V₂ ,... , V_k definidos por:
V_i = { u_j | u_i e u_j são ligados } , 1 i  k.
Para demonstrar que esses conjuntos formam uma partição, basta mostrar que:

V_i ,  1  i  k
U_Vi = VG
V_i V_j = ,  1  i , j k

Grafos Conexos

Dada a partição { V₁,V₂,...,V_k }, induzida pela relação de ligação sobre os vértices de um grafo G. Dizemos que os subgrafos induzidos G[V₁], G[V₂] , ... , [V_k]  são componentes conexos de G.

Indicamos por C(G) o número de componentes conexos de G.

Dizemos que um grafo é conexo quando C(G) = 1, caso contrário, o grafo é dito desconexo.

Obs. Não são somentes os grafos completos que possuem  1 componente
conexo, exemplo
  Partição:{1,2,3,4}
C(G)=1
 

Teorema:  Se G é conexo então quaisquer 2 caminhos de comprimento máximo em G tem um vértice em comum.

Demonstração: (Exercício)

 Problema: Demonstrar que, em qualquer grupo de 2 ou mais pessoas, sempre existem 2 com o mesmo número de amigos.

Modelando o problema para teoria dos grafos, temos:

VG: Grupo de pessoas, | VG| 2
AG: Relação de amizade

Teorema: para qualquer grafo simples pelo menos 2 vértices x,y tais que gr(x)=gr(y)

Prova:

Caso 1 :

Não existe componente conexa C com | V(C) | > 1
Temos então que C é um grafo vazio com pelo menos 2 vértices.
Logo, 2 vértices x,y tais que gr(x) = gr(y) {Grau(x)=0=Grau(y)}
Caso 2 :
Existe....

Sejam g₁,g₂,..., g_n os graus dos vértices de uma componente conexa C com | V(C) | > 1
Como G é simples temos que 1g_in-1, para todo 1i n
Portanto,  1 i, jn \ g_i = g_j e ij
 

Demonstrar os seguintes teoremas (exercícios):

(1) Qualquer grafo conexo com | V(G) | >1 não possui vértices de grau zero
(2) Todos os vértices de um grafo conexo G, com | V(G) | > 1, têm grau1
(3) Se G é conexo então quaisquer 2 caminhos de comprimento máximo em G têm um vértice em comum