| Popis: |
V diplomskem delu obravnavamo nikjer-ničelne pretoke na grafih. Le-ti se izkažejo kot zelo uporabni, tako znotraj same teorije grafov, kot tudi v praksi. Pred samo vpeljavo pojma nikjer-ničelnega pretoka najprej ponovimo osnovne definicije teorije grafov in teorije grup, ki so potrebni za razumevanje diplomskega dela. Nato vpeljemo pojem pretoka in nikjer-ničelnega pretoka, ki ju ilustriramo na primerih. Obravnavamo predvsem pretoke z vrednostmi v abelskih grupah. Navedemo pomemben Tuttov izrek, ki povezuje nikjer-ničelne k-pretoke z nikjer-ničelnimi Z_k-pretoki, ga dokažemo in predstavimo na primeru. Nazadnje podamo in dokažemo še nekaj rezultatov o obstoju nikjer-ničelnih k-pretokov za majhne vrednosti k. Omenimo tudi znane Tuttove domneve o takšnih pretokih. In this BSc thesis we investigate nowhere-zero flows on graphs. It turns out that this concept is very useful in graph theory itself, as well as in practice. Before introducing the concept of nowhere-zero flows we make a short review, along with some examples, of some notions in graph theory and in group theory, which are necessary for the understanding of this BSc thesis. We then define the concept of flows and nowhere-zero flows, and illustrate them with examples. We focus on flows with values in abelian groups. We present an important theorem of W. T. Tutte, which gives a correspondence between nowhere-zero k-flows with nowhere-zero Z_k-flows. We prove the theorem and illustrate it with an example. Lastly, we present and prove some results about the existence of nowhere-zero k-flows for small values of k. We mention also two well-known Tutte's conjectures on these flows. |
