130
правок
Изменения
→Язык гамильтоновых графов
=== Язык гамильтоновых графов ===
{{main|Гамильтоновы графыNP-полнота задач о гамильтоновом цикле и пути в графах}}Рассмотрим следующий язык: <tex>L \mathrm{HAM} = \{ G \mid G</tex> — содержит гамильтонов графцикл<tex>\}</tex>. Он разрешается следующей программой, работающей за полиномиальное относительно числа вершин время:
<tex>r(G)\colon</tex>
<tex>n = |V(G)|</tex>
