Элементы теории алгоритмов - 217 стр.

UptoLike

ВУЗ: 

ЯрГУ | Ярославль

Составители: 

Рубрика: 

§4 NP
G =(V,E) e V \V
1
V G =(V,E)
v u e
V \ V
1
v, u ∈ V
1
NP
G =(V,E)
k
→
G =(
→
V,
→
E) G k
→
G =(
→
V,
→
E)
V = {v
1
,...,v
n
} v
i
v
j
e
ij
e
ij
= e
ji
k a
1
a
k
→
V
→
G
a
i
a
i
e
ij
G v
i
v
j
→
G
[v
i
,e
ij
, 0], [v
i
,e
ij
, 1], [v
j
,e
ij
, 0], [v
j
,e
ij
, 1]
[v
i
,e
ij
, 0] → [v
i
,e
ij
, 1], [v
j
,e
ij
, 0] → [v
j
,e
ij
, 1],
[v
i
,e
ij
, 0] → [v
j
,e
ij
, 0], [v
j
,e
ij
, 0] → [v
i
,e
ij
, 0],
[v
i
,e
ij
, 1] → [v
j
,e
ij
, 1], [v
j
,e
ij
, 1] → [v
i
,e
ij
, 1].
G n
v
i
G
→
G
a
t
t =1,...,k
[v
i
,e
is
, 0] e
is
v
i
a
t
t =1,...,k
[v
i
,e
is
, 1] e
is
v
i
[v
i
,e
it
, 1] [v
i
,e
is
, 0] e
is
e
it
v
i
→
E
→
G

Страницы