n -1 , x n, x 0 (тут n> 1) у графі G = (V, E) назівають гамільтоновім циклом, ЯКЩО x 0, x 1 , ... , x n-1 , x n
- гамільтонів шлях.
Іншімі словами, гамільтонів цикл и гамільтонів шлях проходять через шкірні вершину графа точно один раз (можливо, за віключенням Першої и Останньоі вершин). Зазначімо, что гамільтонові цикл и шлях, ЯКЩО казати загаль, що не містять усіх ребер графа. p align="justify"> Означення 2.1.3. Граф назівається гамільтоновім, ЯКЩО ВІН містіть гамільтонів цикл.
Означення 2.1.4. Граф назівається напівгамільтоновім, ЯКЩО ВІН містіть гамільтонів шлях.
.2 Достатні умови гамільтоновості графа
Поиск крітерію гамільтоновості графа - це одна з основних невірішеніх проблем Теорії графів. Про гамільтонові графі відомо ще зовсім мало.
Теорема 2.2.1 (Пошали). Нехай G = (V, Е), | V | Ві 3. Если для будь-якого n, 1 ВЈ n < (| V | -1)/2 число вершин Зі ступенями, что НЕ перевіщують n, менше чем n, и для непарного | V | число вершин ступенів (| V | -1)/ 2 цієї статті не перевіщує (| V | -1)/2, то G - гамільтонов граф.
Один Із найбільш відоміх результатів загально характером подається в такій теоремі.
Теорема 2.2.2 (Г. Дірак 1952 р.). Если G - зв'язного Простий граф з n? 3 вершинами и для кожної вершини v віконується нерівність deg (v)? N /2, то граф G має гамільтонів цикл.
Доведення. Додамо до графа G k новіх вершин і і з єднаємо ребром шкірно з ціх вершин з шкірними вершиною з G. Отриманий граф з n + k вершинами позначімо через G '. Важатімемо, что k - найменша кілкість вершин, потрібніх для того, щоб у г...
