Deixa eu corrigir uma coisa que falei na aula ontem.
Considere a descrição combinatória do desenho de um grafo com n vértices e m arestas, ou seja, olhemos para a sua lista de adjacências na ordem dada, e consideremos que ela descreve a ordem em que as arestas aparecem no sentido anti-horário ao redor do vértice no desenho (que pode ou não ser planar).
Então podemos calcular o número f de faces de um tal desenho fazendo percursos adequados usando as listas de adjacências ordenadas.
Então, se calcularmos o número \chi = v - m + f, dele podemos determinar o genus da superfície que acomoda esse desenho. Se \chi for par, e g for tal que \chi = 2-2g, então a superfície é orientável e tem genus g.
Por exemplo, se \chi = 2, a superfície tem genus 0, e é portanto o plano. Se \chi = 0, então o desenho está no torus, que é a superfície orientada de genus 1. E assim por diante.
Já se \chi é ímpar, então a superfície onde o desenho se acomoda é não orientável. Uma coisa que falei de errado foi o seguinte. Se \chi=1, então a superfície é o chamado plano projetivo, que nada mais é que um círculo com os pontos da fronteira diametralmente opostos identificados.
A garrafa de Klein corresponde à superfície não orientada seguinte, ou seja, \chi = -1.
Se você gosta destas coisas, pode brincar um pouco da seguinte maneira. Pegue um grafo pequeno, por exemplo, o K_5. Desenhe-o no plano (naturalmente com cruzamentos), numere seus vértices e fixe as listas de adjacências de acordo com o seu desenho (não-plano). Agora conte quantas faces essa lista de adjacências definem.
Isso diz o genus da superfície onde você conseguiria desenhar o K_5, com exatamente estas faces, sem que as suas arestas se cruzem. É bem possível que você pegue uma superfície de genus baixo, como o plano projetivo ou o toro. Daí você pode até tentar visualizar o desenho
Gosta desse assunto? Experimente olhar o seguinte livro na biblioteca:
Mohar e Thomassen, Graphs on surfaces,
QA840 M697g.
Você vai se divertir.
Até,
Cris