SGT

Network:

graph LR;
	a-->|"(5)"|b;
	a-->|"(4)"|q;
	b-->|"(3)"|c;
	b-->|"(5)"|p;
	c-->|"(3)"|d;
	p-->|"(1)"|d;
	p-->|"(4)"|q;
	q-->|"(2)"|c;

1

a,b	a,q	b,c	b,p	c,d	p,d	p,q	q,c
$3/5=0.6$	$1$	$5/3=1.\overline{6}$	$1$	$2/3=0.\overline{6}$	$1$	$1$	$1/2=0.5$

The maximum edge congestion is $1.\overline{6}$.

2

Initial value:

	a,b	a,q	b,c	b,p	c,d	p,d	p,q	q,c
commodity 1	0	0	2	1	2	1	0	0
commodity 2	3	4	0	3	0	0	3	0
commodity 3	0	0	3	1	0	0	1	1

Re-route $3$

New values after re-routing $3$ of commodity from $(b,c)$ to $⟨b,p,q,c⟩$:

	a,b	a,q	b,c	b,p	c,d	p,d	p,q	q,c
commodity 1	0	0	2	1	2	1	0	0
commodity 2	3	4	0	3	0	0	3	0
commodity 3	0	0	0	4	0	0	4	4
New flow congestion:

a,b	a,q	b,c	b,p	c,d	p,d	p,q	q,c
$3/5=0.\overline{6}$	$1$	$2/3=0.\overline{6}$	$8/5=1.6$	$2/3=0.\overline{6}$	$1$	$7/4=1.75$	$4/2=2$

The maximum edge congestion is $1.75$.

Re-route $2$

New values after re-routing $2$ of commodity from $(b,c)$ to $⟨b,p,q,c⟩$:

	a,b	a,q	b,c	b,p	c,d	p,d	p,q	q,c
commodity 1	0	0	2	1	2	1	0	0
commodity 2	3	4	0	3	0	0	3	0
commodity 3	0	0	1	3	0	0	3	3
New flow congestion:

a,b	a,q	b,c	b,p	c,d	p,d	p,q	q,c
$3/5=0.\overline{6}$	$1$	$1$	$7/5=1.4$	$2/3=0.\overline{6}$	$1$	$6/4=1.5$	$3/2=1.5$

The maximum edge congestion is $1.5$ (which is $\le 1.\overline{6}$).

Maximally reducing maximum edge congestion

We want to minimise:

$$\max ⟨0.\overline{6},1,\frac{2+(3-x)}{3},\frac{5+x}{5},0.\overline{6},1,\frac{4+x}{4},\frac{1+x}{2}⟩$$

That is, minimise:

$$\max ⟨\frac{2+(3-x)}{3},\frac{5+x}{5},\frac{4+x}{4},\frac{1+x}{2}⟩$$

That is, minimise:

$$\max ⟨\frac{2+(3-x)}{3},\frac{5+x}{3},\frac{4+x}{4},\frac{1+x}{2}⟩$$

Solve graphically:

Hence redirect $1.143$ of the flow, which produces maximal congestion of $1.286$.

3

Edges from $\{a,b\}$ to $\{c,d,p,q\}$:

• $(a,q)=4$
• $(b,c)=3$
• $(b,p)=5$

???