数学代写|图论作业代写Graph Theory代考|$k$-Flows for small $k$

Doug I. Jones

Lorem ipsum dolor sit amet, cons the all tetur adiscing elit

couryes™为您提供可以保分的包课服务

couryes-lab™ 为您的留学生涯保驾护航 在代写图论Graph Theory方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写图论Graph Theory代写方面经验极为丰富，各种代写图论Graph Theory相关的作业也就用不着说。

数学代写|图论作业代写Graph Theory代考|$k$-Flows for small $k$

Trivially, a graph has a 1-flow (the empty set) if and only if it has no edges. In this section we collect a few simple examples of sufficient conditions under which a graph has a 2-, 3- or 4-flow. More examples can be found in the exercises.

Proposition 6.4.1. A graph has a 2-flow if and only if all its degrees are even.

Proof. By Theorem 6.3.3, a graph $G=(V, E)$ has a 2-flow if and only if it has a $\mathbb{Z}_2$-flow, i.e. if and only if the constant $\operatorname{map} \vec{E} \rightarrow \mathbb{Z}_2$ with value $\overline{1}$ satisfies (F2). This is the case if and only if all degrees are even.

For the remainder of this chapter, let us call a graph even if all its vertex degrees are even.

Proposition 6.4.2. A cubic graph has a 3-flow if and only if it is bipartite.

Proof. Let $G=(V, E)$ be a cubic graph. Let us assume first that $G$ has a 3 -flow, and hence also a $\mathbb{Z}3$-flow $f$. We show that any cycle $C=x_0 \ldots x{\ell} x_0$ in $G$ has even length (cf. Proposition 1.6.1). Consider two consecutive edges on $C$, say $e_{i-1}:=x_{i-1} x_i$ and $e_i:=x_i x_{i+1}$. If $f$ assigned the same value to these edges in the direction of the forward orientation of $C$, i.e. if $f\left(e_{i-1}, x_{i-1}, x_i\right)=f\left(e_i, x_i, x_{i+1}\right)$, then $f$ could not satisfy (F2) at $x_i$ for any non-zero value of the third edge at $x_i$. Therefore $f$ assigns the values $\overline{1}$ and $\overline{2}$ to the edges of $C$ alternately, and in particular $C$ has even length.

Conversely, let $G$ be bipartite, with vertex bipartition ${X, Y}$. Since $G$ is cubic, the map $\vec{E} \rightarrow \mathbb{Z}3$ defined by $f(e, x, y):=\overline{1}$ and $f(e, y, x):=\overline{2}$ for all edges $e=x y$ with $x \in X$ and $y \in Y$ is a $\mathbb{Z}{3^{-}}$ flow on $G$. By Theorem 6.3.3, then, $G$ has a 3-flow.

数学代写|图论作业代写Graph Theory代考|Flow-colouring duality

In this section we shall see a surprising connection between flows and colouring: every $k$-flow on a plane multigraph gives rise to a $k$-vertexcolouring of its dual, and vice versa. In this way, the investigation of $k$-flows appears as a natural generalization of the familiar map colouring problems in the plane.

Let $G=(V, E)$ and $G^=\left(V^, E^\right)$ be dual plane multigraphs. For simplicity, let us assume that $G$ and $G^$ have neither bridges nor loops and are non-trivial. For edge sets $F \subseteq E$, let us write
$$F^:=\left{e^ \in E^* \mid e \in F\right} .$$
Conversely, if a subset of $E^$ is given, we shall usually write it immediately in the form $F^$, and thus let $F \subseteq E$ be defined implicitly via the bijection $e \mapsto e^*$.

Suppose we are given a circulation $g$ on $G^$ : how can we employ the duality between $G$ and $G^$ to derive from $g$ some information about $G$ ? The most general property of all circulations is Proposition 6.1.1, which says that $g(X, \bar{X})=0$ for all $X \subseteq V^$. By Proposition 4.6.1, the minimal cuts $E^(X, \bar{X})$ in $G^$ correspond precisely to the cycles in $G$. Thus if we take the composition $f$ of the maps $e \mapsto e^$ and $g$, and sum its values over the edges of a cycle in $G$, then this sum should again be zero.
Of course, there is still a technical hitch: since $g$ takes its arguments not in $E^$ but in $\overrightarrow{E^}$, we cannot simply define $f$ as above: we first have to refine the bijection $e \mapsto e^$ into one from $\vec{E}$ to $\overrightarrow{E^}$, i.e. assign to every $\vec{e} \in \vec{E}$ canonically one of the two directions of $e^*$. This will be the purpose of our first lemma. After that, we shall show that $f$ does indeed sum to zero along any cycle in $G$.

If $C=v_0 \ldots v_{\ell-1} v_0$ is a cycle with edges $e_i=v_i v_{i+1}$ (and $v_{\ell}:=v_0$ ), we shall call
$$\vec{C}:=\left{\left(e_i, v_i, v_{i+1}\right) \mid i<\ell\right}$$
a cycle with orientation. Note that this definition of $\vec{C}$ depends on the vertex enumeration chosen to denote $C$ : every cycle has two orientations. Conversely, of course, $C$ can be reconstructed from the set $\vec{C}$. In practice, we shall therefore speak about $C$ freely even when, formally, only $\vec{C}$ has been defined.

图论代考

数学代写|图论作业代写Graph Theory代考|Flow-colouring duality

$$F^:=\left{e^ \in E^* \mid e \in F\right} .$$

$$\vec{C}:=\left{\left(e_i, v_i, v_{i+1}\right) \mid i<\ell\right}$$

Days
Hours
Minutes
Seconds

15% OFF

On All Tickets

Don’t hesitate and buy tickets today – All tickets are at a special price until 15.08.2021. Hope to see you there :)