Algorithms for telecommunications: class #3

Solving exercises on flow (ex. 2 & 3 from pages 415-416)

2.a. The value is 18. We look for the minimum cut. We can verify it's the minimum if we find a flow of the same value (cue in explanation of the auxiliary graph).
2.b. The maximum flow is 21 and the cut is { s, a }

Auxiliary graph

We take the same set of nodes and edges. But we put the difference between capacity and flow in the original graph as capacity in the new one. We also add an edge going in the reverse direction with the capacity equivalent to the flow in the original edge. We don't add edges that would have 0 capacity.

Then, we look for a path from s to t. If there's one, the flow was not maximum. We find the minimum capacity of the path, and will add that number to the flow. For doing that, we increase the flow of the edges in the original graph that are going forward in the auxiliary graph, and adjust the auxiliary graph.

For edges that go backwards in the auxiliary graph, we reduce the flow in the original graph, and again update the auxiliary graph.

Now, we restart the process until there's no path from s to t.

At that point we have the maximum flow, and the maximum cut is the set of nodes reachable from s in the auxiliary graph.

Note: if we choose the wrong path when growing the flow, we have the risk of looping. If we choose the shortest path, we are sure we will finish in at most $n^2$ steps.

Graph colouring

Applications: channel assignment, scheduling, VLSI, latin squares.

A colouring is a mapping $c: V(G) \rightarrow S$ where S is the set of colours. A k-colouring is $|S| = k, S = \{ 1, 2 \dots k \}$

A colouring is proper if $\forall uv \in E(G), c(u) \neq c(v)$. If the graph has loops, there is no proper colouring possible. In general we only consider simple graphs (no loops, no duplicate edges).

The chromatic number is defined as: $X(G) = min \{k, G\ \textrm{has a proper k-colouring} \}$. It exists because we can always use n colours.

Proposition 1.1: if H is a subgraph of G, then $X(H) \leq X(G)$.

Proposition 1.2: G is a graph with connected components $C_1 \dots C_p$. $X(G) = max \{ X(C_1) \dots X(C_p) \}$

If G has an edge, then $X(G) \geq 2 \Rightarrow X(G) = 1$ iff it has no edges.

Theorem 1.3: A graph is bipartite iff it has no odd cycles (as subgraphs).

$\Rightarrow$. A bipartite graph has always chromatic number 2. But an odd cycle has chromatic number 3.
$\Leftarrow$. We have G with no odd cycles. W.l.o.g. we may assume G is connected. Let x be a vertes. $\forall v \in G$, we colour v with $dist(x, v) mod 2$.

Let's show that the colouring is proper. Suppose not:

(1)
\begin{align} \exists u, v / c(u) = c(v). \end{align}
(2)
\begin{align} |dist(x, u) - dist(x, v)| \leq 1 \end{align}
(3)
\begin{align} \therefore dist(x, u) = dist(x, v) = d \end{align}

And we have an odd cycle.

Note: It is NP-complete to decide if the chromatic number of a graph is $k \geq 3$.

Lower bounds on the chromatic number

Clique: set of vertices S such that G<S> is a complete graph.

Clique number: $\omega(G)$ is the maximum size of a clique in G

  • $H\ \textrm{subgraph of }\ G \Rightarrow X(G) \geq X(H)$
  • $X(K_n) = n$, where $K_n$ is a complete graph of n nodes.
  • $X(G) \geq \omega(G)$

We would like to know if $\exists f / X(G) \leq f(\omega(G))$. The answer is no. Mycielsky construction (see http://mathworld.wolfram.com/MycielskiGraph.html)

(4)
\begin{align} \exists\ \textrm{triangle-free graph}\ M_k [\omega \leq 2] / \omega(M_k) = 2, X(M_k) = k \end{align}

Independent set, or stable set is a set of pairwise non-adjacent vertices.

Proposition: $X(G) \geq \frac {|V(G)|} {\alpha(G)}$, where $\alpha(G)$ is the stable number, the maximum size of a stable set in G.

Let c be a proper X(G)-colouring, $S_i$ is the set of vertices coloured i. $\sum|S_i| = |V(G)|$

$S_i$ is a stable set, so $|S_i| \leq \alpha(G)$.

(5)
\begin{eqnarray} \sum |S_i| = |V(G)| & \leq & \sum_{i=1}^{X(G)} \alpha(G) \\ & \leq & X(G) \alpha(G) \\ \frac {|V(G)|}{\alpha(G)} & \leq & X(G) \end{eqnarray}

Upper bounds on the chromatic number

Greedy colouring algorithm

We set an ordering of the vertices: $v_1 < v_2 < \dots < v_n$.

For each i, colour the vertex $v_i$ with the smallest integer that is not assigned to a lower-indexed neighbour. In this case, $X(G) \leq \Delta(G) + 1$, where $\Delta(G)$ is the maximum degree of the graph.

We want to find an ordering such that $max \{ \#\ \textrm{of lower indexes neighbours} \}$ is minimum. That is called the degeneracy of G, noted $\delta^*(G) = max \{ \delta(H), H\ \textrm{subraph of G} \}$

(6)
\begin{align} X(G) \leq \delta^*(G) + 1 \leq \Delta(G) + 1 \end{align}

For complete graphs, and for odd cycles, $X(G) = \Delta(G) + 1$

Proposition: If G is not regular (all vertices have the same degree), and is connected, then $\delta^*(G) < \Delta(G) \Rightarrow X(G) \leq \Delta(G)$.

We prove it by taking a v such that $d(v) \< \Delta(G)$ and build a spanning tree from it that defines an ordering of the vertices. $\forall i < n, \exists j > i, v_iv_j \in E \Rightarrow \delta^*(G) \leq \Delta(G) - 1$

Brooks theorem

G connected graph. Then $X(G) \leq \Delta(G)$ unless G is a complete graph or G is an odd cycle.

Excercises

Excercise 1. Find the chromatic number of the following graphs.
We first find boundaries. Then we can calculate the degeneracy: take the edge with minimum degree, assign n to it, remove it with its edges and start again assigning n - 1 until we're done.

Now we use a greedy colouring starting with the smallest number. That will give us a better boundary.

For the first graph, we can find a 4 colouring, which is also a lower bound (it has a 4-clique).

For the second graph, with the degeneracy we find a 6-colouring. We can find a 5-colouring by colouring first the inner cycle with three colours and the outer for which we only need two more colours.

We can find the stable number, we take one vertex, and we only can take on of the nodes in the connected graph at the other corner. So $\alpha(G) = 2$. Then

(7)
\begin{align} X \geq \frac{|V(G)|}{\alpha(G)} = \frac{10}2 = 5 \end{align}

So X(G) = 5.

Unclear, need to ask the teachers, since most is obviously derived works.