Изменения

# Обозначим как Граф называется произвольно вычерчиваемым из вершины $u$, если следующая процедура всегда приводит к эйлеровому циклу: начиная с вершины $\lambda(G)u$ минимальное число ребер, которое нужно удалить в графепереходим каждый раз по любому исходящему из текущей вершины ребру, чтобы он потерял связностьпо которому ранее не проходили. Докажите, что эйлеров граф является произвольно вычерчиваемым из $\kappa(G)u$ - минимальное число вершин, которое нужно удалить в графе, чтобы он потерял связность (для полного графа полагаем если любой его простой цикл содержит $\kappa(G)=n-1u$). # Докажите, что если граф $\kappa(G) \le \lambda($ является произвольно вычерчиваемым из $u$, то $u$ имеет максимальную степень в $G) \le \delta(G)$.# Докажите. , что для любых если граф $1 \le \kappa(G) \le \lambda(G) \le \delta($ является произвольно вычерчиваемым из $u$, то либо $u$ - единственная точка сочленения в $G)$ существует граф , либо в $G$ с такими параметраминет точек сочленения.# Порожденным (также индуцированным) подграфом называется подграф, полученный удалением некоторого множества вершин и всех инцидентных ребер. Докажитеили опровергните, что не существует графов с если $G$\kappaсодержит порожденный тета-подграф (Gдве вершины, соединенные тремя путями произвольной длины) = 3, то $ и G$7$ ребрамине гамильтонов.# Пусть Обозначим как $G^3$ - полный двудольный граф, за исключением в котором две вершины соединены, если они соединены в $K_{2,2}G$путем длины не более 3. Докажите , что если $\lambda(G)=\delta(G)$связен, почем единственный способ удалить то $\lambda(G)^3$ ребер, чтобы граф потерял связность - удалить все ребра, инцидентные одной из вершингамильтонов.# Графы Граф называется произвольно гамильтоновым, если следующая процедура всегда приводит к гамильтонову циклу: начиная с произвольной вершины $G_1u$, содержащий $n_1$ вершин и $m_1$ реберпереходим каждый раз по любому исходящему из текущей вершины ребру, и $G_2$другой конец которого мы ранее не посещали, содержащий $n_2либо обратно в вершину $ вершин и u$m_2$ ребер, гомеоморфныесли непосещенных соседей нет. Докажите, что $n_1+m_2 = n_2+m_1$Опишите все произвольно гамильтоновы графы.# Рассмотрим параметрически заданную замкнутую кривую Будем называть последовательность $(d_1, \phi(tldots, d_n)$, будем говорить, что она имеет самопересечениестепенной последовательностью, если есть точка на кривойсуществует граф с такими степенями вершин. Приведите критерий, которая порождается двумя различными значениями параметра $t_1$ и $t_2$проверяемый за полиномиальное время, причем в окрестности этой точки фрагменты кривой в окрестности параметра $t_2$ лежат по разную сторону от кривой в окрестности параметра $t_1$что заданная последовательность является степенной.# Теорема ""Антихватала"". Докажите, что планарный эйлеров если для степенной последовательности не выполнено условие теоремы Хватала, то найдется граф содержит эйлеров циклсо степенной последовательностью, не имеющий самопересечений.# Приведите пример вершинно двухсвязного планарного графамажорирующей данную, который не является гамильтоновымсодержащий гамильтонова цикла.# Докажите, что планарный четырехсвязный граф гамильтоновесли сумма степеней любых двух несмежных вершин графа $G$ не меньше $n+1$, то любые две различные вершины $G$ можно соединить гамильтоновым путем.# Пусть Реберным графом для графа $G$ - планарный называется граф$G_E$, в котором каждый треугольник ограничивает область, не содержащую множество вершин которого совпадает с множеством реберисходного графа, причем добавление любого два ребра нарушает это свойство$e$ и $f$ соединены ребром в реберном графе, если у них есть общая инцидентная вершина. Докажитеили опровергните, что если $G$ гамильтоновявляется эйлеровым, то реберный граф является гамильтоновым.# Докажитеили опровергните, что любой трехсвязный планарный если $G_E$ является гамильтоновым, то граф имеет остов, у которого наибольшая степень равна 3$G$ является эйлеровым.# ДокажитеВ каком случае ребра реберного графа можно разбить на полные подграфы таким образом, что все колеса самодвойственны.чтобы каждая вершина принадлежала в точности двум из подграфов?# Докажите, что Выразите число треугольников в планарном реберном графе $O(n)G_E$ через число треугольниковграфа $G$ и набор его степеней.# ДокажитеВ каком случае связный граф $G$ имеет регулярный реберный граф?# Постройте связный граф $G$ с $n \ge 4$ вершинами, что можно ориентировать ребра планарного графа такдля которого граф $G_E$ не эйлеров, что а граф $deg^-(vG_E) \le 5$ для всех вершин $v_E$эйлеров.# Докажите, что можно ориентировать ребра планарного графа такесли $G$ содержит $n \ge 5$ вершин, что то если $deg^-(v(G_E)_E) \le 3_E$ для всех вершин эйлеров, то $v(G_E)_E$эйлеров.# Уложите четырехмерный куб на поверхности тора# Уложите $K_7$ на поверхности тораПостройте минимальный по числу ребер граф, в реберном графе которого нет гамильтонова цикла.# Докажите, что $K_8$ нельзя уложить на поверхности тора# Найдите максимальное $kG_E$гамильтонов тогда и только тогда, что когда граф $K_kG$ можно уложить на сфере с двумя ручками.# Докажитесодержит циклический реберно простой путь, что содержащий для любого каждого ребра графа $m$ существует $kG$хотя бы одну вершину, такое что граф с $K_k$ нельзя уложить на сфере с $m$ ручкамиему инцидентную.