Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/mmks/mar08/vesnin1.pdf Дата изменения: Tue Jan 8 22:52:24 2008 Дата индексирования: Tue Oct 2 07:05:43 2012 Кодировка: koi8-r Поисковые слова: http astrokuban.info astrokuban

Гамильтоновы графы (А. Веснин, редакция А. Скопенкова)
Задача 1 является классической. Задача 2 (кроме (f )) проста и приводится для того, что бы помочь решателю войти в курс дела. Задачи, отмеченные звездочкой, являются нерешенными. Цикл называется гамильтоновым, если он проходит через каждую вершину ровно по одному разу. Граф называется гамильтоновым, если в нем есть гамильтонов цикл. 1. (a) Нарисуйте гамильтоновы циклы в графах правильных многогранников. (b) Никакой граф, гомеоморфный букве (т.е. графу K3;2 ), не является гамильтоновым. (c) Грани гамильтонова плоского графа можно правильно раскрасить в 4 цвета. (d)* Если из любой вершины графа (без петель и кратных ре бер) с V вершинами выходит не менее V =2 ре бер, то этот граф гамильтонов. Пусть H | граф. Граф X называется H -гамильтоновым, если в X существует подграф, содержащий все вершины графа X и гомеоморфный графу H . 2. (a) Любой гамильтонов граф, отличный от окружности, является -гамильтоновым. (b) Существует -гамильтонов граф, не являющийся гамильтоновым. (c) Любой гамильтонов граф, отличный от K2;n , является K4 -гамильтоновым. (d) Существует K4 -гамильтонов граф, не являющийся -гамильтоновым. (e) Для любых графов G и H существует G-гамильтонов граф, не являющийся H -гамильтоновым. (f )* Опишите "иерархию" графов по их гамильтоновости: когда H -гамильтонов граф является G-гамильтоновым? 2'. (b,d*,e*,f*) То же, что в 2ef, для графов многогранников. Граф называется графом Погорелова, если существует выпуклый 5-связный многогранник P в трехмерном пространстве с данным графом, (1) из каждой вершины которого исходит три ре бра, (2) в границе каждой грани которого не менее пяти ре бер. 3. (Greenbergs) Постройте не гамильтонов граф Погорелова. 4. (a) Негамильтонов граф Погорелова из [Boll, Kokseter, Matematicheskie esse i razvlecheniya, M, Mir, 1986, str. 285] является -гамильтоновым. (b)* (гипотеза) Существует K4 -гамильтонов граф Погорелова, не являющийся -гамильтоновым. Идея доказательства: udalit' trehvalentnuyu vershiny i na ee mesto vkleit' graf Greenbergsa s udalennoi vershinoi. 5.* (a) Опишите "иерархию" графов Погорелова по их гамильтоновости: когда H -гамильтонов гипер болический граф является G-гамильтоновым? (b) (гипотеза) Для любого графа G существует граф Погорелова, не являющийся Gгамильтоновым. Идея доказательства: "vkleivanie" grafa Greenbergsa. (c) Для любых ли графов G и H существует G-гамильтонов граф Погорелова, не являющийся H -гамильтоновым? 6.* Постройте минимальный (по числу граней) граф Погорелова, (a) являющийся K4 -гамильтоновым, но не -гамильтоновым. (b) не являющийся K4 -гамильтоновым. (c) не являющийся H -гамильтоновыми ни для какого подграфа H данного графа G. (Например, G = K4 .)