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

UptoLike

ВУЗ: 

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

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

Рубрика: 

NP NP
G k
→
G =(
→
V,
→
E)
v
1
v
k
G
i i =1,...,k e
i1
e
it
i
v
i
a
1
→ [v
1
,e
11
, 0], [v
1
,e
11
, 0] → [v
1
,e
11
, 1],
[v
1
,e
11
, 1] → [v
1
,e
12
, 0], [v
1
,e
12
, 0] → [v
1
,e
12
, 1],
...
[v
1
,e
1t
1
, 0] → [v
1
,e
1t
1
, 1], [v
1
,e
1t
1
, 1] → a
2
,
a
2
→ [v
2
,e
21
, 0], [v
2
,e
21
, 0] → [v
2
,e
21
, 1],
[v
2
,e
21
, 1] → [v
2
,e
22
, 0], [v
2
,e
22
, 0] → [v
2
,e
22
, 1],
...
[v
2
,e
2t
2
, 0] → [v
2
,e
2t
2
, 1], [v
2
,e
2t
2
, 1] → a
3
,
...
a
k
→ [v
k
,e
k1
, 0], [v
k
,e
k1
, 0] → [v
k
,e
k1
, 1],
[v
k
,e
k1
, 1] → [v
k
,e
k2
, 0], [v
k
,e
k2
, 0] → [v
k
,e
k2
, 1],
...
[v
k
,e
kt
k
, 0] → [v
k
,e
kt
k
, 1], [v
k
,e
kt
k
, 1] → a
1
.
→
G
v
j
j>k
v
j
j>k e
→
G [v
j
,e,0] [v
j
,e,1]
v
1
v
k
G
i 1 ≤ i ≤ k v
i
e
[v
i
,e,0] → [v
i
,e,1]
[v
i
,e,0] → [v
j
,e,0], [v
j
,e,0] → [v
j
,e,1], [v
j
,e,1] → [v
1
,e,1].
→
G
→
G
k
{a
1
,a
2
,...,a
k
}.

Страницы