Review of the excercise on the satellites network:
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.
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)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)
- 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$
- $T \gets \emptyset, i \gets 0, j \gets 1$
- 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
We have the graph G with $V = \{ V_i \}$ vertices.
- $T \gets \emptyset, s \gets \{ v_1 \}$ (any vertex)
- 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)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
For an undirected, unweighted graph:
(4)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.
Menger's Algorithm (got completely lost here, need to see the book :))
- $s \in S$
- If $x \in S$ and if $\exists (x, y) \notin \Pi$, then add y to S.
- If $x \in S$ and if $\exists (y, x) \in \Pi$, then add y to S.
To do: Excercise 2 & 3 p. 415.