Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Random walks on graphs
Thesis (MSc)--Stellenbosch University, 2014.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2014
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613856420855808 |
|---|---|
| access_status_str | Open Access |
| author | Oosthuizen, Joubert |
| author2 | Wagner, Stephan |
| author_browse | Oosthuizen, Joubert Wagner, Stephan |
| author_facet | Wagner, Stephan Oosthuizen, Joubert |
| author_sort | Oosthuizen, Joubert |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (MSc)--Stellenbosch University, 2014. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/86244 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:42:46.825Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2014 |
| publishDateRange | 2014 |
| publishDateSort | 2014 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/86244 Random walks on graphs Oosthuizen, Joubert Wagner, Stephan Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Cover time Dissertations -- Mathematics Theses -- Mathematics Theses -- Mathematical sciences Random walks (Mathematics) Markov processes Graph theory UCTD Thesis (MSc)--Stellenbosch University, 2014. 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. 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. 2014-04-16T17:28:23Z 2014-04-16T17:28:23Z 2014-04 Thesis http://hdl.handle.net/10019.1/86244 en_ZA Stellenbosch University 72 p. application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Cover time Dissertations -- Mathematics Theses -- Mathematics Theses -- Mathematical sciences Random walks (Mathematics) Markov processes Graph theory UCTD Oosthuizen, Joubert Random walks on graphs |
| title | Random walks on graphs |
| title_full | Random walks on graphs |
| title_fullStr | Random walks on graphs |
| title_full_unstemmed | Random walks on graphs |
| title_short | Random walks on graphs |
| title_sort | random walks on graphs |
| topic | Cover time Dissertations -- Mathematics Theses -- Mathematics Theses -- Mathematical sciences Random walks (Mathematics) Markov processes Graph theory UCTD |
| url | http://hdl.handle.net/10019.1/86244 |
| work_keys_str_mv | AT oosthuizenjoubert randomwalksongraphs |