| Abstrakt: | A nowhere-zero complex r-flow is an oriented bridgeless graph with flow assignment $g:E \rightarrow \mathbb{C}$ and all values assigned to edges have a Euclidean norm in the interval $[1,r-1]$. We define the flow number as an infimum of the real numbers r such that the graph still has a nowhere-zero complex r-flow. The infimum is also minimum. The subset $H_n = \{(a+b\sqrt{2},c+d\sqrt{2})|a,b,c,d \in \mathbb{Z} \wedge |a|,|b|,|c|,|d| \leq n \}$. In this thesis we use subset $H_n$ as an assignment instead of complex numbers because we need an finite set to be able to calculate with it. We define $H_n$-flow an bridgeless graph with flow assignment $h:E\rightarrow H_n$ and all values assigned to edges have a Euclidean norm in the interval $[1,r-1]$. $H_n$-flow number is defined as infimum of real numbers r such that the graph still has a $H_n$-flow. The aim of this thesis is to use $H_n$-flow number as an approximation of an upper bound. With growing n the $H_n$-flow number will approach the complex flow number. We used algorithms, SAT and mathematical optimization for solving the problem. We were able using SAT to calculate the $H_n$-flow number for chosen graph with good performance for some chosen graph. Also we proved that $H_1$-flow number for all wheels is $1 + \sqrt{2}$. And last we were able to calculate the exact complex flow number of Petersen graph to accuracy of 5 decimal digits with a solver.
|
|---|