244
правки
Изменения
Нет описания правки
# Для $n \ge 2$, найдите формулу для количества остовных деревьев $K_n$, содержащих ребро $1 -- 2$,
# Обобщите матричную теорему Кирхгофа для следующей задачи: дан ориентированный граф и вершина $r$, нужно найти количество корневых деревьев с корнем в $r$.
# Сколько раз необходимо оторвать карандаш от бумаги, чтобы нарисовать граф $K_n$, не проводя никакое ребро два раза, в зависимости от $n$?
# Сколько раз необходимо оторвать карандаш от бумаги, чтобы нарисовать граф $K_{n,m}$, не проводя никакое ребро два раза, в зависимости от $n$ и $m$?
# Докажите, что связный граф эйлеров тогда и только тогда, когда каждый его блок (компонента вершинной двусвязности) эйлеров
# Сбалансированной ориентацией неориентированного графа называют такую ориентацию всех его ребер, чтобы в каждую вершину входило столько же ребер, сколько выходит. Какие графы имеют сбалансированную ориентацию?
# Граф называется произвольно вычерчиваемым из вершины $u$, если следующая процедура всегда приводит к эйлеровому циклу: начиная с вершины $u$, переходим каждый раз по любому исходящему из текущей вершины ребру, по которому ранее не проходили. Докажите, что эйлеров граф является произвольно вычерчиваемым из $u$, если любой его простой цикл содержит $u$.
# Докажите, что если граф $G$ является произвольно вычерчиваемым из $u$, то $u$ имеет максимальную степень в $G$.
# Докажите, что если граф $G$ является произвольно вычерчиваемым из $u$, то либо $u$ - единственная точка сочленения в $G$, либо в $G$ нет точек сочленения.
# Реберным графом для графа $G$ называется граф $G_E$, множество вершин которого совпадает с множеством ребер исходного графа, два ребра $e$ и $f$ соединены ребром в реберном графе, если у них есть общая инцидентная вершина. В каком случае ребра реберного графа можно разбить на полные подграфы таким образом, чтобы каждая вершина принадлежала в точности двум из подграфов?
# Выразите число треугольников в реберном графе $G_E$ через число треугольников графа $G$ и набор его степеней.
# В каком случае связный граф $G$ имеет регулярный реберный граф?
# Постройте связный граф $G$ с $n \ge 4$ вершинами, для которого граф $G_E$ не эйлеров, а граф $(G_E)_E$ эйлеров.
# Докажите, что если $G$ содержит $n \ge 5$ вершин, то если $((G_E)_E)_E$ эйлеров, то $(G_E)_E$ эйлеров.
# Сколько существует неизоморфных связных неориентированных эйлеровых графов с 4 вершинами?
# Сколько существует неизоморфных связных неориентированных эйлеровых графов с 5 вершинами?
# Сколько существует неизоморфных связных неориентированных эйлеровых графов с 6 вершинами?
# Сколько эйлеровых циклов у $K_n$?
# Ребра связного неориентированного графа раскрашены в 2 цвета: красный и синий, причем каждой вершине инцидентно равное число ребер красного и синего цвета. Докажите, что между любой парой вершин существует путь (не обязательно простой), в котором любые два соседних ребра имеют разные цвета.
# На некоторых клетках таблицы $n\times n$ стоит фишка, причем в каждой горизонтали и в каждой вертикали стоит хотя бы две фишки. Докажите или опровергните, что можно убрать часть фишек, чтобы в каждой вертикали и в каждой горизонтали стояло ровно по две фишки.
# Дан неориентированный регулярный граф, степень каждой вершины которого равна $k^2$. Звездой называется набор из $k$ ребер, инцидентных одной и той же вершине. Докажите или опровергните, что можно разбить все ребра этого графа на звезды.
