Orientador: Prof. Dr. Rafael de Mattos Grisi / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional, 2015. / Esse trabalho tem por objetivo apresentar um pouco da teoria de grafos no ensino Básico. Nele serão abordados conceitos básicos da teoria de grafos com maior enfoque sobre os grafos eulerianos e semieulerianos e o teorema das quatro cores. Apresentamos e discutimos também algumas propostas de atividades que foram e poderão ser desenvolvidas no Ensino Fundamental e Médio, possibilitando ao aluno o desenvolvimento de algumas habilidades como investigar, analisar, modelar, dentre outras. A prática dessas atividades foi realizada em uma escola da rede estadual do Estado de São Paulo com uma turma do 9o ano do Ensino Fundamental e com uma turma do 3o ano do Ensino Médio, no ano de 2014. / This work aims to present some of the so called graph theory in the Basic education. It will address the basic concepts of graph theory with greater focus on the Euler graphs and the four color theorem. We also discuss some proposals for activities that have been developed in primary and secondary education, enabling the student to develop some skills to investigate, analyze and model problems using graphs. The practice of these activities took place in a state school of São Paulo with a class of 9th graders of the elementary school and a group of the 3rd year of high school, in 2014.

Made available in DSpace on 2014-06-11T19:35:03Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-05-27Bitstream added on 2014-06-13T19:44:51Z : No. of bitstreams: 1 santos_dm_dr_araca.pdf: 1533021 bytes, checksum: 248d1fb3f8ac9369529ebf0ea03f0654 (MD5) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / O presente estudo teve por objetivo avaliar a influência de dois pigmentos (pó de cerâmica e tinta a óleo) e um opacificador (sulfato de barium) sobre as propriedades físicas de estabilidade de cor, dureza, absorção e solubilidade do silicone facial MDX4-4210, submetido ao envelhecimento acelerado. Para a confecção das amostras, foram utilizadas 2 matrizes metálicas em alumínio, contendo em seu interior 10 compartimentos circulares com 45mm de diâmetro apresentando estes, em uma matriz, uma espessura de 2mm para os testes de estabilidade de cor e dureza e, na outra, 1mm para os ensaios de absorção e solubilidade. Foram confeccionadas 120 amostras, metade para os ensaios de análise cromática e dureza e, a outra metade, para o teste de absorção e solubilidade. As amostras destinadas para cada teste foram distribuídas em seis grupos, incolor (G1), incolor com opacificador (G2), cerâmica (G3), cerâmica com opacificador (G4), óleo (G5), óleo com opacificador (G6). Após a obtenção das amostras, a análise cromática inicial foi verificada por meio da análise visual e da espectrofotometria de reflexão. Os ensaios de dureza foram realizados com auxílio de um durômetro Shore A. Os testes de absorção e solubilidade foram realizados por meio de um dessecador no qual as amostras permaneceram neste ambiente em estufa à temperatura de 37±2°C, sendo pesadas diariamente até obtenção de massa constante (W1); posteriormente as amostras foram submetidas ao envelhecimento seguido de nova pesagem (W2), e nova dessecação com pesagem final (W3). As amostras foram submetidas ao envelhecimento acelerado por 1008 horas, sendo os ensaios realizados nos períodos correspondentes a 252, 504 e 1008 horas. Os dados obtidos foram submetidos à ANOVA e Tukey, com significância de 5%. Pode-se observar pela análise espectrofotométrica que os grupos com opacificador apresentaram melhor... / The aim of this study was to evaluate the influence of two pigments (ceramic powder and oil paint) and one opacifier (barium sulfate) on physical properties of color stability, hardness, absorption and solubility of the facial silicone MDX4-4210 submitted to artificial aging. The replicas were fabricated in two metallic matrixes in aluminum containing 10 circular compartments with 45mm in diameter. One matrix generated specimens with 2mm in thickness for color stability and hardness evaluations while the other matrix, specimens with 1mm in thickness for absorption and solubility tests. The replicas were divided into six groups: colorless (G1), colorless with opacifier (G2), ceramic (G3), ceramic with opacifier (G4), oil (G5) and oil with opacifier (G6). Initial chromatic evaluation was performed by visual analysis and reflection spectrophotometry. The hardness tests were carried out by a Shore A durometer. The evaluations of absorption and solubility were performed through a desiccator to maintain the replicas in a stove at 37±2°C. The specimens were weighed daily until obtaining a constant mass, (W1). Then, the replicas were submitted to aging followed by a new weighing (W2) and drying with final weighing (W3). The replicas were submitted to accelerated aging during 1008 hours with evaluation after 252, 504 and 1008 hours. Data were submitted to statistical analysis by ANOVA and Tukey’s test at 5% level of significance. According to spectrophotometry, the groups with opacifier presented statistically significant better chromatic stability than the other groups. The accelerated aging generated significant chromatic alterations in all groups, except for colorless and oil groups both with opacifier. There was no statistically significant difference among the groups after aging regarding hardness, absorption and solubility. According to the results, it may be concluded that... (Complete abstract, click electronic access below)

[pt] Nas redes de fibras óticas, as informações são transmitidas na forma de um sinal luminoso através de uma fibra ótica. A tecnologia de multiplexação WDM permite a transmissão simultânea de vários sinais em um mesmo enlace. As conexões entre estações terminais são estabelecidas na forma de caminhos óticos, que são definidos em função de sua rota e do comprimento de onda no qual são multiplexados. Conversores de comprimentos de onda não são considerados neste trabalho. Conseqüentemente, os caminhos óticos devem permanecer com o mesmo comprimento de onda em todos os enlaces do transmissor ao receptor. O Problema de Roteamento e Atribuição Mínima de Comprimentos de Onda (min- RWA) consiste em estabelecer um conjunto de conexões entre pares de estações e atribuir um determinado comprimento de onda para cada uma delas, de forma que caminhos óticos que compartilhem algum enlace da rede tenham comprimentos de onda diferentes e que o número total de comprimentos de onda utilizados seja mínimo. Neste trabalho, uma nova heurística é proposta para min-RWA, onde k possíveis rotas são calculadas para cada conexão e, em seguida, uma rota (dentre as rotas pré-calculadas) e um comprimento de onda são atribuídos a cada conexão resolvendo-se um Problema de Coloração de Partições (PCP). O PCP é um problema de coloração em grafos particionados, ou seja, grafos onde os vértices estão particionados em subconjuntos disjuntos. O PCP consiste em selecionar e colorir um único vértice de cada subconjunto, de modo que dois vértices adjacentes, no grafo induzido pelos vértices selecionados tenham cores diferentes e que o número total de cores utilizadas seja mínimo. Nesta dissertação, são apresentadas e propostas novas heurísticas para PCP e min-RWA. Estas heurísticas são comparadas com as melhores conhecidas na literatura. / [en] In optical networks, the information is transmitted along the optical fibers as optical signals. Wavelength Division Multiplexing (WDM) allows more efficient use of the huge capacity of optical fibers, as far as it permits the simultaneous transmission of different channels along the same fiber, each of them using a different wavelength. The connections are established by lightpaths, in which the signal is converted to the optical domain and reaches the receptor without conversion to the electrical domain. A lightpath is defined by a route and a wavelength. We assume that wavelength conversion along a lightpath is not permitted, since this technology is not yet fully available. Therefore, each lightpath should use the same wavelength from the transmitter to the receiver. The Routing and Wavelength Assignment problem consists in routing a set of lightpaths and assigning a wavelength to each of them. All connection requirements are known beforehand and one seeks to minimize the total number of wavelengths used for routing these connections, so as that two lightpaths sharing a common link use different wavelengths. In this work, we propose a new heuristic in which min-RWA is solved by a combined approach involving the computation of alternative routes for the lightpaths, followed by the solution of a Parttion Coloring Problem (PCP). Given a graph where the vertex set is partitioned in disjoint susets, PCP consists in selecting and coloring only one vertex in each subset, so as that every two adjacent colored nodes have different colors and the total number of colors used is minimum. We present and propose new heuristics for PCP and min-RWA. Computational experiments are reported comparing the new heuristics and those which already appeared in the literature.

La classe des graphes sans P5, c'est-à-dire des graphes ne contenant pas de chaîne induite à cinq sommets, est d'un intérêt particulier en théorie des graphes. Il s'agit en effet de la plus petite classe définie par un seul sous-graphe connexe interdit pour laquelle on ignore encore s'il existe un algorithme polynomial permettant de résoudre le problème du stable maximum. Or ce problème, dont on sait qu'il est difficile en général, est d'une grande importance en pratique (problèmes de planification, d'allocation de registres dans un processeur, biologie moléculaire...). Dans cette thèse, nous commençons par dresser un état de l'art complet des méthodes utilisées pour résoudre le problème dans des sous-classes de graphes sans P5, puis nous étudions et résolvons ce problème dans une sous-classe particulière, la classe des graphes sans P5 3-colorables. Nous apportons également des solutions aux problèmes de la reconnaissance et de la coloration de ces graphes, chaque fois en temps linéaire. Enfin, nous définissons, caractérisons et sommes capables de reconnaître les graphes "chain-probe", qui sont les graphes auxquels il est possible de rajouter des arêtes entre certains sommets de sorte qu'ils soient bipartis et sans P5. Les problèmes de ce type proviennent de la génétique et ont également des applications en intelligence artificielle. / The class of P5-free graphs, namely the graphs without induced chains with five vertices, is of particular interest in graph theory. Indeed, it is the smallest class defined by only one forbidden connected induced subgraph for which the complexity of the Maximum Independent Set problem is unknown. This problem has many applications in planning, CPU register allocation, molecular biology... In this thesis, we first give a complete state of art of the methods used to solve the problem in P5-free graphs subclasses; then we study and solve this problem in a particular subclass, the class of 3-colorable P5-free graphs. We also bring solutions to recognition and coloring problems of these graphs, each time in linear time. Finally, we define, characterize, and are able to recognize "chain-probe" graphs, namely the graphs for which we can add edges between particular vertices such that the resulting graph is bipartite and P5-free. Problems of this type come from genetics and have application in I.A.

Submitted by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:26:41Z No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:26:55Z (GMT) No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) / Approved for entry into archive by Milena Rubi (milenarubi@ufscar.br) on 2017-10-09T16:27:03Z (GMT) No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) / Made available in DSpace on 2017-10-09T16:27:11Z (GMT). No. of bitstreams: 1 CRUZ_Jadder_2017.pdf: 1326879 bytes, checksum: 61ee3c40e293d26085a939c0a0290716 (MD5) Previous issue date: 2017-05-02 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Let G = (V, E) be a simple and undirected graph. An edge-coloring is an assignment of colors to the edges of the graph such that any two adjacent edges receive different colors. The chromatic index of a graph G is the smallest number of colors such that G has an edge-coloring. Clearly, a lower bound for the chromatic index is the degree of the vertex of higher degree, denoted by ?(G). In 1964, Vizing proved that chromatic index is ?(G) or ?(G) + 1. The Classification Problem is to determine if the chromatic index is ?(G) (Class 1 ) or if it is ?(G) + 1 (Class 2 ). Let n be number of vertices of a graph G and let m be its number of edges. We say G is overfull if m > (n-1) 2 ?(G). Every overfull graph is Class 2. A graph is subgraph-overfull if it has a subgraph with same maximum degree and it is overfull. It is well-known that every overfull and subgraph-overfull graph is Class 2. The Overfull Conjecture asserts that every graph with ?(G) > n 3 is Class 2 if and only if it is subgraph-overfull. In this work we prove the Overfull Conjecture to a particular class of graphs, known as split-comparability graphs. The Overfull Conjecture was open to this class. / Dado um grafo simples e não direcionado G = (V, E), uma coloração de arestas é uma função que atribui cores às arestas do grafo tal que todas as arestas que incidem em um mesmo vértice têm cores distintas. O índice cromático é o número mínimo de cores para obter uma coloração própria das arestas de um grafo. Um limite inferior para o índice cromático é, claramente, o grau do vértice de maior grau, denotado por ?(G). Em 1964, Vizing provou que o índice cromático ou é ?(G) ou ?(G) + 1, surgindo assim o Problema da Classificação, que consiste em determinar se o índice cromático é ?(G) (Classe 1 ) ou ?(G) + 1 (Classe 2 ). Seja n o número de vértices de um grafo G e m seu número de arestas. Dizemos que um grafo é sobrecarregado se m > (n-1) 2 ?(G). Um grafo é subgrafo-sobrecarregado se tem um subgrafo de mesmo grau máximo que é sobrecarregado. É sabido que se um grafo é sobrecarregado ou subgrafo-sobrecarregado ele é necessariamente Classe 2. A Conjectura Overfull é uma famosa conjectura de coloração de arestas e diz que um grafo com ?(G) > n 3 é Classe 2 se e somente se é subgrafo-sobrecarregado. Neste trabalho provamos a Conjectura Overfull para uma classe de grafos, a classe dos grafos split-comparabilidade. Até este momento a Conjectura Overfull estava aberta para esta classe.

The aim of this study was to evaluate the efficiency of cleaning methods in removing pigment deposited on aesthetic brackets, after immersion in coffee. We selected 160 premolar brackets (80 monocrystalline and polycrystalline 80). The brackets were fixed on a glass blade and soon, thereafter, color measurement was performed using a spectrophotometer (T0). For each means of immersion, 80 brackets were selected (40 for each type of ceramic). Soon after staining (30 days of immersion), new color measurements were made (T1). Subsequently, the specimens were divided randomly into four groups for brushing, bleaching, blasting with sodium bicarbonate jet and sodium bicarbonate jet followed by bleaching. New color measurements were made after each cleaning method was used (T2). The color change of the brackets was evaluated according to two formulae, i.e., CIELAB and CIEDE2000. The differences between the average ΔE according to treatment, bracket, and solution were evaluated by linear regression analysis. The greatest staining was caused by coffee. The crystalline structure did not influence the color change. The methods with lower averages of ΔE for coffee were sodium bicarbonate jet followed by bleaching and bleaching, followed by the group that received brushing and sodium bicarbonate jet (both CIELAB as to CIEDE2000). The CIEDE2000 formula was more sensitive in detecting non-acceptable and perceptible differences in color when compared with the CIELAB formula. It was concluded that the most effective methods to remove pigment deposited on aesthetic brackets are sodium bicarbonate jet followed by bleaching and bleaching alone. / O objetivo desse estudo foi avaliar a eficiência dos métodos de limpeza na remoção de pigmentos depositados sobre bráquetes estéticos, após imersão em café. Foram selecionados 160 bráquetes (80 monocristalinos e 80 policristalinos) de pré-molares superiores. Os bráquetes foram fixados em uma lâmina de vidro e logo depois a mensuração de cor foi realizada com um espectrofotômetro (T0). Cada meio de imersão (café ou saliva) continha 80 bráquetes (40 para cada tipo de cerâmica). Logo após a coloração (30 dias de imersão) novas aferições foram feitas (T1). Posteriormente, os espécimes foram divididos randomicamente em 4 grupos: Grupo 1 Escovação; Grupo 2 Clareamento; Grupo 3 Jateamento com bicarbonato de sódio; Grupo 4 Jateamento com bicarbonato de sódio seguido de Clareamento. Novas aferições foram feitas depois de cada método de limpeza (T2). A variação da cor dos bráquetes foi avaliada de acordo com 2 fórmulas: CIELAB E CIEDE2000. As diferenças entre as médias de ΔE de acordo com o tratamento, braquete e solução foram avaliadas através de análise de regressão linear. O café promoveu maior manchamento. A estrutura cristalina não influenciou na alteração de cor. Os métodos com menores médias de ΔE, no café, foram o jateamento com posterior clareamento e o clareamento sozinho, seguido dos grupos que receberam jateamento e escovação (tanto para CIELAB quanto para CIEDE2000). A fórmula CIEDE2000 foi mais sensível em detectar diferenças de cor não-aceitáveis e perceptíveis quando comparado à fórmula CIELAB. Conclui-se que os métodos mais eficazes na remoção de pigmentos depositados sobre bráquetes estéticos são o jateamento com bicarbonato de sódio com posterior clareamento e o clareamento sozinho.

Made available in DSpace on 2015-05-14T13:21:35Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 5352516 bytes, checksum: 794641cb921c8b2deee06ca5e6ee12ed (MD5) Previous issue date: 2014-04-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / A portable and low-cost photometer is proposed in this work. The instrument uses a tri-color light emitting diode (LED) as its radiation source in maximum emission wavelengths of 480 (blue), 534 (green) and 630 nm (red). It employs a phototransistor with spectral sensitivity in the visible region, as well as an Arduino microcontroller. Its analytical performance was evaluated by means of quantitative analysis (analytical curves), whose models were validated by analysis of variance (ANOVA). The instrument was applied to determine sunset yellow dye in energy drinks and sodas, and potassium permanganate pills. For comparison purposes, a commercial spectrophotometer was used to construct the calibration curves for the reference method. Applying the paired t-test at a 95 % confidence level for the concentration results obtained with the two instruments, we observed no statistically significant difference. Furthermore, accurate concentration estimates were obtained for the analytes as confirmed by the low relative standard deviation range of 0.2 and 0.5%, respectively, for both the dye and the permanganate. The proposed photometer might be an economically viable alternative to spectroscopic analysis, especially in teaching laboratories with limited financial resources or lacking in highly qualified personnel. / Um fotômetro portátil e de baixo custo é proposto neste trabalho. Esse instrumento utiliza um diodo emissor de luz (LED-Light Emitting Diode) tricolor como fonte de radiação nos comprimentos de onda do máximo de emissão de 480 (azul), 534 (verde) e 630 nm (vermelho). Além disso, emprega um fototransistor com sensibilidade espectral na região do visível como fototransdutor, bem como um microcontrolador Arduino como unidade de controle. Seu desempenho analítico foi avaliado por meio de análises quantitativas baseadas em curvas analíticas, cujos modelos foram validados por meio da Análise de Variância (ANOVA). O instrumento foi aplicado à determinação do corante amarelo crepúsculo em amostras de refrigerantes e bebidas energéticas e de permanganato de potássio em amostras de medicamentos. Para fins de comparação, um espectrofotômetro comercial foi empregado para construir as curvas analíticas do instrumento de referência. Aplicando o teste t-emparelhado ao nível de 95% de confiança para os resultados de concentração obtidos com os dois instrumentos, observa-se que não houve diferença estatisticamente significativa. Ademais, resultados precisos nas estimativas das concentrações dos analitos foram obtidos sendo atestado pelo baixo desvio padrão relativo conjunto de 0,2 e 0,5%, respetivamente, para o corante e permanganato. O fotômetro proposto pode ser uma alternativa economicamente viável para análises espectrométricas, sobretudo, em laboratórios de ensino com poucos recursos financeiros e carentes de pessoal altamente qualificado.

Presente estudo teve como objetivo avaliar a utilização da tecnologia de banda estreita com filtros ópticos (TBE) no rastreamento do carcinoma espinocelular do esôfago (CEC), utilizando como método comparativo a cromoscopia com a solução de Lugol. Trata-se de um estudo prospectivo de teste de diagnóstico, para o qual foram avaliados 129 pacientes do Hospital das Clínicas da Faculdade de Medicina da Universidade de São Paulo (HC-FMUSP), com diagnóstico de carcinoma epidermóide de cabeça e pescoço, em programa de rastreamento de tumores secundários, no período de agosto de 2006 a fevereiro de 2007. Os exames de endoscopia convencional, TBE e a cromoscopia com Lugol foram realizados consecutivamente em um mesmo procedimento, e as lesões encontradas foram registradas e submetidas a biópsias. Foram calculados para cada método valores da sensibilidade, especificidade, acurácia, valores preditivos positivos e negativos, valores de verossimilhança positivo e negativo. Foram diagnosticados nove carcinomas superficiais (7%), sendo cinco carcinomas in situ e quatro carcinomas intramucosos, todos detectados pelo TBE e pelo Lugol, porém apenas seis foram diagnosticados pelo exame convencional e destes, nenhum foi menor ou igual a 10 mm. A tecnologia de bandas estreitas com filtros ópticos (TBE) sem magnificação de imagem apresentou resultados superponíveis a cromoscopia com Lugol, método atualmente de escolha para rastreamento do CEC esofágico em grupos de pacientes de alto risco, portadores de tumores de cabeça e pescoço / Background and study aims: The aim of this study was to compare narrow band imaging (NBI) without magnification and chromoendoscopy with Lugols solution for detecting superficial esophageal squamous cell carcinoma in patients with head and neck cancer. Patients and methods: This is a prospective observational study of 129 patients with primary head and neck tumors consecutively referred to the Gastrointestinal Endoscopy Unit of Hospital das Clínicas, São Paulo University Medical School (FMUSP), Brazil, between August 2006 and February 2007. Conventional examinations, NBI and Lugol chromoendoscopy were consecutively performed, and the detected lesions were mapped, recorded and sent for biopsy. The results of the three methods were compared regarding sensitivity, specificity, accuracy, positive predictive value, negative predictive value, positive likelihood value and negative likelihood value. Results: Of the 129 patients, nine (7%) were diagnosed with carcinomas, five of which were in situ and four intramucosal. All carcinomas were detected through NBI and Lugol chromoendoscopy. Only six lesions were diagnosed by conventional examination, all of which were larger than 10 mm. Conclusions: Narrow-band imaging technology with optical filters has high sensitivity and high negative predictive value for detecting superficial esophageal squamous cell carcinomas and produces results comparable to those obtained with 2.0% Lugol chromoendoscopy in patients with head and neck cancer

Submitted by Celso Magalhaes (celsomagalhaes@ufrrj.br) on 2017-07-11T12:30:26Z No. of bitstreams: 1 2016 - Odilon Magno da Silva J?nior.pdf: 3269429 bytes, checksum: b0bdf0f0a5612790959d29453f0ac06d (MD5) / Made available in DSpace on 2017-07-11T12:30:26Z (GMT). No. of bitstreams: 1 2016 - Odilon Magno da Silva J?nior.pdf: 3269429 bytes, checksum: b0bdf0f0a5612790959d29453f0ac06d (MD5) Previous issue date: 2016-08-03 / The main objective of this work is to describe an experience with problems related to graph coloring with a group of 2nd year high school students. The survey worked with students from a private school located in the city of Volta Redonda, in the state of Rio de Janeiro. This research had the participation of 51 students aged 15 to 17 years, among boys and girls, who wanted to voluntarily participate in the extracurricular classes offered. The idea of this work is to use the fact that the basic concepts of coloring in Graph Theory are easily accessible to students, they are powerful optimization tools used by large companies and are applicable to students' everyday problems, three precious characteristics for a Professor to attract the attention of the class. In this regard, we held 8 meetings with students. At first, there was a Motivational pre-test based on Gontijo?s test in order to evaluate various aspects of the relationship of students with mathematics. In the second meeting, a Content Pre-test with everyday students' problems commonly solved by graphs' techniques, but that can also be solved without them. Over the next four meetings, classes were held in order to teach some basic techniques of graphs and discuss with students what they did on the test. After those four classes, the next meeting was used for the students to take a Content Post-test with similar problems, but with the intention of observing how the students would apply the techniques they learned. On the last meeting, the students took a Motivational Post-test, so that they could give their opinion on the activities. All data were studied, analyzed and compared in the final chapters / Este trabalho tem por principal objetivo descrever uma experi?ncia com problemas relacionados a colora??o em Grafos com um grupo de alunos do 2? ano do Ensino M?dio. A pesquisa realizada trabalhou com alunos de uma escola da rede particular, localizada no munic?pio de Volta Redonda, no estado do Rio de Janeiro. Esta pesquisa contou com a participa??o de 51 alunos na faixa et?ria de 15 a 17 anos, entre meninos e meninas, que quiseram voluntariamente participar das aulas extracurriculares oferecidas. A ideia do trabalho ? utilizar o fato de que conceitos b?sicos de colora??o em Teoria de Grafos s?o de f?cil acesso aos alunos, s?o poderosas ferramentas de Otimiza??o usadas por grandes empresas e s?o aplic?veis a problemas do cotidiano dos alunos, tr?s caracter?sticas preciosas para que um professor atraia a aten??o da classe. Neste sentido foram realizados 8 encontros com os alunos. No primeiro, foi realizado um Pr?-teste Motivacional, baseado no teste de Gontijo, com o intuito de avaliar v?rios aspectos relativos ? rela??o dos alunos com a Matem?tica. No segundo, um Pr?-teste de Conte?do, com problemas que fazem parte do dia-a-dia dos alunos e comumente resolvidos com t?cnicas de Grafos, mas que tamb?m podem ser resolvidos sem elas. Nos quatro encontros seguintes, foram realizadas aulas com o objetivo de ensinar algumas t?cnicas b?sicas de Grafos e comentar com os alunos o que eles fizeram no teste. Depois das aulas, no pen?ltimo encontro foi realizado um P?s-teste de Conte?do, com quest?es similares ao primeiro, mas com o intuito de observar os alunos aplicando as t?cnicas aprendidas. No ?ltimo encontro foi realizado um P?s-teste Motivacional, para que os alunos dessem suas opini?es sobre as atividades. Todos os dados foram estudados, analisados e comparados nos cap?tulos finais.

Orientador: Christiane Neme Campos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:02:03Z (GMT). No. of bitstreams: 1 Galvao_KaioKaram_M.pdf: 1971760 bytes, checksum: e2f60ab09595b03fa6da5051cd78e3f3 (MD5) Previous issue date: 2013 / Resumo: Em 1971, Fulkerson propôs a seguinte conjetura: todo grafo cúbico sem arestas de corte admite seis emparelhamentos perfeitos tais que cada aresta do grafo pertence a exatamente dois destes emparelhamentos. A Conjetura de Fulkerson tem desafiado pesquisadores desde sua publicação. Esta conjetura é facilmente verificada para grafos cúbicos 3-aresta-coloráveis. Portanto, a dificuldade do problema reside em estabelecer a conjetura para grafos cúbicos sem arestas de corte que não possuem 3-coloração de arestas. Estes grafos são chamados snarks. Nesta dissertação, a Conjetura de Fulkerson e os snarks são introduzidos com ¿ênfase em sua história e resultados mais relevantes. Alguns resultados relacionados à Conjetura de Fulkerson são apresentados, enfatizando suas conexões com outras conjeturas. Um breve histórico do Problema das Quatro Cores e suas relações com snarks também são apresentados. Na segunda parte deste trabalho, a Conjetura de Fulkerson é verificada para algumas famílias infinitas de snarks construídas com o método de Loupekine, utilizando subgrafos do Grafo de Petersen. Primeiramente, mostramos que a família dos LP0-snarks satisfaz a Conjetura de Fulkerson. Em seguida, generalizamos este resultado para a família mais abrangente dos LP1-snarks. Além disto, estendemos estes resultados para Snarks de Loupekine construídos com subgrafos de snarks diferentes do Grafo de Petersen / Abstract: In 1971, Fulkerson proposed a conjecture that states that every bridgeless cubic graph has six perfect matchings such that each edge of the graph belongs to precisely two of these matchings. Fulkerson's Conjecture has been challenging researchers since its publication. It is easily verified for 3-edge-colourable cubic graphs. Therefore, the difficult task is to settle the conjecture for non-3-edge-colourable bridgeless cubic graphs, called snarks. In this dissertation, Fulkerson's Conjecture and snarks are presented with emphasis in their history and remarkable results. We selected some results related to Fulkerson's Conjecture, emphasizing their reach and connections with other conjectures. It is also presented a brief history of the Four-Colour Problem and its connections with snarks. In the second part of this work, we verify Fulkerson's Conjecture for some infinite families of snarks constructed with Loupekine's method using subgraphs of the Petersen Graph. More specifically, we first show that the family of LP0-snarks satisfies Fulkerson's Conjecture. Then, we generalise this result by proving that Fulkerson's Conjecture holds for the broader family of LP1-snarks. We also extend these results to even more general Loupekine Snarks constructed with subgraphs of snarks other than the Petersen Graph / Mestrado / Ciência da Computação / Mestre em Ciência da Computação