Please use this identifier to cite or link to this item: http://hdl.handle.net/2445/176011
Title: Arbres de cost mı́nim i jocs cooperatius
Author: Camacho Martı́n, Laura
Director/Tutor: Jarque i Ribera, Xavier
Martínez de Albéniz, F. Javier
Keywords: Arbres (Teoria de grafs)
Treballs de fi de grau
Jocs cooperatius (Matemàtica)
Xarxes elèctriques
Trees (Graph theory)
Bachelor's thesis
Cooperative games (Mathematics)
Electric networks
Issue Date: Jun-2020
Abstract: [en] In this project we study minimun cost spanning tree problems and how to associate them with a cooperative game of transferable utility. Some real economic situations such as the construction of an electricity network for the supply of energy to an entire village from a common power station can be modelled by these problems. This case was studied by Dutta and Kar (2004). On the one hand, we define two algorithms capable of obtaining a minimum cost spanning tree of a connected graph, namely Prim’s (1957) and Kruskal’s (1956). On the other hand, we explain a series of cost allocation rules, which are interpreted under the prism of cooperative games. A series of properties are detailed to see which of these properties determine them. We also study the irreducible form introduced by Bird (1976) associated with a minimum cost spanning tree problem. We see how to associate one to each problem and analyze the equivalence between rules in this irreducible form.
Note: Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2020, Director: Xavier Jarque i Ribera i F. Javier Martínez de Albéniz
URI: http://hdl.handle.net/2445/176011
Appears in Collections:Treballs Finals de Grau (TFG) - Matemàtiques

Files in This Item:
File Description SizeFormat 
176011.pdfMemòria460.7 kBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons