Strøm i nettverk og transportmatriser med bestemte strukturer

Abstract

I denne oppgaven utforsker vi sammenhengen mellom strøm i nettverk og transportmatriser der matriseelementene oppfyller gitte begrensninger. Videre bruker vi denne sammenhengen til å avgjøre om det eksisterer, og i så fall bestemme, nedre triangulære, øvre triangulære og tridiagonale transportmatriser, samt transportmatriser der elementene enten er 0 eller 1. Deretter karakteriserer vi når disse typene matriser eksisterer uten å løse ett nettverk strøm problem. I forkant av den utforskende delen der dette diskuteres, innledes oppgaven med en teoridel. Her redegjør vi for relevant teori om strøm i nettverk, og beskriver ulike nettverk strøm problemer. Videre presenteres noen anvendelser av de introduserte nettverk strøm problemene. Teoridelen avsluttes med to kapitler der vi introduserer teori som karakteriserer når det eksisterer trappematriser og (0,1)-matriser med gitte linjesummer. I den utforskende delen av oppgaven kobles egne resultater til denne teorien.

In this thesis, we aim to explore the connection between network flows and transportation matrices where the elements satisfy given restrictions. We use this relationship to determine whether it exists, and if so, we determine lower triangular, upper triangular and tridiagonal transportation matrices, as well as transportation matrices where the elements either are 0 or 1. Furthermore, we characterize when these types of matrices exist, without solving a network flow problem. Ahead of the exploratory part discussing this, the thesis begins with a theory part. Here we explain relevant network flow theory, and describe some network flow problems. Furthermore, we present some applications of the introduced network flow problems. In the last two chapters of the theory part, we introduce theory that characterizes when staircase matrices and (0,1)-matrices with given line sums exist. In the exploratory part of the thesis, our results are linked to this theory.