Search

Pakirno kromatično število $chi_{pi}(G)$ grafa $G$ je najmanjši $k$, za katerega lahko poiščemo $k$-pakirno barvanje grafa, torej najmanjši $k$, za katerega obstaja taka funkcija $pi: (G) to [k]$, da iz $pi(u) = pi(v)$ sledi, da je razdalja med $u$ in $v$ večja od $pi(u)$. Za graf $G$ in $p ge 1$ definiramo $p$-korono grafa $G$ kot graf, ki ga iz grafa $G$ dobimo tako, da na vsako njegovo vozlišče pripnemo $p$ dodatnih listov (torej vozlišč stopnje ena). Določanje pakirnega kromatičnega števila grafa je v splošnem težek problem, kar v delu nakažemo s tem, da dokažemo, da je 4-pakirno barvanje NP-poln problem. Nato dokažemo izrek o pakirnem kromatičnem številu na poteh in ciklih, zatem pa se omejimo na pakirno kromatično število $p$-koron poti in ciklov. The packing chromatic number $chi_{pi}(G)$ of a graph $G$ is the smallest integer $k$ for which a packing k-coloring of graph $G$ can be found, which is the smallest $k$ for which such a function $pi: (G) to [k]$ exists, that from $pi(u) = pi(v)$ follows that the distance between u and v is greater than $pi(u)$. For a graph $G$ and $p ge 1$, a $p$-coronae of the graph $G$ is defined as the graph we obtain graph $G$ by adding p additional leaves (vertices of degree 1) to each vertex on the graph. Determining the packing chromatic number of a graph is a complex problem. In this paper we show this by presenting a proof that 4-packing coloring is an NP-complete problem. Then we prove a theorem on the packing chromatic number of paths and cycles, and afterwards focus on the packing chromatic number of $p$-coronae of paths and cycles.

Namen diplomske naloge je pregledati in oceniti različna orodja za pregledovanje in testiranje spletnih aplikacij v programskem jeziku Python. Orodja Twill, Webunit in FunkLoad so namenjena testiranju končnih spletnih aplikacij. Glavna prednost orodja Twill je enostavna uporaba, slabost pa zastarelost in majhna razširjenost. Orodje Webunit je tudi enostavno, vendar ni prilagojeno za uporabo v Windows okolju. Orodje FunkLoad je nadgradnja orodja Webunit s snemalnikom za pripravo testov. Orodja PyChecker, Pylint in Pyflakes so namenjena za pregledovanje pravilnosti kode. PyChecker najde vse napake v kodi, vendar pri tem izvede kodo. Pyflakes je nadgraditev orodja PyChecker, ki kode ne izvede, vendar ne odkrije vseh napak. Pylint poleg napak odkriva tudi lepopisne napake v kodi in je ne izvede. Na koncu je predstavljen nabor orodij iz različnih področij, ki bi jih bilo najbolje uporabljati pri svojih projektih. The objective of my thesis is to review and evaluate different tools for inspecting and testing Python web applications. Tools Twill, Webunit and FunkLoad are intended for testing web applications. Twill is easy to use, but it is outdated and unpopular. Tool Webunit is also easy to use, but it is not adapted for usage in Windows. Tool FunkLoad is upgraded from Webunit with a recorder for making tests. Tools PyChecker, Pylint in Pyflakes are intended for checking source code. PyChecker detects all errors in code, but needs to execute the code. Pyflakes is upgraded from PyChecker and does not need to execute the code, but does not detect all errors. Pylint, beside errors, also detects poorly formed lines inside code. At the end is presented a set of tools from different fields, which are the most suitable for usage in our projects.