Random walks on graphs
| dc.contributor.advisor | Wagner, Stephan | en_ZA |
| dc.contributor.author | Oosthuizen, Joubert | en_ZA |
| dc.contributor.other | Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. | en |
| dc.date.accessioned | 2014-04-16T17:28:23Z | |
| dc.date.available | 2014-04-16T17:28:23Z | |
| dc.date.issued | 2014-04 | |
| dc.description | Thesis (MSc)--Stellenbosch University, 2014. | en_ZA |
| dc.description.abstract | ENGLISH ABSTRACT: We study random walks on nite graphs. The reader is introduced to general Markov chains before we move on more specifically to random walks on graphs. A random walk on a graph is just a Markov chain that is time-reversible. The main parameters we study are the hitting time, commute time and cover time. We nd novel formulas for the cover time of the subdivided star graph and broom graph before looking at the trees with extremal cover times. Lastly we look at a connection between random walks on graphs and electrical networks, where the hitting time between two vertices of a graph is expressed in terms of a weighted sum of e ective resistances. This expression in turn proves useful when we study the cover cost, a parameter related to the cover time. | en |
| dc.description.abstract | AFRIKAANSE OPSOMMING: Ons bestudeer toevallige wandelings op eindige gra eke in hierdie tesis. Eers word algemene Markov kettings beskou voordat ons meer spesi ek aanbeweeg na toevallige wandelings op gra eke. 'n Toevallige wandeling is net 'n Markov ketting wat tyd herleibaar is. Die hoof paramaters wat ons bestudeer is die treftyd, pendeltyd en dektyd. Ons vind oorspronklike formules vir die dektyd van die verdeelde stergra ek sowel as die besemgra ek en kyk daarna na die twee bome met uiterste dektye. Laastens kyk ons na 'n verband tussen toevallige wandelings op gra eke en elektriese netwerke, waar die treftyd tussen twee punte op 'n gra ek uitgedruk word in terme van 'n geweegde som van e ektiewe weerstande. Hierdie uitdrukking is op sy beurt weer nuttig wanneer ons die dekkoste bestudeer, waar die dekkoste 'n paramater is wat verwant is aan die dektyd. | en_ZA |
| dc.format.extent | 72 p. | |
| dc.identifier.uri | http://hdl.handle.net/10019.1/86244 | |
| dc.language.iso | en_ZA | |
| dc.publisher | Stellenbosch : Stellenbosch University | |
| dc.rights.holder | Stellenbosch University | |
| dc.subject | Cover time | en |
| dc.subject | Dissertations -- Mathematics | en_ZA |
| dc.subject | Theses -- Mathematics | en_ZA |
| dc.subject | Theses -- Mathematical sciences | en_ZA |
| dc.subject | Random walks (Mathematics) | en_ZA |
| dc.subject | Markov processes | en_ZA |
| dc.subject | Graph theory | en_ZA |
| dc.subject | UCTD | en_ZA |
| dc.title | Random walks on graphs | en |
| dc.type | Thesis |