Grafos Planares

Grafos que podem ser desenhados sem que haja interseções de arestas.

Teoremas

Teorema 1

Num grafo conexo planar de pp vértices, qq arestas e rr regiões, então

p+r=q+2p+r = q+2
Demonstração

Por indução Simples

Base

q=0q=0, então o grafo terá apenas 11 vértice e 11 região.

1+1=0+21+1=0+2 \quad \checkmark

Hipótese de Indução

p+r=q+2p+r = q+2

Substituindo qq por q+1q+1 temos 22 casos:

  1. Grafo é uma árvore
    Se é uma árvore, sabemos que terá q+1q+1 arestas e apenas tem 11 região, logo, por hipótese de Indução:

    (q+2)+1=(q+1)+2(q+2) + 1 = (q+1) + 2 \quad \checkmark
  2. Não é árvore, tem pelo menos um ciclo
    Removendo uma aresta do ciclo ficamos com qq arestas. Agora já não temos ciclo, por isso também temos menos uma região (a do ciclo).

    p+(r1)=((q+1)1)+2(Por Hip. Induc¸a˜o)p+r=(q+1)+2p + (r-1) = ((q+1)-1) + 2 \quad \text{(Por Hip. Indução)}\\ p + r = (q+1) +2 \quad \checkmark

    NOTA (q+1)(q+1) é o número de arestas do grafo em análise, por isso é que é verdade pela Hipótese de Indução.

QED

Teorema 2

Num grafo conexo planar de p3p \geq 3 vértices, tem-se que q3p6q \leq 3p-6

Demonstração

Sabe-se que a menor região num grafo planar é limitada por 33 vértices/arestas (um triângulo, que pode ser "torto" (exemplo no fim)).
Deste modo, seja NiN_i o número de arestas na fronteira da região ii, rr o número de regiões e qq o número de arestas, no mínimo teremos só regiões formadas por triângulos e a soma de regiões será no máximo 2q2q (repetimos cada aresta 22 vezes)

3rN1++Nr2qr23qp+rp+23q3r \leq N_1 + \dots + N_r \leq 2q\\ r \leq \frac{2}{3}q\\ p+r \leq p+\frac{2}{3}q

Como q+2=p+rq+2=p+r pelo Teorema 1

q+2p+23q13qp2q3p6q+2 \leq p+\frac{2}{3}q\\ \frac{1}{3}q \leq p- 2 \Rightarrow q \leq 3p-6

QED

Triângulo "torto"

Tri Torto

A região R1R_1 assinalada a verde é limitada por um triângulo ("torto").
Mas atenção: "torto" não foi uma designação dada pelo professor na aula, nem sei se existe.

Exemplo

O grafo completo de 55 vértices (k5)(k_5) não é planar.
Como é completo, o número de arestas será

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

Onde pp é o número de vértices. Se p=5p=5, q=10q=10 e, pelo Teorema 2 um grafo de 55 vértices tem de ter:

q3×56=9q \leq 3 \times5 -6 = 9

Como 10>910>9, conclui-se que k5k_5 não é planar

AVISO

Um grafo pode respeitar as condições do Teorema 2 e não ser planar. Só podemos tirar conclusões se não respeitar a igualdade.

Teorema 3

Num grafo conexo planar de p2p\geq 2 vértices, que não tem triângulos, tem-se

q2p4q \leq 2p-4
Demonstração

Quase igual à anterior, só temos de mudar os valores.

4rN1++Nr2qr12qp+rp+12q4r \leq N_1 + \dots + N_r \leq 2q\\ r \leq \frac{1}{2}q\\ p+r \leq p+\frac{1}{2}q

Como q+2=p+rq+2=p+r pelo Teorema 1

q+2p+12q12qp2q2p4q+2 \leq p+\frac{1}{2}q\\ \frac{1}{2}q \leq p- 2 \Rightarrow q \leq 2p-4

QED

Exemplo

Um grafo bipartido com partições de dimensão 33 (k3,3)(k_{3,3}) não é planar.

K 33

A região mínima é um quadrado.
Se verificarmos, temos 99 arestas. Pelo Teorema 3 temos de ter no máximo 88 em grafos com 66 vértices.
k3,3k_{3,3} não é planar.

Teorema 4

Num grafo planar há sempre pelo menos um vértice de grau 5\leq 5.

Demonstração

Imagine-se que afinal havia pelo menos um vértice de grau 6\leq 6.

Então, para grafos onde os vértices têm todos grau 6\geq 6, pelo Teorema Fundamental da Teoria dos Grafos

6p2q6p \leq 2q

Onde pp é o número de vértices e qq o número de arestas.

q3p>3p6q>3p6q \geq 3p > 3p -6\\ q > 3p-6

O que significa que não pode ser planar pelo Teorema 2.

QED