18. Гамильтоновы графы
К списку вопросов
Цикл, проходящий через каждую вершину графа, называется Гамильтоновой линией; а граф, содержащий такую линию - Гамильтоновым графом.
Граф, который содержит простую цепь, проходящую через каждую вершину, называется полу-Гамильтоновым.
Допустимое и достаточное условие гамильтонованности графов неизвестны.
Если в простом графе с n (nі3) вершинами степень каждой вершины і n/2, то этот граф является Гамильтоновым.
Необходимые и достаточные условия Гамильтоновости графа не известны.
Если в простом графе с n (nі3) вершинами степень каждой вершины і n/2, то этот граф является Гамильтоновым.
Теорема Дирака. Если в простом графе с числом вершин n (n>=3) ?(v)>=n/2 для любых n, то граф является гамельтоновым
К списку вопросов
