Розкладність графів. Квазігамільтонові Графи, Детальна інформація

Нехай Gr(V,E) - зліченний звязний граф. Бієкцію f: ((V назвемо квазігамільтоновим променем (скорочено qh-променем), якщо d(f(i), f(i+1))(2 для всіх i((. Граф, що допускає таку бієкцію назвемо qhr-графом.

Проблема 6. Охарактеризувати qhr-дерева.

Наступна задача показує, що клас qhr-дерев значно вужчий за клас qr-дерев.

Задача 3. Нехай T(V,E) - зліченне дерево, x(V,

)|>1.

не більше одного нескінченного дерева.

Розглянемо деякі алгоритмічні задачі і проблеми, пов'язані з результатами останніх двох параграфів.

Задача 4. Спираючись на доведення теореми 4.1, вказати алгоритм побудови повного квазіциклу в довільному скінченному звязному графі. Оцінити його складність.

Задача 5. Вказати алгоритми, які по заданому скінченному дереву визначають, чи є це дерево qhc-графом, qhp-графом? Оцінити їх складності.

Відомо, що задача перевірки, чи є заданий скінченний звязний граф гамільтоновим, являється NP-повною [6].

Проблема 7. Чи є NP-повною задача тестування скінченного звязного графа на існування в ньому qh-циклу? qh-шляху?