244
правки
Изменения
Нет описания правки
# Для $n \ge 2$, найдите формулу для количества остовных деревьев $K_n$, содержащих ребро $1-2$,
# Обобщите матричную теорему Кирхгофа для следующей задачи: дан ориентированный граф и вершина $r$, нужно найти количество корневых деревьев с корнем в $r$.
# Обозначим как $\lambda(G)$ минимальное число ребер, которое нужно удалить в графе, чтобы он потерял связность, $\kappa(G)$ - минимальное число вершин, которое нужно удалить в графе, чтобы он потерял связность (для полного графа полагаем $\kappa(G)=n-1$). Докажите, что $\kappa(G) \le \lambda(G) \le \delta(G)$.
# Докажите. что для любых $1 \le \kappa(G) \le \lambda(G) \le \delta(G)$ существует граф $G$ с такими параметрами.
# Докажите, что не существует графов с $\kappa(G) = 3$ и $7$ ребрами.
# Пусть $G$ - полный двудольный граф, за исключением $K_{2,2}$. Докажите $\lambda(G)=\delta(G)$, почем единственный способ удалить $\lambda(G)$ ребер, чтобы граф потерял связность - удалить все ребра, инцидентные одной из вершин.
# Графы $G_1$, содержащий $n_1$ вершин и $m_1$ ребер, и $G_2$, содержащий $n_2$ вершин и $m_2$ ребер, гомеоморфны. Докажите, что $n_1+m_2 = n_2+m_1$.
# Рассмотрим параметрически заданную замкнутую кривую $\phi(t)$, будем говорить, что она имеет самопересечение, если есть точка на кривой, которая порождается двумя различными значениями параметра $t_1$ и $t_2$, причем в окрестности этой точки фрагменты кривой в окрестности параметра $t_2$ лежат по разную сторону от кривой в окрестности параметра $t_1$. Докажите, что планарный эйлеров граф содержит эйлеров цикл, не имеющий самопересечений.
# Приведите пример вершинно двухсвязного планарного графа, который не является гамильтоновым.
# Докажите, что планарный четырехсвязный граф гамильтонов.
# Пусть $G$ - планарный граф, в котором каждый треугольник ограничивает область, не содержащую ребер, причем добавление любого ребра нарушает это свойство. Докажите, что $G$ гамильтонов.
# Докажите, что любой трехсвязный планарный граф имеет остов, у которого наибольшая степень равна 3.
# Докажите, что все колеса самодвойственны.
# Докажите, что в планарном графе $O(n)$ треугольников.
# Докажите, что можно ориентировать ребра планарного графа так, что $deg^-(v) \le 5$ для всех вершин $v$.
# Докажите, что можно ориентировать ребра планарного графа так, что $deg^-(v) \le 3$ для всех вершин $v$.
# Уложите четырехмерный куб на поверхности тора
# Уложите $K_7$ на поверхности тора
# Докажите, что $K_8$ нельзя уложить на поверхности тора
# Найдите максимальное $k$, что граф $K_k$ можно уложить на сфере с двумя ручками.
# Докажите, что для любого $m$ существует $k$, такое что граф с $K_k$ нельзя уложить на сфере с $m$ ручками.
