Seminário de Teoria da Computação

         As Classes de Grafos PI (Point-Interval) e PI*

                 Sheila Morais de Almeida

           Sexta-feira, 3 de outubro de 2003

              Auditório do IC (IC1), 13:00hs




Seja F uma família de conjuntos. Podemos associar à família F um
grafo, G, da seguinte forma: cada conjunto de F corresponde a um
vértice de G e existe uma aresta ligando dois vértices em G se, e
somente se, existe interseção nos conjuntos correspondentes a esses
vértices. O grafo G é grafo interseção da família F.  Todo grafo
simples é grafo interseção de alguma família de conjuntos. Sendo
assim, é mais interessante considerar classes de grafos de interseção
de famílias de conjuntos com alguma estrutura especial, tais como os
grafos de interseção de intervalos em uma reta, de trapézios entre
duas retas paralelas, de cordas de um círculo, de cliques de um grafo,
dentre outros. O interesse por classes especiais de grafos de
interseção está diretamente relacionado às aplicações em vários campos
tais como computação, genética, arqueologia, dentre outros. Algumas
aplicações recentes incluem análise de substituição em macros e
seqüenciamento de proteínas.

Neste seminário serão apresentados os grafos de interseção de
triângulos entre duas retas paralelas, cada triângulo representa um
vértice do grafo e existe uma aresta ligando dois vértices se, e
somente se, os triângulos que representam o respectivos vértices se
intersectam. Quando a base de todos os triângulos estiver sobre uma
mesma reta, dizemos que o grafo interseção desse modelo pertence à
Classe dos Grafos PI. Se a base dos triângulos puder estar em qualquer
uma das duas retas, dizemos que o grafo interseção pertence à Classe
dos Grafos PI*.  Situaremos as classes PI e PI* dentro de um contexto
de outras classes mais estudadas e mostraremos alguns resultados de
pesquisa sobre essas classes.

http://www.ic.unicamp.br/~fkm/seminarios