Побудовано нескінченну послідовність регулярних зв"язних графів, елементи якої є майже екстремальними графами, бо відношення кількості вершин графа до кількості його ребер є константою. Встановлено, що у кожному графі побудованої послідовності графів існують послідовності гамільтонових циклів, довжина яких є експонентою від кількості вершин графу, та для яких побудова наступного елементу по поточному елементу здійснюється за допомогою лише локальних обчислень, що мають константну складність.
Ключові слова: регулярні графи, гамільтонові цикли, складність.
It is proposed some infinite sequence of regular connected graphs, elements of which are nearly extremal ones, since ratio of the order of a graph to its size is some constant. It is established that for any graph of proposed sequence of graphs there exists some sequence of Hamiltonian cycles, such that its length is some exponent of the order of a graph and transformation of any element of this sequence into the next one can be realized only via local computing with constant complexity.
Key Words: regular graphs, Hamiltonian cycles, complexity.
