Resumos LEIC-A
IST LEIC-AGitHub
Edit page

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+2✓1+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+(r−1)=((q+1)−1)+2(Por Hip. Induc¸a˜o)p+r=(q+1)+2✓p + (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 p≥3p \geq 3 vértices, tem-se que q≤3p−6q \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)

3r≤N1+⋯+Nr≤2qr≤23qp+r≤p+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+2≤p+23q13q≤p−2⇒q≤3p−6q+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(p−1)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:

q≤3×5−6=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 p≥2p\geq 2 vértices, que não tem triângulos, tem-se

q≤2p−4q \leq 2p-4
Demonstração

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

4r≤N1+⋯+Nr≤2qr≤12qp+r≤p+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+2≤p+12q12q≤p−2⇒q≤2p−4q+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

6p≤2q6p \leq 2q

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

q≥3p>3p−6q>3p−6q \geq 3p > 3p -6\\ q > 3p-6

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

QED