Poliedros, Grafos e Identidade de Euler

Prévia do material em texto

Seminário MA770
Poliedros, sólidos platônicos e identidade de Euler
Leonardo Schultz Araujo
RA:159828
Definição 1. Um poliedro é um sólido de três dimensões que possui faces planas que são
poĺıgonos.
Definição 2. Um poliedro é convexo em relação a uma de suas faces se estiver totalmente
contido no semi-espaço determinado pelo plano que contem esta face. Dizemos que o
poliedro é convexo se ele for convexo em relação a cada uma de sua faces.
Definição 3. Um poliedro convexo é dito regular se suas faces forem poĺıgonos congruentes
e seus vértices forem congruentes.
Definição 4. Um grafo é um par (V,A), onde V = {v1, v2, . . . , vn} é um conjunto de
vértices e A = {(vi, vj) | vi, vj ∈ V } é um conjunto de arestas.
Definição 5. Dizemos que G é um grafo simples, se G não possui arestas da forma (v, v),
onde v é um vértice de G.
Definição 6. Se G é um grafo e v é um vértice de G, definimos o grau de v como sendo o
número de arestas de G que chegam em v. Denotaremos o grau de v por gr(v). Dizemos
que G é regular se todos os vértices de G tiverem o mesmo grau.
Definição 7. Um caminho em um grafo é uma sequência de arestas da forma {vi1, vi2},
{vi2, vi3}, {vi3, vi4}, . . . , {vi(n−1), vin}. Chamamos de ciclo um caminho fechado.
Definição 8. Um grafo é dito conexo se para todo par de vértices distintos existe um
caminho que os liga.
Definição 9. Uma árvore é um grafo conexo que não possui ciclos.
Definição 10. G é um grafo planar se existir um mergulho deste grafo no plano tal que
suas arestas não se interceptam a menos dos vértices. Um mergulho que satisfaz esta
propriedade é chamado representação plana de G.
Definição 11. Se G é um grafo plano, então sua representação plana particiona o plano
em regiões. Chamaremos estas regiões de faces. Para todo grafo teremos uma face exterior
determinada por sua representação plana, que chamaremos de face do infinito. Se f é
uma face, definimos o grau de f como sendo o número de arestas que fazem fronteira com
f. Denotaremos o grau de f por gr(f). Dizemos que G é face-regular se todas as faces de
G tiverem o mesmo grau.
Agora a relação entre poliedros e grafos fica evidente, uma vez que podemos ver
os vértices e as arestas de um poliedro como vértices e as arestas de um grafo.
Dado um poliedro convexo podemos mergulha-lo na esfera, e depois mergulha-lo
no plano, utilizando a projeção esferográfica. Devida a convexidade, obteremos assim
uma representação plana deste poliedro. Por isso, se estudarmos propriedades dos grafos
planares estaremos assim, estudando uma classe maior de objetos, onde os resultados
relacionados a poliedros convexos seguem como casos particulares.
Provaremos agora a identidade de Euler para grafos planares. E em seguida,
demonstraremos que existem apenas cinco poliedros regulares.
A partir daqui, dado um grafo G, denotaremos por V , A e F seu número de
vértices, arestas e faces, respectivamente. Também denotaremos por Vk a quantidade de
vértices de G com grau k e por Fk a quantidade de faces de G com grau k.
1
Figura 1: Representação planar de um poliedro convexo.
Lema 1. Se G é uma árvore, então A = V − 1.
Demonstração. Perceba que como G é uma árvore, dados dois vértices distintos existe um
único caminho que os liga. Sendo assim, se G possui dois vértices teremos apenas uma
aresta. E portanto, temos a igualdade.
Suponha que o resultado seja válido para toda árvore com A = n− 1. Note então
que se G for uma árvore com A = n, retirando um vértice e a aresta que o liga ao restante
dos vértices, obteremos um novo grafo G′ que satisfaz nossa hipótese de indução. Logo,
(A− 1) = (V − 1)− 1⇒ A = V − 1. �
Teorema 1 (Identidade de Euler). Se G é um grafo planar conexo, então V −A+F = 2.
Demonstração. Faremos por indução no número de arestas. Suponha A = 0. Como G é
conexo segue que V = 1 e F = 1. Donde, neste caso, obtemos a igualdade.
Suponha então que o resultado seja válido para todo grafo planar conexo com
A < n. Seja G um grafo com n arestas. Separaremos em dois casos:
Caso 1: G é uma árvore.
Se G é uma árvore segue que F = 1. Utilizando o lema anterior, temos
V − A+ F = V − (V − 1) + 1 = 2
Caso 2: G não é uma árvore.
Como G é conexo, segue então que G deve possuir ao menos um ciclo. Seja e uma
aresta deste ciclo. Consideraremos agora o grafo G− e. Perceba que, ao retirar a aresta
e, obtemos um novo grafo que possui o mesmo número de vértices, porém uma aresta e
uma face a menos. Aplicando a hipótese de indução,
V − (A− 1) + (F − 1) = 2⇒ V − A+ F = 2
�
Lema 2. Se G é um grafo simples, então
∑
k∈N kVk = 2A.
2
Demonstração. Basta notar que, dada uma aresta (vi, vj), ao contarmos o grau de vi e
de vj estaremos contando duas vezes a mesma aresta (vi, vj). Uma vez que G é simples,
e portanto cada aresta está associada a dois vértices destintos, ao percorrermos todos os
vértices teremos somado duas vezes cada aresta. �
Lema 3. Se G é um grafo planar conexo, então
∑
k∈N kFk ≤ 2A
Demonstração. Note que as faces e as arestas têm ”quase”a mesma relação que as arestas
e os vértices no sentido que da mesma forma que uma aresta está associada a dois vértices,
temos que uma aresta toca duas ou uma face. �
Lema 4. Se G é um grafo planar conexo com V > 3, então A < 3V − 6.
Demonstração. Perceba que, dada uma face f de G, necessariamente gr(f) ≥ 3 (para se
convencer basta analisar os casos onde G é e não é uma árvore). Sendo assim,
2A ≥
∑
k∈N
kFk ≥
∑
k∈N
3Fk = 3
∑
k∈N
Fk = 3F.
Pela identidade de Euler, temos que F = A− V + 2, portanto
2A ≥ 3F = 3(A− V + 2) = 3A− 3V + 6⇒ A ≤ 3V − 6.
�
Teorema 2. Se G é um grafo planar conexo, então existe pelo menos um vértice v de G
tal que gr(v) ≤ 5.
Demonstração. Se V < 6 não há o que argumentar. Suponha então V ≥ 6. Aplicando o
lema anterior, obtemos que:∑
k∈N
kVk = 2A ≤ 2(3V − 6) = 6V − 12
Suponha por absurdo que G tenha apenas vértices com grau maior do cinco. Consequen-
temente, ∑
k∈N
kVk ≥
∑
k∈N
6Vk = 6V.
O que nos dá que,
6V − 12 ≥ 6V.
Donde temos um absurdo. �
Teorema 3. Seja P um poliedro convexo. Defina ρ(P ) = min{gr(f) | f face de P}. Então
3 ≤ ρ ≤ 5.
Demonstração. Olharemos para G o grafo planar de P . Como P é um poliedro convexo,
segue que G é conexo. Além disso, como toda aresta de P toca duas faces, teremos que
vale a igualdade para G ∑
k∈N
kFk = 2A.
3
A desigualdade 3 ≥ ρ segue do fato de que P não pode ter uma face determinada
por menos que três arestas.
Suponha por absurdo que toda face tenha grau maior do que 5. Disso segue que :
2A =
∑
k∈N
kFk ≥
∑
k∈N
6Fk = 6
∑
k∈N
Fk = 6F ⇒
A
3
≥ F.
Observe que por P ser um poliedro, para todo vértice v de G teremos gr(v) ≥ 3. Portanto,
2A =
∑
k∈N
kVk ≥
∑
k∈N
3Vk = 3
∑
k∈N
Vk = 3V ⇒
2A
3
≥ V.
Utilizando a identidade de Euler,
A = V + F − 2 ≤ 2A
3
+
A
3
− 2 = A− 2.
O que é um absurdo.
�
Teorema 4. Existem apenas cinco poliedros regulares.
Demonstração. Seja P um poliedro regular e G sua representação planar. Observe que
da definição de poliedro regular, temos que G é regular e face-regular. Seja d e k o grau
dos vértices es das faces, respectivamente. Dos teoremas (2) e (3) temos que 3 ≤ d ≤ 5 e
3 ≤ k ≤ 5. Note então que,
2A =
∑
k∈N
dVk = dV,
2A =
∑
k∈N
kFk = kF.
Utilizando mais uma vez a identidade de Euler, temos:
8 = 4V − 4A+ 4F = 4V − 2A+ 4F − 2A = V (4− d) + F (4− k).
Levando em conta que V e F são positivos, temos apenas cinco opções para d e k:
Caso 1: d = 3 e k = 3⇒ V = 4 F = 4 (Tetraedro)
Caso 2: d = 3 e k = 4⇒ V = 8 F = 6 (Cubo)
Caso 3: d = 3 e k = 5⇒ V = 20 F = 12 (Dodecaedro)
Caso 4: d = 4 e k = 3⇒ V = 6 F = 8 (Octaedro)
Caso 5: d = 5 e k = 3⇒ V = 12 F = 20 (Icosaedro) �
4
Figura 2: Representação plana dos poliedros regulares.
5