Please use this identifier to cite or link to this item: http://hdl.handle.net/2445/53496
Title: Estudi de la planaritat i número de talls d’un graf
Author: Màdico Ferrer, Adrià
Director: Soria de Diego, F. Javier
Keywords: Teoria de grafs
Tesis
Algorismes
Graph theory
Theses
Algorithms
Issue Date: 19-Jun-2013
Abstract: In this project, we will work on two types of graphs, the complete and the complete bipartite graph. They are two important structures in graph theory and are defined in 1.2.1. We show the proofs for each case for which the number corresponding to the minimum cuts of edges is already known. What is more, we also explain some general lower bounds achieved for the minimum. All the proofs can be found in several original papers and our work fixes all and is a useful guide for having a general reference point. The fact that this is not a recent problem can be noticed because the first one who wrote about this was Zarankiewicz in 1954. He used only mathematical arguments like other mathematicians that in the sixties and seventies developed their own methods. In 1993, Woodall started using computational algorithms [17] and finally, Farahani in 2013 published the last paper explained in this work [2]. The last part of the project is about some algorithms we have done that generated our initial interest for this topic. Although they do not give unknown results, they are expected to open a new path that will help us to reach new objectives. To conclude, we finally see that this is an open problem and it is difficult to determinate how the improvements will come. The lasts proofs that use the computational power and have achieved better bounds fall easily with bigger graphs because this is an NP-complete problem. In my opinion, better results will arrive when we manage to reduce the number of cases limiting the huge magnitude of the problem, otherwise, there should be extremely good improvements in the actual algorithms to offset the complexity.
Note: Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any:2013, Director: F. Javier Soria de Diego
URI: http://hdl.handle.net/2445/53496
Appears in Collections:Treballs Finals de Grau (TFG) - Matemàtiques

Files in This Item:
File Description SizeFormat 
madico_ferrer_TFG.pdfMemòria1.59 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons