Orientador: Maria do Socorro Nogueira Rangel / Banca: Samuel Jurkiewicz / Banca: Cleonice Fátima Bracciali / Resumo: O objetivo desse trabalho é apresentar o problema de coloração em grafos sob diferentes perspectivas. Caracterizamos o polinômio cromático de um grafo e enunciamos algumas de suas propriedades. Apresentamos duas formulações matemáticas para o problema de coloração de vértices e um método de solução para cada formulação. Apresentamos e discutimos propostas de atividades para o desenvolvimento de uma Oficina de Coloração para alunos do Ensino Médio e Fundamental. / Abstract: In this work the graph coloring problem was presented under di erent perspectives. We define the chromatic polynomials of a graph and describe some of its properties. Furthermore, two solution methods for the vertex coloring problem, through integer programming formulation, has been presented. We propose and discuss some activities for the development of a Workshop for students of secondary school. / Mestre

Orientador: Maria do Socorro Nogueira Rangel / Banca: Horácio Hideki Yanasse / Banca: Silvio Alexandre de Araújo / Resumo: Neste trabalho, analisamos os padrões de corte adotados por uma Indústria de Móveis, e identificamos suas características básicas. Definimos, a partir dessas características, os padrões tabuleiros compostos, que pertencem a classe dos padrões de corte n-grupos, apresentada por Gilmore e Gomory (1965). Os padrões tabuleiros compostos preservam as facilidades de corte dos padrões tabuleiros, apresentando melhores índices de sobra de matéria-prima. Propomos uma heurística para a geração de um pool de padrões tabuleiros compostos, usados para resolver o problema de corte de estoque na indústria de móveis. / Abstract: In this work, we analyze the cutting patterns used by a furniture Industry, and we determine some of its basic characteristics. We defined a composed checkerboard pattern, that belongs to the class of n-groups cutting patterns, presented by Gilmore and Gomory (1965). The composed checkerboard patterns preserve the easiness of the cutting process and have better indexes of waste. We propose a heuristic to generate a pool of composed checkerboard patterns to solve the cutting stock problem in the furniture Industry. / Mestre