In this master thesis we will show how random walks are used in Wilson's algorithm to generate spanning trees of graphs, and how they can be used to calculate the number of spanning trees in a graph. We will also explore the connection between electrical networks and random walks, and how this connection can be exploited to prove Pólya's theorem (normally proved with probability and combinatorics) using electrical arguments.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:uu-524684 |
| Date | January 2024 |
| Creators | Jonsson, Erik |
| Publisher | Uppsala universitet, Sannolikhetsteori och kombinatorik |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | U.U.D.M. project report ; 2024:3 |
Page generated in 0.013 seconds