Algorithms for telecommunications: class #2

Review of the excercise on the satellites network:
satellites.png

Proof it is not a valid network: mark failures in the outputs 14 to 17, and in one of outputs 8 or 9, and the failure is not recoverable.

satellites2.png

Some results from the satellites research

$\textbb N (n, k)$ is the minimum number of switches for a k-valid network with n inputs.

(1)
\begin{eqnarray} \textbb N (n, 2) & = & n \\ \textbb N (n, 4) & = & n + \sqrt{\frac n 4}\\ \textbb N (n, 6) & = & n + \frac n 4 + \sqrt{\frac n 8} + \textbb O (1) \\ \textbb N (n, 6) & \get & n + \frac n 4 + \sqrt{\frac n 8 + \frac 3 2} \\ \textbb N (n, 6) & \let & n + \frac n 4 + \sqrt{\frac n 8 + \frac{23}{16}} + 3 +\frac 1 4 \\ \textbb N (n, 8) & = & n + \frac n 3 + \frac 2 3 \sqrt{\frac n 3} + \textbb O (n^{\frac 1 4}) \\ \end{eqnarray}

Greedy algorithms: Minimum spanning tree

Some definitions:

  • Let G be a graph, n is the number of nodes, w(x) defines the weight of each edge.
  • A tree T is a connected graph without cycles. The number of edges in a tree $|E| = n + 1$
  • $w(T) = \sum_{e \in T} w(e)$

Kruskal's algorithm

Wikipedia description (IMHO, that one is nicer)

  1. Sort the edges according to ther weight in non decreasing order: $e_1 \leq e_2 \leq \dots \leq e_m$. Step $m \log m$
  2. $T \gets \emptyset, i \gets 0, j \gets 1$
  3. While $i \leq n - 2$:
    • If $T \cup \{ e_j \}$, do $j \gets j +1$
    • Else, $T \gets T \cup \{ e_j \}, i \gets i + 1$

Prim's algorithm

Wikipedia description

We have the graph G with $V = \{ V_i \}$ vertices.

  1. $T \gets \emptyset, s \gets \{ v_1 \}$ (any vertex)
  2. While $S \neq V$:
    • Choose an edge e of minimum weght connecting S and V - S.
    • Let v be the end vertex of e in V - S.
    • $T \gets T \cup \{e\}, S \gets S \cup \{v\}$

Important lemma

(4.17 from page 145)

Assume that all edge costs are distinct. Let S be any subset of nodes that is neither empty nor equal to all of V, and let the edge e = (v, w) be the minimum-cost edge with one end in S and the other in V - S. Then every minimum spanning tree contains the edge e.

Network flow

It is a weighted digraph G = V, E with a defined capacity on each edge c(e).
There is two specific verices: s (source) and t (sink).

The flow of an edge e is f(e) with the following properties:

(2)
\begin{align} f(e) \leq c(e) \end{align}
(3)
\begin{align} \forall v \neq s, t, \sum_{e\ \textrm{entering}\ v} f(e) = \sum_{e\ \textrm{exiting}\ v} f(e) \qquad \textrm{(conservation law)} \end{align}

The flow of the network is what is leaving (entering) the source (sink).

Cut

Let S be a subset of the nodes of a network, such as $s \in S, t \in V - S$. A cut is the set of edges from S to V - S. The capacity of the cut is $c(cut) = \sum_{e \in cut} c(e)$

Theorem: the maximum flow is equal to the minimum cut.

Menger's theorem

Proof

For an undirected, unweighted graph:

The maximum number of arc-disjoint paths from s to t is equal to the minimum number of arcs you have to delete to disconnect s from t.

(4)
\begin{align} \exists k\ \textrm{arc-disjoint paths}\ \Rightarrow \ \textrm{I need to delete at least k arcs to disconnect them} \end{align}

Menger's Algorithm (got completely lost here, need to see the book :))

  1. $s \in S$
  2. If $x \in S$ and if $\exists (x, y) \notin \Pi$, then add y to S.
  3. If $x \in S$ and if $\exists (y, x) \in \Pi$, then add y to S.

To do: Excercise 2 & 3 p. 415.

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