Igra policajev in roparjev na grafih

Bastašić, Tina

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Igra policajev in roparjev na grafih
Authors:	ID Bastašić, Tina (Author) ID Dravec, Tanja (Mentor) More about this mentor...
Files:	MAG_Bastasic_Tina_2019.pdf (318,60 KB) MD5: 627FFE8487F2D6A8325E87B3BEA11873 PID: 20.500.12556/dkum/131741a0-026f-4c0d-bf2c-a080067ab3db
Language:	Slovenian
Work type:	Master's thesis/paper
Typology:	2.09 - Master's Thesis
Organization:	FNM - Faculty of Natural Sciences and Mathematics
Abstract:	V magistrskem delu bomo predstavli igro policajev in roparjev na grafih, kjer se policaji in ropar premikajo po vozliščih grafa. Cilj policajev je, da eden izmed njih uspe priti na enako vozlišče kot ropar. Grafom, na katerih ima v igri z enim policajem policaj zmagovalno strategijo, pravimo policaj-zmaga grafi. Najmanjše število policajev, ki je potrebnih, da imajo zmagovalno strategijo na grafu G, imenujemo varnostno število grafa G. Poleg igre policajev in roparjev bomo predstavili še druge različice te igre. Varnostno število grafa bomo izračunali za nekatere preproste družine grafov in predstavili spodnje in zgornje meje varnostnega števila grafa. Nato bomo pokazali, kako varnostno število retraktov grafa vpliva na varnostno število originalnega grafa. Kot bomo videli, retrakti grafov igrajo pomembno vlogo pri karakterizaciji policaj-zmaga grafov. Dokažemo, da so policaj-zmaga grafi natanko odstranljivi grafi. Predstavimo tudi policaj-zmaga urejenost in policaj-zmaga strategijo. Na koncu še dokažemo, da so tudi mostovni grafi policaj-zmaga grafi.
Keywords:	igra policajev in roparjev, varnostno število grafa, policaj-zmaga grafi, odstranljivi grafi, mostovni grafi
Place of publishing:	Maribor
Publisher:	[T. Bastašić]
Year of publishing:	2019
PID:	20.500.12556/DKUM-74902
UDC:	519.17(043.2)
COBISS.SI-ID:	24865288
NUK URN:	URN:SI:UM:DK:ANTDMAOV
Publication date in DKUM:	05.11.2019
Views:	1593
Downloads:	130
Metadata:
Categories:	FNM
:	Copy citation

Average score:	(0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Licences

License:	CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Link:	http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:	The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.
Licensing start date:	11.09.2019

Secondary language

Language:	English
Title:	The game of cops and robbers on graphs
Abstract:	In this master's thesis we will present the Game of Cops and Robbers on graphs, where cops and robber moves on vertices of a graph. The goal of the cops is, that one of them is on the same vertex as the robber. The graphs on which one cop has a winning strategy are called cop-win graphs. The minimum number of cops, that have a winning strategy on a graph G, is called the cop number of G. In addition to the Game of Cops and Robbers, we will present other variations of this game. We will calculate the cop number for some simple graph families and present some lower and upper bounds for the cop number. Then we will show how the cop number of a retract of a graph affects on the cop number of the original graph. As we will see, retracts of a graph play an important role in the characterization of the cop-win graphs. We prove that cop-win graphs are exactly dismantlable graphs. Then we present the cop-win ordering and the cop-win strategy. At the end, we show that bridged graphs are cop-win graphs.
Keywords:	Game of Cops and Robbers, cop-win number, cop-win graphs, dismantlable graphs, bridged graphs

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back