Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/276351
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: Grafos PI
Author: Almeida, Sheila Morais de, 1979-
Advisor: Mello, Célia Picinin de, 1950-
Abstract: Resumo: Uma representação PI consiste em duas retas paralelas, r e s, e triângulos com um vértice em r e um lado em s. Considere R uma representação PI. O grafo interseção de R é chamado grafo P I quando cada vértice do grafo corresponde a um triângulo de R e existe aresta entre dois vértices se, e somente se, os triângulos correspondentes se intersectam. Segundo o livro Graph Classes - a Survey (1999) [3], escrito por Brandstiidt, Le e Spinrad, os problemas de reconhecer e de caracterizar a classe dos grafos PI ainda não estão resolvidos. Essa é a principal motivação para o estudo da classe PI. Nesta dissertação, apresentamos um estudo dos grafos PI baseado nas suas relações com outras classes de grafos tais como os grafos de intervalos e permutação, que são classes amplamente conhecidas de grafos interseção, e os grafos trapezóides, que possuem uma estrutura muito semelhante à dos grafos PI. Esta dissertação é uma síntese de trabalhos existentes sobre a classe PI e apresenta novas condições necessárias e/ou suficientes para que um grafo seja PI

Abstract: A PI-representation consists of two parallellines, r and s, and triangles with one vertex on r and the other two on s. Let R be a PI-representation. The intersection graph of R is called PI graph when each vertex in the graph corresponds to a triangle in R and there exists an edge between two vertices if and only if their corresponding triangles intersect. According to the book Graph Classes - a Survey (1999) [3], by Brandstiidt, Le and Spinrad, the PI graph characterization and recognition problems are still open. This is the main motivation for the study of the PI graph class. In this dissertation, we present a study of PI graphs based on their relationship with other graph classes such as the interval and permutation graphs, which are well known intersection graph classes, and trapezoid graphs, which have a very similar structure to that of PI graphs. This dissertation is a survey on existing work on the PI graph class and presents new necessary andj or sufficient conditions for a graph to be PI
Subject: Teoria dos grafos
Language: Inglês
Editor: [s.n.]
Date Issue: 2005
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Almeida_SheilaMoraisde_M.pdf410.93 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.