11I il
log(u!) E
Onloga)
:
um log).) is mor increasing
n
As !
,
and ,
we get loglu!) log(n) aloga Kn
=
, 1
i
log(u!) a
Inlogul
:
E
Let k :
=
TET and us, then
, 4,
!
u =
M(( -
1)
. ..
K(k -
1) ...
-
1
( , M(u -
.
1 - -
k ,kk
log(u. )
Klogk
, E log
=
logn
-
Elog 2
,
logu (as mz
, 4)
!)
=>
log
(n - In
logu) (I
e
1
51 ·
etT
(a) Define xe ·
=
I0, eaT
Them a formulation for the MST problem in
minimize Excel
t
s.
, 1 1 (1)
=
-
2 xe> 1 ,
FOSCV (2)
eeS(S)
Xee20 , 13 feze (3)
here ,
(1) guarantes
exactly /VI-1
edges, and
(1) guarantees that for each cut 5(S) of
the graph, where sie
any - mon-empty and
prousset of the verfices V
I
at least one
edge in selected, herce the selected
subset edge connected
of must be a
connected subgraph with
graph . As
any
T
the
IVI-1
edger is a
spanning trea,
formulation is correct . I
1/
(b) "onlyif" : Let e =24 , V3ET and assume >FeP(V) with
spanning tre
C(1) < <(F) .
Then T+e-F is a will <(T+e-f)
=CCT) Eclel-eCf)
-
< CIT) . Contradiction #
↑ O
"if": Consider T with property and MST T*, with ITnT*/ maximal
.
.
- , - -
FePx(n v)
*
*
SUIVETIT and Flies in
#fT +T Fe =
,
,
where
the cut induced T-e
by
)
---
R
-
- ---
-
2
P+
+ (n ,v)
Now an FET Lotherwise T had a
cycle containinge and f) ,
the two
endpoints of f are connected in T
by
a path that containse .
the if"
By property , ICC) <(F) .
On other hand , by the "only
T*
part For T
*, as ie
MS5, cels , (f) .
Now T*+e-f MST with ITn *+e-F)KITNT
(T *)
is
again , .
Contradiction
&
&
· ta
#I
Cal Simple O(u) algorithm
For all n,r EU do (OnY many)
-
Run BFS(n) on (V,T) to find <n ,v3 path P(n , V) O(a + n -
1) =
O(n)
-
On Pr(n , v), find emay(ir) Ola
Lives Ons) to compute all (4 , V)
-
emay
I
14
~ - - ~
-
- -
- -
More Sin
Clever
algorithm
-
Pick
any
wer and run BFS(r) on (VIT) ,
O(n+h) =
Oln)
F(r)
denote
by flv) the "Father" of v,
fol :
=
.
r
- D
&
-
-
2
↑ a
-
~
-
- -
-Define emax(V , V) =
0, <(0) =
0 D F(n)
·
-
-
--
↑
A
&
- U
-
&
-
↑
Then we have FureU (with u+F(r) and v
+Flu)
0 1 2 3 4
#Gr
-
0(1) computation !
ervel
-
Flas, cu Flul3,
,
, clemapafial Fil , Scistance Frohr)
Algorithm :
-FreV :
emax(v, flvl) :
=
<v, Flvl3 Olul
3
FuzV in oder of single
-
Fret in oder of increasing level
-
Onl
# and FlvlFU and FlulFV
Boul
u +V
compute emax (4 , 01 with (+)
(works because when
considering ,
u
v
max En) Ill ,
in
already ! 3p
1 1 Let T*: = Ind cheapest spanning tree so that T *: T-e+e
*
(b) (for some etT and et EIT) .
Let F 2nd deapest t re
spanking
: =
By definition (IT) EC(F) CCT*)
consider all es -eu ETIF .
Then Fe ETIF ;
7
EFIT so that
T-li+ ;
in again a
free .
(Acymentation property (
A Tie MST, <T-eit)L , CCT) CTik clei) Fi
,
=>
(FlCCT) +Zcl-cleil
i
=
-T 3 0
, Ki
actually this is
,
21T +(C) -Clee)
not
immediately -
clear (See
cost f re obtained From
of sime spanning
T
by
next
page) changing es
For ên
but we accept
by T*.
34
*
it if used (CT ) definition E
(c) Algorithm :
-Compute emay(4 , V) FureV (a) Din
using
v3 EEIT
Bocms
-
For all e =
24,
compute <(T+e-emaSU I V( ⑤(1)
The cheapest of all these is the second cheapest MST #T,
because of (b), and because Te-emar(n , V, ecElT,
the cheapest spanning tre possible
is
precisely when
adding
e to T land
eliminating one other
edge on the cycle) 14
# part of the reise (I -
had overlooked
(1) (CFCECCT) +Zkl-ceil) i
this complication)
=
-T 30 Vi
this true
why is ?
Recall T
MST, F second chapest MST (IT)
:
= =
Say TIF =
Les ...,
en3 and
FIT = s n3
..
(note, these must have sae cordinality (
Then we can find a
-
matching of alle,
to alle ,
so that
Fi, T-eite , is
again a
spanning free
From the the claim (1) follows
Exauph :
e
Treiten true
an
edge if in a
spanzing
pe ↑
The proof of the fact (existence of thin
perfect
matching) is, unfortunately ,
a non-trivial exereise
!
in its own
I
(From 2020
14) cas
Branchings die not
-
a matroid .
Consider G u
=
&
->
And the two
branchings) !
bases
#
& -
* - - ⑨ & &
Bz Bs1
Then IB11<1By / but #etBr so
that BevLe3 E ,
so (M3) is
violated .
(And (M4), tor) T
1p
(b)
Stable sets in graphs ar
not a matroid .
Consider
U W W
G =
&.
and stable (indip .) Sets I =
<v3 and I =
Su, w3
,
then
Il1 <171, but Fee11 that IUSe3E*
1p
so
14)
(C) A-sided
matchings a re
a matroid ,
#of : Consider two indep . sets of edges En Ez ,
With IErxlE21 .
Not that (EssA1 =
/E1)
and / Eze Al =
/ Ez) ,
so that Ez is
insident with mer vertine From A
than E ..
Example (For illustration
only /:
T-B
------
Er
V e
=> Ez
-
&
·
T -
&
/Ein Al =
2, (EzeAl =
1A) =
3
Choose VEA so that VeEz #* but
Un E1 = 8. .
Let etEr be the
with
edge incident .
v
ThenetEzIEr 1
and EquaeBEE, as unE, =D .
=(M3) is
fulfilled H
3 p
