Nowhere-zero k-flow

Материал из WikiGrapp
Перейти к:навигация, поиск

Nowhere-zero k-flow --- нигде не нулевой k-поток, везде ненулевой k-поток.

A graph admits a nowhere-zero k-flow (k is an integer \geq 2) if its edges can be oriented and labeled by numbers from \{\pm1, \ldots,
\pm(k-1)\} so that for every vertex the sum of the incoming values equals the sum of the outcoming ones. A graph without nowhere-zero k-flow is called k-snark. Note that if a graph is a k-snarks then it is a k'-snark for any integer 2 \leq k' \leq k. Very famous is the 5-flow conjecture of W.T.Tutte which says that there are no bridgeless 5-snarks.