著色問題(graph coloring problem)的研究已行之有年，並衍生出廣泛的實際應用，但還缺乏一般化的著色問題模型。本論文建構一般化的著色問題模型，其目標函數包含顏色成本的固定支出和點著色變動成本。此著色模型為0/1整數線性規畫模型，其限制式含有選點問題(node packing problem)的限制式。我們利用圖中的極大團(maximal clique)所構成的強力限制式，取代原有的選點限制式，縮短求解時間。我們更進一步舉出一個特殊指派問題並將此著色模型應用於此指派問題上。本論文亦針對此指派問題發展了一個演算法來尋找極大團。計算結果顯示極大團限制式對於此著色問題模型的求解有極大的效益。 / The graph coloring problem (GCP) has been studied for a long time and it has a wide variety of applications. A straightforward formulation of graph coloring problem has not been formulated yet. In this paper, we formulate a general GCP model that concerns setup cost and variable cost of different colors. The resulting model is an integer program that involves the packing constraint. The packing constraint in the GCP model can be replaced by the maximal clique constraint in order to shorten the solution time. A special assignment problem is presented which essentially is a GCP model application. An algorithm of finding maximal cliques for this assignment problem is developed. The computational results show the efficiency of maximal clique constraints for the GCP problem.

No description available.

Le calcul du nombre chromatique et la détermination d'une colo- ration optimale des sommets d'un graphe sont des problèmes NP- difficiles en général. Ils peuvent cependant être résolus en temps po- lynomial dans les graphes parfaits. Par ailleurs, la perfection d'un graphe peut être décidée efficacement. Les graphes parfaits sont caractérisés par la structure de leur poly- tope des stables : les facettes non-triviales sont définies exclusivement par des inégalités de cliques. Réciproquement, une structure similaire des facettes du polytope des stables détermine-t-elle des propriétés combinatoires et algorithmiques intéressantes? Un graphe est h-parfait si les facettes non-triviales de son polytope des stables sont définies par des inégalités de cliques et de circuits impairs. On ne connaît que peu de résultats analogues au cas des graphes parfaits pour la h-perfection, et on ne sait pas si les problèmes sont NP-difficiles. Par exemple, les complexités algorithmiques de la re- connaissance des graphes h-parfaits et du calcul de leur nombre chro- matique sont toujours ouvertes. Par ailleurs, on ne dispose pas de borne sur la différence entre le nombre chromatique et la taille maxi- mum d'une clique d'un graphe h-parfait. Dans cette thèse, nous montrons tout d'abord que les opérations de t-mineurs conservent la h-perfection (ce qui fournit une extension non triviale d'un résultat de Gerards et Shepherd pour la t-perfection). De plus, nous prouvons qu'elles préservent la propriété de décompo- sition entière du polytope des stables. Nous utilisons ce résultat pour répondre négativement à une question de Shepherd sur les graphes h-parfaits 3-colorables. L'étude des graphes minimalement h-imparfaits (relativement aux t-mineurs) est liée à la recherche d'une caractérisation co-NP com- binatoire de la h-perfection. Nous faisons l'inventaire des exemples connus de tels graphes, donnons une description de leur polytope des stables et énonçons plusieurs conjectures à leur propos. D'autre part, nous montrons que le nombre chromatique (pondéré) de certains graphes h-parfaits peut être obtenu efficacement en ar- rondissant sa relaxation fractionnaire à l'entier supérieur. Ce résultat implique notamment un nouveau cas d'une conjecture de Goldberg et Seymour sur la coloration d'arêtes. Enfin, nous présentons un nouveau paramètre de graphe associé aux facettes du polytope des couplages et l'utilisons pour donner un algorithme simple et efficace de reconnaissance des graphes h- parfaits dans la classe des graphes adjoints. / Computing the chromatic number and finding an optimal coloring of a perfect graph can be done efficiently, whereas it is an NP-hard problem in general. Furthermore, testing perfection can be carried- out in polynomial-time. Perfect graphs are characterized by a minimal structure of their sta- ble set polytope: the non-trivial facets are defined by clique-inequalities only. Conversely, does a similar facet-structure for the stable set polytope imply nice combinatorial and algorithmic properties of the graph ? A graph is h-perfect if its stable set polytope is completely de- scribed by non-negativity, clique and odd-circuit inequalities. Statements analogous to the results on perfection are far from being understood for h-perfection, and negative results are missing. For ex- ample, testing h-perfection and determining the chromatic number of an h-perfect graph are unsolved. Besides, no upper bound is known on the gap between the chromatic and clique numbers of an h-perfect graph. Our first main result states that the operations of t-minors keep h- perfection (this is a non-trivial extension of a result of Gerards and Shepherd on t-perfect graphs). We show that it also keeps the Integer Decomposition Property of the stable set polytope, and use this to answer a question of Shepherd on 3-colorable h-perfect graphs in the negative. The study of minimally h-imperfect graphs with respect to t-minors may yield a combinatorial co-NP characterization of h-perfection. We review the currently known examples of such graphs, study their stable set polytope and state several conjectures on their structure. On the other hand, we show that the (weighted) chromatic number of certain h-perfect graphs can be obtained efficiently by rounding-up its fractional relaxation. This is related to conjectures of Goldberg and Seymour on edge-colorings. Finally, we introduce a new parameter on the complexity of the matching polytope and use it to give an efficient and elementary al- gorithm for testing h-perfection in line-graphs.

Este trabalho investiga os pressupostos e fundamentos da Teoria das Cores de Goethe (Farbenlehre) como parte dos seus empenhos enquanto cientista da natureza. Apresenta a tradução de um texto seu sobre o método científico (Kautelen des Beobachters) e de um segundo texto sobre experimentos prismáticos (Beitrag zur Optik), no qual ele lança as bases do seu trabalho de mais de 30 anos sobre as cores. Estes textos, até então inexistentes em português, fornecem os subsídios para um entendimento mais amplo da Farbenlehre. E a pesquisa como um todo se orienta no sentido de contribuir para um resgate da fenomenologia goetheana para o ambiente cultural da atualidade. / This work investigates the principles and bases of Goethe\'s Theory of Colours (Farbenlehre\") as part of his studies as a Natures scientist. A translation of Goethe\'s essay on scientific methods (\"Kautelen des Beobachters\") and another on prismatic experiments (\"Beitrag zur Optik\"), where he sets the bases of his 30 years work on colours studies, are presented in this work too. The papers translated here were never before available in Portuguese, and they represent relevant subsidies for a comprehensive understanding of the \"Farbenlehre\". This research aims to contribute to the recovery of the Goethean\'s Phenomenology for the cultural enviroment of our days.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-10-22T14:20:36Z No. of bitstreams: 2 Dissertação - Alexandre Carlos da Silva Teixeira - 2015.pdf: 5570395 bytes, checksum: 56c1a16748accf85c9390695464810aa (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-10-22T14:22:35Z (GMT) No. of bitstreams: 2 Dissertação - Alexandre Carlos da Silva Teixeira - 2015.pdf: 5570395 bytes, checksum: 56c1a16748accf85c9390695464810aa (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-10-22T14:22:35Z (GMT). No. of bitstreams: 2 Dissertação - Alexandre Carlos da Silva Teixeira - 2015.pdf: 5570395 bytes, checksum: 56c1a16748accf85c9390695464810aa (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-06-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This paper presents a proposal for relationship studies between mathematics and music, a relationship that has been established since the dawn of humanity, and could be seen more clearly from the studies developed by Pythagoras. We approach the evolution of music in the historical context and introduce the basics of music theory, essential to establishing relationships with mathematics. Our e orts were focused on instruments with strings, by which present a relationship between a musical scale, called Chromatic and geometric progressions; also we present a relationship between musical intervals and right triangles. We present a mathematical relationship between music and colors, through their respective frequencies of sound and light. Also we address the present mathematics in the construction of some instruments with strings, via Golden Proportion, and nished the work presented some proposals for activities that can be worked in the classroom, aimed at high school students. / Este trabalho traz uma proposta de estudos da relação existente entre a Matemática e a Música, relação esta que foi estabelecida desde os primórdios da humanidade, e pôde ser observada de forma mais clara a partir dos estudos desenvolvidos por Pitágoras. Abordamos a evolução da Música no contexto histórico e introduzimos as noções básicas de teoria musical, essencial ao estabelecimento de relações com a Matemática. Nossos esforços foram focados nos instrumentos com cordas, pelos quais apresentamos uma relação entre uma escala musical, denominada Cromática, e as progressões geométricas; também apresentamos uma relação entre intervalos musicais e os triângulos retângulos. Apresentamos uma relação matemática entre a Música e as cores, por meio de suas respectivas frequências de som e luz. Também abordamos a matemática presente na construção de alguns instrumentos com cordas, via Proporção Áurea, e nalizamos o trabalho apresentando algumas propostas de atividades que podem ser trabalhadas em sala de aula, voltadas para alunos do Ensino Médio.

Esta dissertação de mestrado investiga os formatos de modulação óptica alternativos ao tradicional formato binário de intensidade (NRZ - Non-return-to-zero), ditos avançados, como tecnologia chave para atender às exigências do mercado atual de telecomunicações por transporte de grande volume de dados e alta largura de banda, associados com a redução do custo da informação transmitida por bit. Os formatos avançados de modulação óptica fazem parte das tecnologias que estão sendo investigadas intensamente com o objetivo de superar os desafios impostos pela nova geração de sistemas ópticos com taxas a partir de 40 Gb/s. Este trabalho focaliza o estudo dessa tecnologia, apresentando uma visão geral dos formatos mais discutidos atualmente, suas características e tecnologias de implementação. Foram realizadas simulações utilizando o software comercial Optisystem versão 7.0 da empresa canadense Optiwave Systems Inc., para analisar o desempenho de alguns formatos de modulação de intensidade e de fase com respeito à sensibilidade do receptor, resistência ao cascateamento de filtragem óptica e a efeitos dispersivos e não-lineares. Procurou-se avaliar os formatos em enlaces reais, com características necessárias à sua possível utilização. Também é feita uma breve consideração dos custos associados aos formatos de modulação analisados neste trabalho. Dentre os formatos analisados, os RZ (Return-to zero) apresentaram maior sensibilidade do receptor e melhor tolerância aos efeitos não-lineares que os seus equivalentes NRZ, porém baixa tolerância aos efeitos dispersivos e ao cascateamento de filtragem óptica. O formato duobinário mostrou fraco desempenho de sensibilidade, mas provou ser o mais tolerante à dispersão cromática e à concatenação de filtragem óptica. Os formatos de modulação de fase mostraram ser bem resistentes aos efeitos não-lineares e aos efeitos dispersivos. / This MSc thesis investigates optical modulation formats as an alternative to the use of the traditional intensity binary format NRZ (Non-return-to-zero). Those formats, classified as advanced, represent one of the key technologies aimed to enable the high data volume and broadband, demanded by the present telecommunication market, with cost reduction of transmitted information per bit. Those technologies have been intensevely studied with purpose of overcoming the challenges imposed by the new generation of optical systems, with bit rates from 40 Gb/s. This work focuses on the study of modulation formats most discussed currently, presenting an overview of their main characteristics and implementation techniques. The performance of some intensity and phase formats, in terms of receiver sensitivity, optical filtering cascading, dispersion and nonlinear effects robustness, have been theoretically analyzed from simulations carried out with the commercial software Optisystem v. 7.0, of the Canadian company Optiwave Systems Inc. The analysis has been applied to real optical links, with characteristics that, potentially, demand their use. A cost analysis, based on estimated values associated to devices required for implementing the formats investigated in this work, is also presented. Among the formats studied, those based on RZ (Return-to zero) presented the highest receiver sensitivity and best tolerance to nonlinear effects, in comparison to their equivalent formats, based on NRZ. However, they are less tolerant to dispersive effects and optical filtering cascading. The duobinary format (DB) has shown a weak performance in terms of sensitivity, though has been proved to be the most tolerant to chromatic dispersion and filtering cascading effects. Among all formats, the phase modulation ones presented the highest resistance against nonlinear and dispersive effects.

Un graphe métrique G(X;D) est un graphe dont l’ensemble des sommets est l’ensemble X des points d’un espace métrique (X; d), et dont les arêtes relient les paires fx; yg de sommets telles que d(x; y) 2 D. Dans cette thèse, nous considérons deux problèmes qui peuvent être interprétés comme des problèmes de graphes métriques dans Rn. Premièrement, nous nous intéressons au célèbre problème d’empilements de sphères, relié au graphe métrique G(Rn; ]0; 2r[) pour un rayon de sphère r donné. Récemment, Venkatesh a amélioré d’un facteur log log n la meilleure borne inférieure connue pour un empilement de sphères donné par un réseau, pour une suite infinie de dimensions n. Ici nous prouvons une version effective de ce résultat, dans le sens où l’on exhibe, pour la même suite de dimensions, des familles finies de réseaux qui contiennent un réseaux dont la densité atteint la borne de Venkatesh. Notre construction met en jeu des codes construits sur des corps cyclotomiques, relevés en réseaux grâce à un analogue de la Construction A. Nous prouvons aussi un résultat similaire pour des familles de réseaux symplectiques. Deuxièmement, nous considérons le graphe distance-unité G associé à une norme k_k. Le nombre m1 (Rn; k _ k) est défini comme le supremum des densités réalisées par les stables de G. Si la boule unité associée à k _ k pave Rn par translation, alors il est aisé de voir que m1 (Rn; k _ k) > 1 2n . C. Bachoc et S. Robins ont conjecturé qu’il y a égalité. On montre que cette conjecture est vraie pour n = 2 ainsi que pour des régions de Voronoï de plusieurs types de réseaux en dimension supérieure, ceci en se ramenant à la résolution de problèmes d’empilement dans des graphes discrets. / A distance graph G(X;D) is a graph whose set of vertices is the set of points X of a metric space (X; d), and whose edges connect the pairs fx; yg such that d(x; y) 2 D. In this thesis, we consider two problems that may be interpreted in terms of distance graphs in Rn. First, we study the famous sphere packing problem, in relation with thedistance graph G(Rn; (0; 2r)) for a given sphere radius r. Recently, Venkatesh improved the best known lower bound for lattice sphere packings by a factor log log n for infinitely many dimensions n. We prove an effective version of this result, in the sense that we exhibit, for the same set of dimensions, finite families of lattices containing a lattice reaching this bound. Our construction uses codes over cyclotomic fields, lifted to lattices via Construction A. We also prove a similar result for families of symplectic lattices. Second, we consider the unit distance graph G associated with a norm k _ k. The number m1 (Rn; k _ k) is defined as the supremum of the densities achieved by independent sets in G. If the unit ball corresponding with k _ k tiles Rn by translation, then it is easy to see that m1 (Rn; k _ k) > 1 2n . C. Bachoc and S. Robins conjectured that the equality always holds. We show that this conjecture is true for n = 2 and for several Voronoï cells of lattices in higher dimensions, by solving packing problems in discrete graphs.

Actuellement, la presbytie peut être corrigée chirurgicalement à l’aide d’implants intraoculaires réfractifs ou diffractifs multifocaux (chirurgie endoculaire invasive et irréversible) ou en intracornéen avec une correction multifocale réfractive (correction laser irréversible, ou insertion d’un implant dans le stroma). L’objectif de ce travail est de développer un nouvel implant permettant de corriger la presbytie, qui allie l’innocuité et la réversibilité d’une correction intracornéenne, à l’efficacité du diffractif. Le design des profils optiques bifocaux a été permis grâce au développement d’outils de simulation optique. Les efficacités de diffraction sont calculées à partir de la propagation du champ électrique par spectre angulaire. La qualité optique est déterminée d’après les simulations de Fonction de Transfert de Modulation obtenues sous Zemax. Des simulations de rendu d’images permettent de visualiser les effets de différents profils envisagés. Les paramètres critiques du design optique sont déterminés. Le choix du matériau dépend des contraintes de biocompatibilité de l’implant et des techniques de fabrication. La solution retenue est un hydrogel à forte teneur en eau, couplé à une nouvelle architecture de l’implant. L’hydrogel est obtenu par polymérisation radicalaire de macromonomères difonctionnels de poly(éthylène glycol) de masses molaires de l’ordre de 8000 g.mol‐1 qui conduisent à des propriétés mécaniques et une perméabilité aux nutriments compatibles avec l’application. La réalisation, la stérilisation et la caractérisation optique de prototypes ont abouti à la preuve du concept d’un implant bifocal diffractif intracornéen / Presbyopia can be corrected with surgery by means of refractive or diffractive multifocal intraocular lenses (which imply an irreversible and invasive endocular surgery) or by intracorneal multifocal refractive correction (irreversible laser correction, or insertion of an intrastromal implant). This work aims at developing a new implant to correct presbyopia, which takes advantage of both the harmlessness and the reversibility of an intracorneal correction, and the efficiency of diffractive optics. The design of the bifocal optical profiles was based on the development of optical simulation tools. The diffractive efficiencies are calculated from the distribution of the electric field with the method of angular spectrum. The optical quality is determined according to the simulations of Modulation Transfer Function obtained with Zemax. Images simulations show the effects of the different profiles studied. The critical parameters of the optical design are also determined. The choice of the material depends on several constraints such as biocompatibility and techniques of manufacturing. The adopted solution relies on the used of an hydrogel with high water content and the design of a new implant architecture. The hydrogel is obtained by radical polymerization of difunctional macromonomers of poly(ethylene glycol) with molar masses around 8000 g.mol‐1, allowing mechanical properties and permeability to nutriments compatible with the application. The realization, the sterilization and the characterization of prototypes showed the proof of the concept of a diffractive bifocal intracorneal implant

Současný vývoj v oblasti nízkovoltové elektronové mikrokospie vede ke zlepšování prostorového rozlišení cestou korekce elektronově-optických vad. V posledních letech se implementace korektorů u konvenčních elektronových mikroskopů (50-200 kV) stává standardem. Nicméně zabudování korektoru do malého stolního prozařovacího mikroskopu pracujícího s nízkým urychlovacím napětím je stále výzva. Velmi vhodným řešením korekce otvorové vady u takovýchto přístrojů se zdá být koncept hexapólového korektoru založeného na bázi permantních magnetů umožňující zachovat minimální rozměry stolního transmisního mikroskopu. Přednosti a potenciál Roseho hexapólového korektoru vzhledem k použití v nízkovoltových systémech jsou předmětem kritické analýzy obsažené v této práci, včetně zásadního příspěvku tohoto korektoru k celkové chromatické vadě přístroje. Chromatická vada zůstává, navzdory veškeré snaze o její minimalizaci, zcela zásadním aspektem při návrhu korektoru. Koncept představený v rámci této dizertační práce je určen především pro skenovací prozařovací transmisní mód z důvodu omezení nárůstu chromatické vady způsobeného průchodem elektronového svazku preparátem. V práci lze také nalézt podrobný popis navržených kompenzačních systémů korektoru určených k precisnímu seřízení optické soustavy.

The main goal of the master’s thesis was to familiarize with optical networks dilemma and its measuring during fabrication. The whole thesis is divided into several parts where the first part deals with optic fiber dilemma. It describes its kinds, properties and also suggests a basic principle of optic signal dispersion using these fibers. It describes also optical network FTTx architecture (Fiber To The x). The second part of the thesis focuses on methods of measuring key parameters of optical networks. Is brings out the methods of measuring optical loss and dispersive influences. The last and final part in focused on creating a methodical manual for measuring these networks during its fabrication and verifying measuring methods stated in the theoretical part inside a real network. Measuring was implemented on an optical network of Masaryk University in Brno.