130
правок
Изменения
→Проблема раскраски вершин графа в k цветов: оформил псевдокод в техе
Разрешается следующей недетерминированной программой за полиномиальное относительно числа вершин время:
<tex>r(G)\colon</tex>
'''for''' <tex>uv</tex> '''in''' <tex>E(G)</tex>
'''if''' <tex>c[u] </tex> == <tex>c[v]</tex>
'''return''' ''false''
'''return''' ''true''
=== Проблема нахождения гамильтонова цикла ===
<tex>r(G)\colon</tex>
