Grafos Planares: segmentos bastam - Parte 01
Channel: ToLOCA - UFBA
Date: 2022-06-03

Expositor: Luiz Moreira, doutor pelo IMPA e futuro docente da UFPE.

Resumo: Um grafo é um par ordenado (V,E), onde V é um conjunto não vazio de objetos denominados vértices e E, o conjunto das arestas, é um subconjunto de pares não ordenados de V. Essa é a definição abstrata, mas bom mesmo é desenhar. Para tal, representamos (no papel) o conjunto de vértice por pontos e o conjunto de aresta por uma curvas conectando os dois pontos do par. Logo nas primeiras tentativas, notamos que essa representação pode virar uma bagunça. E uma pergunta natural seria: é possível representar todos os grafo sem que as aresta se cruzem? A resposta para a pergunta é não. Infelizmente, nós teremos que lidar com a bagunça. Os grafos que conseguimos desenhar no papel sem cruzar arestas são minoria, e a essa classe damos o nome de Grafos Planares. O seminário de hoje é sobre essa classe especial. Nós provaremos que todo grafo planar pode ser desenhado usando apenas segmentos de reta como arestas. Isto é, permitir que arestas se curvem (tentando desviar?) não aumenta a classe de grafos que conseguimos desenhar sem cruzamentos. Esse belíssimo teorema é conhecido como Teorema de Fáry, espero que aproveitem.