Slučajne šetnje na grafovima

diplomski rad

• Autor: Tin Barišin
• Mentor: Zoran Vondraček (mentor)
• Član povjerenstva: Zoran Vondraček (predsjednik povjerenstva)
• Član povjerenstva: Rudi Mrazović (član povjerenstva)
• Član povjerenstva: Snježana Lubura Strunjak (član povjerenstva)
• Član povjerenstva: Bojan Basrak (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2020-02-10, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Grafovi s težinama se mogu interpretirati na više načina: kao slučajni proces ili električna mreža. Iz raznih interpretacija grafa slijede zgodna svojstva grafova koja nam mogu biti korisna za opisivanje geometrije grafa. Osnovno svojstvo slučajnih šetnji su prolaznost i povratnost. Električne mreže predstavljaju potpuno drukčiji pogled na grafove od slučajnih šetnji te omogućuju interpretaciju prolaznosti i povratnosti preko efektivnog otpora. Varijacijski problemi se prirodno nadovezuju na teoriju električnih mreža i omogućavaju nam bolje razumijevanje geometrije grafa s obzirom na prolaznost i povratnost. Primjerice, kako brisanje i zamjena bridova utječe na efektivni otpor grafa. Koristeći ovaj pristup izvodimo nove tehnike za dokazivanje prolaznosti i povratnosti. Razne vrste grafova možemo povezati konceptom grubih izometrija koje čuvaju određene odnose među grafovima. Glavni cilj ovog diplomskog rada je proučavati svojstva grafova vezanih uz slučajne šetnje: prolaznost i povratnost te dokazati njihovu stabilnost na grube izometrije. Korisnost ovog svojstva je sljedeća: za prolazan ili povratan graf, prolaznost ili povratnost grafa lako slijedi za sve grafove koji su mu grubo izometrični, što znači da gruba izometrija čuva određenu vrstu strukture u grafu koja je važna.

Sažetak (engleski)

Weighted graphs can be easily interpreted in several ways: as a stochastic process or electric network. From these different interpretations many different properties of graphs can be derived and used to further describe its geometry. The fundamental properties of random walks are transience and recurrence. Electric networks represent completely different approach on graph interpretation regarding random walks and enable us to interpret transience and recurrence through the concept of effective resistance. Variational problems are natural upgrade on the theory of electric networks and enable us to further understand connection of graph geometry to transience and recurrence. For example, how cutting and shorting the edges affect effective resistance. Using these approaches we derive new techniques for proving transience and recurrence. Furthermore, different types of graphs can be connected using concept of rough isometries that preserve certain relations between graphs. The main idea of this thesis is to investigate the properties of graphs connected to random walks: transience and recurrence and prove their stability under rough isometries. Usefulness of this property is following: for a graph that is transient or recurrent, transience or recurrence comes easily for all graphs that are roughly isometric to him, meaning that rough isometry preserves some kind of graph structure.

• Ključne riječi: grafovi s težinama; geometrija grafa; slučajne šetnje
• Ključne riječi (engleski): weighted graphs; graph geometry; random walks
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:361420
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2020-07-22 10:24:03