The main objective of this dissertation is to present an algebraic method capable of determining a solution, if any, of a non linear polynomial equation systems using Gröbner basis. In order to accomplish that, we first present some concepts and theorems linked to polynomial rings with several undetermined and monomial ideals where we highlight the division extended algorithm, the Hilbert Basis and the Buchberger´s algorithm. Beyond that, using basics of Elimination and Extension Theorems, we present an algebraic solution to the map coloring that use 3 colors as well as a general solution to the Sudoku puzzle. / O objetivo principal desse trabalho é, usando bases de Gröbner, apresentar um método algébrico capaz de determinar a solução, quando existir, de sistemas de equações polinomiais não necessariamente lineares. Para tanto, necessitamos inicialmente apresentar alguns conceitos e teoremas ligados a anéis de polinômios com várias indeterminadas e de ideais monomiais, dentre os quais destacamos o algoritmo extendido da divisão, o teorema da Base de Hilbert e o algoritmo de Buchberger. Além disso, usando noções básicas da Teoria de eliminação e extensão, apresentamos uma solução algébrica para o problema da coloração de mapas usando três cores, bem como um solução geral para o puzzle Sudoku.

The vertex coloring problem is a classic problem in graph theory that asks for a partition of the vertex set into a minimum number of stable sets. This thesis presents our studies on three vertex (re)coloring problems on graphs and on a problem related to a long-standing conjecture on subdivision of digraphs. Firstly, we address the convex recoloring problem in which an arbitrarily colored graph G is given and one wishes to find a minimum weight recoloring such that each color class induces a connected subgraph of G. We show inapproximability results, introduce an integer linear programming (ILP) formulation that models the problem and present some computational experiments using a column generation approach. The k-fold coloring problem is a generalization of the classic vertex coloring problem and consists in covering the vertex set of a graph by a minimum number of stable sets in such a way that every vertex is covered by at least k (possibly identical) stable sets. We present an ILP formulation for this problem and show a detailed polyhedral study of the polytope associated with this formulation. The last coloring problem studied in this thesis is the proper orientation problem. It consists in orienting the edge set of a given graph so that adjacent vertices have different in-degrees and the maximum in-degree is minimized. Clearly, the in-degrees induce a partition of the vertex set into stable sets, that is, a coloring (in the conventional sense) of the vertices. Our contributions in this problem are on hardness and upper bounds for bipartite graphs. Finally, we study a problem related to a conjecture of Mader from the eighties on subdivision of digraphs. This conjecture states that, for every acyclic digraph H, there exists an integer f(H) such that every digraph with minimum out-degree at least f(H) contains a subdivision of H as a subdigraph. We show evidences for this conjecture by proving that it holds for some particular classes of acyclic digraphs. / O problema de coloração de grafos é um problema clássico em teoria dos grafos cujo objetivo é particionar o conjunto de vértices em um número mínimo de conjuntos estáveis. Nesta tese apresentamos nossas contribuições sobre três problemas de coloração de grafos e um problema relacionado a uma antiga conjectura sobre subdivisão de digrafos. Primeiramente, abordamos o problema de recoloração convexa no qual é dado um grafo arbitrariamente colorido G e deseja-se encontrar uma recoloração de peso mínimo tal que cada classe de cor induza um subgrafo conexo de G. Mostramos resultados sobre inaproximabilidade, introduzimos uma formulação linear inteira que modela esse problema, e apresentamos alguns resultados computacionais usando uma abordagem de geração de colunas. O problema de k-upla coloração é uma generalização do problema clássico de coloração de vértices e consiste em cobrir o conjunto de vértices de um grafo com uma quantidade mínima de conjuntos estáveis de tal forma que cada vértice seja coberto por pelo menos k conjuntos estáveis (possivelmente idênticos). Apresentamos uma formulação linear inteira para esse problema e fazemos um estudo detalhado do politopo associado a essa formulação. O último problema de coloração estudado nesta tese é o problema de orientação própria. Ele consiste em orientar o conjunto de arestas de um dado grafo de tal forma que vértices adjacentes possuam graus de entrada distintos e o maior grau de entrada seja minimizado. Claramente, os graus de entrada induzem uma partição do conjunto de vértices em conjuntos estáveis, ou seja, induzem uma coloração (no sentido convencional) dos vértices. Nossas contribuições nesse problema são em complexidade computacional e limitantes superiores para grafos bipartidos. Finalmente, estudamos um problema relacionado a uma conjectura de Mader, dos anos oitenta, sobre subdivisão de digrafos. Esta conjectura afirma que, para cada digrafo acíclico H, existe um inteiro f(H) tal que todo digrafo com grau mínimo de saída pelo menos f(H) contém uma subdivisão de H como subdigrafo. Damos evidências para essa conjectura mostrando que ela é válida para classes particulares de digrafos acíclicos.

Orientador: Sidney José Lima Ribeiro / Resumo: Este trabalho descreve o desenvolvimento de membranas de cellulose bacterianas (BCM), econômicas e ecologicamente amigáveis com propriedades funcionais. Nanopartículas de sílica esféricas com tamanho de partícula de cerca de 51 ± 4 nm, obtidas pelo método sol-gel e nanopartículas de sílica com tamanho de partículas heterogêneo, extraídas da casca de arroz, foram preparadas e funcionalizadas pelas metodologias in situ e post-grafting, respectivamente, com alcoxisilanos com propriedades easy-cleaning e curcuma. Nanocompósito de anatase SiO2@TiO2 preparado pelo método sol-gel, também foi desenvolvido. Posteriormente, estes nanomateriais funcionais e os organosilanos 1,4 – bis(trietoxissilil)benzeno (BTEB), Bis(trietoxisililpropil)disulfeto (BTPD) and 1,2-Bis(trietoxissilil)etano (BTSE), foram imobilizados com sucesso na BCM, segundo as metodologias in situ e post-grafting. Na BCM funcionalizada com os organosilanos BTEB, BTPD e BTSE, nanopartículas de sílica esféricas com estrutura porosa e distribuição de tamanho de partícula heterogêneo, foram formados nas fibras de celulose. A repelência da BCM funcionalizado com nanopartículas de sílica contendo propriedades de limpeza facilmente melhorada notavelmente. BCM apresenta fobicidade à água, tolueno, cicloexano e solução de suor artificial. Especificamente, a BCM funcionalizada com a amostra SiO2@F13TES segundo as metodologias in situ e post-grafting, apresentam uma superfície quase superhidrofóbica (> 150°). As medições de decomp... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: This work reports the development of economic and environmentally friendly Bacterial Cellulose Membrane (BCM) with functional properties. The spherical mesoporous silica nanoparticles with average particle size around 51 ± 4 nm, obtained by sol-gel method and spherical silica nanoparticles with heterogeneous particles size distribution (20-40 nm) obtained through agro-industrial waste were prepared and functionalized by in situ and post-grafting methodology, respectively, with alkoxysilanes with easy-cleaning properties and natural dye obtained through natural extracts, namely curcuma. Anatase TiO2@SiO2 spherical nanocomposites prepared by the sol-gel method, have also been developed. Subsequently, these functional nanomaterials and the organosilanes 1,4 – bis(triethoxysilyl)benzene (BTEB), Bis(triethoxysilylpropyl)disulfide (BTPD) and 1,2-Bis(triethoxysilyl)ethane (BTSE), were successfully incorporated into BCM, by in situ and post-grafting methodologies. In the BCM functionalized with BTEB, BTPD and BTSE, spherical silica nanoparticles with porous structure and heterogeneous particle size, were formed on the cellulose fibers. The surface repellency of the functionalized BCM with silica nanoparticles containing easy-cleaning properties was remarkably enhanced. This BCM displaying phobicity to water, toluene, cyclohexane and artificial sweat. Specifically, the BCM functionalized by in situ and post-grafting with SiO2@F13TES, displayed a surface almost superhydrophobic (> 150°... (Complete abstract click electronic access below) / Doutor