Primjena teorije grafova u proučavanju mreža javnog prijevoza

master's thesis

• Author: Marija Mihaljević
• Mentor: Marko Erceg (mentor)
• Committee member: Marko Erceg (predsjednik povjerenstva)
• Committee member: Boris Širola (član povjerenstva)
• Committee member: Boris Muha (član povjerenstva)
• Committee member: Marcela Hanzer (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2019-11-27, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu iznesene su osnovne definicije i rezultati vezani za mreže. Glavni dio teorije o mrežama je Teorem o maksimalnom toku i minimalnom rezu te Algoritam metode označavanja. Algoritmom metode označavanja konstruiramo niz tokova dane mreže rastuće vrijednosti, a izneseni teorijski rezultati osiguravaju da je posljednji tok u nizu maksimalan tok dane mreže. Teoremom o maksimalnom toku i minimalnom rezu dana je veza vrijednosti maksimalnog toka i kapaciteta minimalnog reza mreže. Preciznije, dokazano je da su te dvije veličine jednake. Zahvaljujući tom rezultatu, nakon primjene algoritma metode označavanja i određivanja maksimalnog toka mreže, lako se odredi i kapacitet minimalnog reza mreže. U drugom dijelu rada iznose se rezultati analize mreža javnog prijevoza Firence i Atike. Na primjeru tih mreža opisane su dvije vrste simulacije ciljanog napada na mreže javnog prijevoza: simulacija u statičnom i dinamičnom kontekstu. Takve simulacije omogućuju proučavanje ranjivosti mreže te, eventualno, pronalazak njezinih slabih točaka.

Abstract (english)

In this paper we presented the main definitions and results related to networks. The most important results related to network theory, in this paper, are the max-flow min-cut theorem and the labelling method algorithm. By the labelling method algorithm, the sequence of flows of increasing value is constructed and network theory ensures that algorithm terminates with the max-flow of a network. In the max-flow min-cut theorem, we can see relation between max-flow value and min-cut capacity of a network. To be more specific, it is proven that those two values are equal. This results ensure that if we apply the labelling method algorithm and find max-flow of a network, we can determine capacity of a min-cut. In the second part of this paper, the results of public transportation network analyses are shown. The analysis are based on two public transportation networks (PTNs), PTN of Florence and PTN of Attika region. In those analyses, two approaches in simulations of trageted attacks on PTNs are described: simulation in static context and simulation in dynamic context. Those simulations give us possibility to study vulnerability of PTNs and, eventually, determination of its weaknesses.

• Keywords: mreže; teorem o maksimalnom toku i minimalnom rezu; algoritam metode označavanja; analiza mreže javnog prijevoza
• Keywords (english): networks; max-flow min-cut theorem; labelling method algorithm; analysis of public transportation network
• Language: croatian
• URN:NBN: urn:nbn:hr:217:867242
• Study programme: Title: Mathematics Education; specializations in: Mathematics Education; Course: Mathematics Education; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra edukacije matematike (magistar/magistra edukacije matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2020-07-10 11:25:25