Grafos - Início

O que é um Grafo?

Um grafo é um par g=(V,R)g = (V,R), onde:

  • VV é um conjunto de vértices finito e não vazio
  • RR é o conjunto dos dos pares de vértices que estão ligados por uma aresta

Por exemplo

Grafo 1

V={V1,V2,V3,V4}R={(V1,V2),(V2,V1),(V2,V3),(V3,V2),(V1,V3),(V3,V1),(V3,V4),(V4,V3),}V = \{V_1,V_2,V_3,V_4\}\\ R = \{(V_1,V_2),(V_2,V_1),(V_2,V_3),(V_3,V_2),(V_1,V_3),(V_3,V_1),(V_3,V_4),(V_4,V_3),\}

Como uma aresta não tem direção, em RR representa-se os dois pares das 22 "direções" de cada aresta.
Contudo, como isto é uma propriedade conhecida dos grafos, também se pode represente um grafo gg por g=(R,E)g = (R,E), onde EE é o conjunto RR sem repetições.

No caso do exemplo acima, um EE possível seria

E={(V1,V2),(V3,V2),(V4,V3),(V1,V3)}E = \{(V_1,V_2),(V_3,V_2),(V_4,V_3),(V_1,V_3)\}

Definições e Teoremas

Ordem e Tamanho do grafo

  • Ordem do grafo, pp, é o número de vértices do grafo.
  • Tamanho do grafo, qq, é o número de arestas do grafo

Seja g=(V,E)g = (V,E),

p=#Vq=#Ep = \#V\\ q = \#E

Relembrar

#A\#A = número de elementos do conjunto AA


Grau de um vértice

g=(V,E)g = (V,E). Para um vértice vVv\in V, o seu grau em gg corresponde ao número de arestas de gg que incidem em vv.
Representa-se por:

degg(v)\operatorname{deg}_g(v)

Teorema Fundamental da Teoria dos Grafos

Num grafo g=(V,E)g=(V,E), a soma dos graus dos seus vértices é igual ao dobro do Tamanho do grafo.

Demonstração

Primeiro define-se a seguinte operação

I:V×E{0,1}\operatorname{I}:V \times E \rightarrow \{0,1\}

Seja vv um vértice e ee uma aresta de gg,
I(v,e)=\operatorname{I}(v,e) = número de vezes que a aresta ee incide em vv

Seja SdegS_{deg} a soma dos graus dos vértices de gg,

Sdeg=vVdegg(v)=vVeEI(i,e)=eEvVI(i,e)=eE2=2×(#E)S_{deg} = \sum_{v \in V} \operatorname{deg}_g(v)\\ =\sum_{v \in V} \sum_{e \in E} \operatorname{I}(i,e)\\ = \sum_{e \in E} \sum_{v \in V} \operatorname{I}(i,e)\\ = \sum_{e \in E} 2 = 2 \times (\#E)

QED

vVI(i,e)\sum_{v \in V} \operatorname{I}(i,e) é 2, pois cada aresta ee está associada a 2 vértices.


Teorema 2

Num grafo g=(V,E)g = (V,E), o número dos seus vértices ímpares é par.

NOTA

vértice é par/ímpar \rightarrow tem grau par/ímpar.

Demonstração

Para g=(V,E)g = (V,E), onde #V=p\#V=p

V={v1,,vk,u1,,upk}v1,,vkveˊrtices paresu1,,upkveˊrtices ıˊmparesV = \{v_1,\dots,v_k,u_1,\dots,u_{p-k}\}\\ v_1,\dots,v_k \rightarrow \text{vértices pares}\\ u_1,\dots,u_{p-k} \rightarrow \text{vértices ímpares}

Pelo Teorema Fundamental da Teoria dos Grafos, a soma dos graus é 2×q2\times q, com qq o número de arestas.
Assim sendo, será um número par. Como a soma dos graus dos vértices pares é par, para o resultado final também ser par, é obrigatório haver um número par de vértices ímpares.

QED

Aplicações

Exercício 5 da Série 4
Um certa comissão parlamentar da Assembleia da República é composta por 15 deputados. Conclua que não é possível que cada um deles já tenha estado em comissões parlamentares anteriores com exatamente 5 dos outros deputados que fazem parte desta comissão.

Se se desenhar um grafo onde os vértices são os deputados e as arestas ligam dois deputados que tenham estado juntos em comissões anteriores, o grafo teria um número ímpar (15)(15) de vértices com grau ímpar (5)(5), o que pelo Teorema 2 é impossível.

QED


Grafo Regular

Um grafo diz-se regular se todos os seus vértices têm o mesmo grau.
Um grafo diz-se kk-regular (kN)(k \in N) se os seus vértices têm grau kk.

Exemplo

Grafo 2


Grafo Completo

Um grafo diz-se completo quando cada par de vértices constitui uma aresta (está tudo ligado).

Exemplo

Grafo 3

NOTA

  • Todo o grafo completo de kk vértices é kk-1 regular
  • (p2)=p(p1)2\binom{p}{2} = \frac{p(p-1)}{2} é o número máximo de arestas que um grafo pode ter
  • KnK_n \rightarrow grafo completo de nn vértices

Rede

É um terno N=(V,E,f)N = (V,E,\operatorname{f}), onde g=(V,E)g=(V,E) é um grafo subjacente à Rede e f:ER\operatorname{f}: E \rightarrow \R uma aplicação (todos os elementos de EE têm correspondência).

Em suma, uma Rede é um grafo onde as arestas têm valores reais associados.

Exemplo

Grafo 4


Multigrafo

É uma Rede onde as arestas estão associadas a valores naturais. Pode-se representar um multigrafo substituindo cada aresta por nn arestas, onde nn é o valor associado. (Com o exemplo fica claro)

Exemplo

Grafo 5

NOTA

É normal referir-se a multigrafos como apenas grafos. O novo termo é só usado para evitar ambiguidade quando temos grafos e multigrafos.


Caminho

Num grafo g=(V,E)g=(V,E) é uma sequência alternada de vértices e arestas P=v0a1v1anvnP = v_0a_1v_1\dots a_nv_n, onde j=1,,k\forall j = 1,\dots,k, aj=vj1vja_j = v_{j-1}v_j, ou seja, cada aresta liga os vértices ao seu lado.


Atalho

Caminho que não repete arestas.


Trajetória

Caminho que não repete vértices, exceto no caso dos vértices inicial e final coincidirem. Neste caso a Trajetória é fechada, caso contrário é aberta.


Vértices Conectados

Dois vértices uu e vv de um grafo g=(V,E)g = (V,E) dizem-se conectados se forem o mesmo vértice ou se existir um caminho onde as extremidades são uu e vv

Exemplo

Grafo 6 V1V_1 e V2V_2 são vértices conectados.
O caminho vermelho é um exemplo de caminho que prova esse facto.


Grafo Conexo

Um grafo é conexo se quaisquer dois vértices do grafo estão conectados.


Subgrafo

Dado um grafo g=(V,E)g=(V,E), diz-se que o grafo h=(V,E)h = (V',E') é subgrafo de gg se VVV' \subseteq V ou EEE'\subseteq E.
Um grafo é subgrafo de si mesmo


Componente

hh é uma componente de um grafo gg, se hh for um subgrafo conexo de gg e não for subgrafo de nenhum outro subgrafo conexo de gg.

Exemplo

Grafo 7

hh é uma componente do grafo gg

Grafo Planar

Grafo que é possível desenhar sem cruzar arestas.

Teorema 3 - Lei de Euler

Seja gg um Grafo Planar, existe a seguinte relação:

Arestas+2=Veˊrtices+Regio˜es\text{Arestas}+2=\text{Vértices}+\text{Regiões}

NOTA

A Região "Exterior" também conta

Exemplo

Grafo Teorema 3

Sejam A,B,CA,B,C e DD as regiões, a igualdade confirma-se

13+2=11+413 + 2 = 11 + 4

Ponte

Aresta de um grafo, que, se for removida, aumenta o número de componentes.

Exemplo

Grafo Ponte

A Aresta Verde é uma Ponte.

Teorema 4

Num grafo de pp vértices e kk componentes, o nº de arestas (q)(q) é tal que:

pkq(pk+1)(pk)2p-k\leq q \leq \frac{(p-k+1)(p-k)}{2}
Demonstração
  1. Provar que pkqp-k \leq q

Por indução simples, variando o Tamanho do Grafo (q)(q)

q=0q=0,
Neste caso o número de vértices é igual ao número de componentes.

0pp=0,P.V. 0 \geq p-p = 0, \quad \text{P.V.}

Hipótese: Grafos com qq arestas (não importando o nº de componentes e vértices): pkqp-k \leq q.

Para esta prova, vamos supor que o grafo é esquelético, ou seja, todas as arestas são pontes. (No final da Demonstração há um exemplo de grafo esquelético.) Se a prova funcionar para grafos esqueléticos funcionará para qualquer um, pois estes têm o menor número de arestas para um dado número de vértices.

Se removermos uma aresta de um grafo esquelético, o número de componentes aumenta.
Deste modo, por hipótese de indução

qpk(Hip de Induc¸a˜o)qp(k+1)(Removendo uma aresta)q+1pkq \geq p - k\quad \text{(Hip de Indução)}\\ q \geq p - (k+1)\quad \text{(Removendo uma aresta)}\\ q+1 \geq p-k

O que é válido, pois qpkq \geq p-k.
A primeira inequação está provada \checkmark.

  1. Provar que q(pk+1)(pk)2q \leq \frac{(p-k+1)(p-k)}{2}

Como estamos a tentar provar que o número de arestas tem um limite máximo, vamos ter em conta sempre os casos "máximos".

Seja kk' uma componente do grafo em estudo. Se essa componente tem pp' vértices, tem no máximo p(p1)2\frac{p'(p'-1)}{2} arestas.

Se o grafo tem kk componentes, o que acontecerá se transferirmos um vértices de uma componente para outra?
Seja h1h_1 e h2h_2 duas componentes com p1,q1p_1, q_1 e p2,q2p_2,q_2, respetivamente e p1p2p_1 \leq p_2 (o que é verdade para quaisquer duas componentes, haverá com mais vértices, ou têm as duas o mesmo número).
Seja Δqi,i=1,2\Delta q_i, i=1,2 a variação do número de arestas nas componentes h1h_1 e h2h_2, quando "transferimos" um vértice de h1h_1 para h2h_2.

Δq1=(p11)(p12)2p1(p11)2=1p1Δq2=(p2+1)p22p2(p21)2=p2\Delta q_1 = \frac{(p_1-1)(p_1-2)}{2}-\frac{p_1(p_1-1)}{2}\\ =1-p_1\\ \Delta q_2 = \frac{(p_2+1)p_2}{2}-\frac{p_2(p_2-1)}{2}\\ =p_2

A variação total será 1+p2p11+p_2-p_1 e será positiva pois p2p1p_2 \geq p_1

Assim, com o que acabamos de verificar, podemos concluir que um grafo com kk componentes terá o números máximo de arestas se e só se tem:

  • k1k-1 vértices isolados
  • 11 componente com p(k1)=pk+1p-(k-1)=p-k+1 vértices

Nestas condições, o número máximo de arestas será:

(pk+1)(pk)2\frac{(p-k+1)(p-k)}{2}

Finalmente, podemos concluir que q(pk+1)(pk)2q\leq\frac{(p-k+1)(p-k)}{2}
A segunda inequação está provada \checkmark.

QED

Exemplo Grafo Esquelético

Esquelético

Teorema 5

Se um grafo de pp vértices tem mais de (p1)(p2)2\frac{(p-1)(p-2)}{2} arestas, então é conexo.

Demonstração

Se o grafo não for convexo tem pelo menos 22 componentes. Seja qq o número de arestas, pelo Teorema Anterior

q(p2+1)(p2)2=(p1)(p2)2q \leq \frac{(p-2+1)(p-2)}{2} = \frac{(p-1)(p-2)}{2}

Logo, como também vimos no Teorema Anterior que a "transferência" de vértices entre componentes aumenta qq, se passarmos todos os vértices de uma componente para outra (passando agora a ter apenas 11), conclui-se que qq será maior do que a expressão acima.

QED