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.

# 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\}$

- Choose an edge

## Important lemma

(4.17 from page 145)

Assume that all edge costs are distinct. Let

Sbe any subset of nodes that is neither empty nor equal to all ofV, and let the edgee = (v, w)be the minimum-cost edge with one end inSand the other inV - S. Then every minimum spanning tree contains the edgee.

# 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:

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

stotis equal to the minimum number of arcs you have to delete to disconnectsfromt.

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.