Orientador: Claudio Leonardo Lucchesi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-07T04:48:23Z (GMT). No. of bitstreams: 1
Miranda_AlbertoAlexandreAssis_M.pdf: 924668 bytes, checksum: 5707312a9e0513f890e4affc3858fbb6 (MD5)
Previous issue date: 2006 / Resumo: Um grafo G que tem emparelhamento perfeito é o Pfaffiano se existe uma orientação D das arestas de G, tal que todo circuito conforme de G tem orientação ímpar em D. Um subgrafo H de G é conforme se G- V (H) tem emparelhamento perfeito. Uma orientação de um circuito par é ímpar se numa dada direção de percurso do circuito o número de arestas que concorda com a direção é ímpar. Calcular o número de emparelhamentos perfeitos de um grafo, no caso geral, _e NP-difícil [11, pág. 307]. No entanto, para grafos Pfaffiano, seu cálculo torna-se polinomial [11, pág. 319]. A caracterização de grafos bipartidos Pfaffiano, feita por Little, tem quase trinta anos [9]. No entanto, somente nos últimos anos apareceram algoritmos polinomiais para reconhecimento de tais grafos, por McCuaig [13] e independentemente por Robertson, Seymour e Thomas [14]. A solução para este problema resolve também uma série de problemas, muitos deles clássicos, em teoria dos grafos, economia e química, como descrito no artigo de McCuaig [13, págs. 16 a 35]. Nesta dissertação, apresentamos uma prova de corretude do algoritmo distinta das duas provas anteriormente conhecidas / Abstract: A graph G that contains a perfect matching is Pfaffiano if there is an orientation D of the edges of G, such that every conformal circuit of G is oddly oriented in D. A subgraph H of G is conformal if G - V (H) has a perfect matching. A circuit with an even number of edges is oddly oriented if the number of edges whose orientation in D agrees with any sense of traversal of the circuit is odd. Counting the number of perfect matchings of a graph is known to be NP-hard [11, page 307]. However, when restricted to Pfaffiano graphs, this problem is solvable in polynomial time [11, page 319]. The characterisation of Pfaffiano bipartite graphs, achieved by Charles Little, is almost thirty years old [9]. However, only recently, polynomial time algorithms for determining whether a bipartite graph is Pfaffiano were discovered, by McCuaig [13] and independently by Robertson, Seymour and Thomas [14]. This problem's solution solves a lot of problems, some of them are quite famous, in graph theory, economy and chemistry, as described in McCuaig's article [13, pages 16 to 35]. On this dissertation, we present a new proof of the correctness of this algorithm distinct from the two previously known proofs / Mestrado / Mestre em Ciência da Computação
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/276295 |
| Date | 08 July 2006 |
| Creators | Miranda, Alberto Alexandre Assis |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Lucchesi, Cláudio Leonardo, 1945-, Carvalho, Marcelo Henriques de, Lee, Orlando |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Computação, Programa de Pós-Graduação em Ciência da Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | 136p. : il., application/octet-stream |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0017 seconds