============================================================ Seminário de Teoria da Computação e Combinatória (TCC) ============================================================ Título: Dois problemas em grafos Palestrante: Jorge Stolfi Instituto de Computação Universidade Estadual de Campinas Hora e Data: 14h, sexta-feira, 16 de setembro de 2011 Local: auditório do NUMEC Resumo: Neste seminario vou descrever dois problemas sobre grafos que encontrei como sub-problemas em outras aplicações. Não sei se são fáceis ou difíceis, abertos ou resolvidos. O primeiro problema é definir um conceito coerente de "grafo esparso". Tenho um algoritmo numérico que opera sobre uma malha dada G. O algoritmo é muito eficiente quando G é planar, e parte dessa eficiência decorre das seguintes propriedades: (1) em qualquer grafo simples planar conexo com V vértices e E arestas, temos E = O(V); (2) certas operações de simplificação local preservam planaridade. A questão é como estender esse algoritmo para malhas em dimensões maiores. Para isso precisaríamos encontrar uma classe de grafos "esparsos" que (0) inclui malhas regulares d-dimensionais, (1) satisfaz E = O(V) e (2) é fechada sob certas operações de simplificação local. O segundo problema é a caracterização de grafos que são esqueletos de triangulações. Uma triangulação bidimensional pode ser vista como um desenho de um grafo em uma superfície compacta (esfera, toro, fita de Moebius, etc.) onde cada face é um triângulo. A questão é: quando é que um grafo simples tem uma triangulação? (Todo grafo pode ser desenhado em alguma superfície, mas as faces resultantes não são necessariamente triângulos.) Verifica-se que K6 admite triangulação; será que K7 admite? Este problema pode ser definido de maneira inteiramente combinatória (sem falar em superfície), e nessa forma ele pode ser generalizado para d dimensões.