A Dual-Eulerian graph is a plane multigraph G that contains an edge list which is simultaneously an Euler tour in G and an Euler tour in the dual of G. Dual-Eulerian tours play an important role in optimizing CMOS layouts of Boolean functions. When circuits are represented by undirected multigraphs the layout area of the circuit can be optimized through finding the minimum number of disjoint dual trails that cover the graph. This paper presents an implementation of a polynomial time algorithm for determining whether or not a plane multigraph is Dual-Eulerian and for finding the Dual-Eulerian trail if it exists.

In this thesis we consider two sets of combinatorial structures defined on an Eulerian graph: the Eulerian orientations and Euler tours. We are interested in the computational problems of counting (computing the number of elements in the set) and sampling (generating a random element of the set). Specifically, we are interested in the question of when there exists an efficient algorithm for counting or sampling the elements of either set. The Eulerian orientations of a number of classes of planar lattices are of practical significance as they correspond to configurations of certain models studied in statistical physics. In 1992 Mihail and Winkler showed that counting Eulerian orientations of a general Eulerian graph is #P-complete and demonstrated that the problem of sampling an Eulerian orientation can be reduced to the tractable problem of sampling a perfect matching of a bipartite graph. We present a proof that this problem remains #Pcomplete when the input is restricted to being a planar graph, and analyse a natural algorithm for generating random Eulerian orientations of one of the afore-mentioned planar lattices. Moreover, we make some progress towards classifying the range of planar graphs on which this algorithm is rapidly mixing by exhibiting an infinite class of planar graphs for which the algorithm will always take an exponential amount of time to converge. The problem of counting the Euler tours of undirected graphs has proven to be less amenable to analysis than that of Eulerian orientations. Although it has been known for many years that the number of Euler tours of any directed graph can be computed in polynomial time, until recently very little was known about the complexity of counting Euler tours of an undirected graph. Brightwell and Winkler showed that this problem is #P-complete in 2005 and, apart from a few very simple examples, e.g., series-parellel graphs, there are no known tractable cases, nor are there any good reasons to believe the problem to be intractable. Moreover, despite several unsuccessful attempts, there has been no progress made on the question of approximability. Indeed, this problem was considered to be one of the more difficult open problems in approximate counting since long before the complexity of exact counting was resolved. By considering a randomised input model, we are able to show that a very simple algorithm can sample or approximately count the Euler tours of almost every d-in/d-out directed graph in expected polynomial time. Then, we present some partial results towards showing that this algorithm can be used to sample or approximately count the Euler tours of almost every 2d-regular graph in expected polynomial time. We also provide some empirical evidence to support the unproven conjecture required to obtain this result. As a sideresult of this work, we obtain an asymptotic characterisation of the distribution of the number of Eulerian orientations of a random 2d-regular graph.

Made available in DSpace on 2016-06-02T20:28:28Z (GMT). No. of bitstreams: 1 5476.pdf: 893744 bytes, checksum: e444c4faa79c02073abeef63581d7ed5 (MD5) Previous issue date: 2013-08-27 / Financiadora de Estudos e Projetos / In this work we present some applications of graph theory in problems involving polynomial identities for the algebra Mn (K). A brief presentation of PI-theory and some concepts of graph theory, such as the definition of Eulerian graphs, which are the basic elements of this work, were presented to make the text self- contained. We show two different proofs of the Amitsur-Levitzki theorem, the proof of Razmyslov and other due to Swan's theorem - an important result on Eulerian graphs. Finally, a similar result of the Amitsur-Levitzki's theorem for skew-symmetric matrices is proved using elements of graph theory. We emphasize that the understanding of the technique makes it possible to simplify many results and has been an important tool in the study of PI-algebras. / Neste trabalho apresentamos algumas aplicações de Teoria de Grafos em problemas envolvendo identidades polinomiais para a álgebra das matrizes Mn (K). Uma breve apresentação de PI-teoria e de alguns on eitos de Teoria de Grafos, como a de_- nição de grafos eulerianos, que são os elementos básicos desta abordagem, foram apresentadas para tornar o texto auto contido. São explicitadas duas demonstrações distintas do Teorema de Amitsur-Levitzki, a de Razmyslov e uma de corrente do Teorema de Swan - um resultado importante a respeito de grafos eulerianos. Por _m, um resultado semelhante ao Teorema de Amitsur-Levitzki para matrizes antis- simétricas é demonstrado utilizando elementos de Teoria de Grafos. Ressaltamos que o entendimento da técnica utilizada torna possível a simplificação de diversos resultados e tem se mostrado uma importante ferramenta no estudo de PI-álgebras.

[pt] O presente trabalho busca apresentar uma proposta de inclusão de tópicos elementares da teoria de Grafos, com destaque para os Grafos Eulerianos, na educação básica. Iniciamos com uma introdução a essa teoria destacando algumas definições importantes que fundamentam o trabalho além de concepções teóricas relevantes para tratar da questão específica dos Grafos Eulerianos. Posteriormente, algumas sugestões de atividades sobre o tema, que podem ser aplicadas em qualquer nível da educação básica desde o Ensino Fundamental até o Ensino Médio, são apresentadas com o intuito de auxiliar e inspirar o professor desse segmento que esteja interessado em utilizar novas propostas na sua prática pedagógica. Assim, esse profissional pode se valer do presente trabalho como um recurso motivador para novas construções ou simplesmente adaptá-lo, alterá-lo e/ou utilizá-lo na realidade da sua sala de aula. Algumas das atividades propostas foram aplicadas com alunos do sétimo ano de uma escola pública do Rio de Janeiro e a metodologia e avaliação desta aplicação encontram-se também descritas no presente estudo. Desta forma, pretende-se promover uma reflexão sobre novas estratégias que incrementem o processo de ensino-aprendizagem da Matemática na busca de uma educação Matemática mais autônoma e mais significativa. / [en] This paper seeks to show a proposal of inclusion of elementary topics of Graphs theory, with emphasis in Eulerian graphs, on basic school. We begin with an introduction to this theory highlighting some important definitions which underpin this paper beyond relevant theoretical conceptions to deal with the specific issue of Eulerian graphs. In addition, some suggestions of activities on the subject, which can be applied in any level of basic education, from Elementary to High School, are presented with the intention of help teachers interested in using new proposals on their pedagogical practice. So they can use this material as a motivating resource for new constructions or just adapt it, change it and/or use it in his classroom routine. Some of the proposed activities were applied with seventh year students from a public school of Rio de Janeiro and the methodology and evaluation of this application are also described on this present work. Therefore it is intended to promote a reflection about new strategies that increase the teaching-learning process of Mathematics in the searching for more autonomy and more meaningful mathematical education.