Список заданий по ДМ 2к 2018 осень — различия между версиями
| Строка 34: | Строка 34: | ||
# Опишите все деревья с диаметром 2. | # Опишите все деревья с диаметром 2. | ||
# Опишите все деревья с диаметром 3. | # Опишите все деревья с диаметром 3. | ||
| + | # Опишите дерево с кодом Прюфера $(i, i,\ldots , i)$. | ||
| + | # Опишите деревья, в коде Прюфера которых нет одинаковых чисел. | ||
| + | # Докажите, что число помеченных неподвешенных деревьев есть $n^{n-2}$, используя теорему Кирхгофа. | ||
# Сколько остовных деревьев у полного двудольного графа $K_{n,m}$? | # Сколько остовных деревьев у полного двудольного графа $K_{n,m}$? | ||
| − | # Докажите или опровергните, что если в | + | # Приведите пример графа с двумя непересекающимися остовными деревьями. |
| + | # Какое максимальное количество попарно непересекающихся остовных деревьев может быть в графе с $n$ вершинами? | ||
| + | # Пусть связный граф $G$ имеет диаметр $d$. Докажите или опровергните, что у $G$ есть остовное дерево с диаметром $d$. | ||
| + | # Рассмотрим множество остовных деревьев связного графа $G$. Построим граф $S_G$, вершинами которого являются остовные деревья $G$, а две вершины $T_1$ и $T_2$ соединены ребром, если дерево $T_2$ можно получить из $T_1$ удалением одного ребра и добавлением другого. Докажите, что $S_G$ является связным. | ||
| + | # Докажите, что две вершины $T_1$ и $T_2$ в $S_G$ соединены ребром тогда и только тогда, когда их объединение содержит ровно один простой цикл. | ||
| + | # Пусть связный граф $G$ содержит $n$ вершин, докажите, что диаметр $S_G$ не превышает $n - 1$. | ||
| + | # Приведите пример связного графа $G$, содержащего $n$ вершин, для которого граф $S_G$ имеет диаметр $n - 1$. | ||
| + | # Докажите, что для любого $1 \le k \le n - 1$ существует связный граф $G$, содержащий $n$ вершин, такой что диаметр $S_G$ равен $n - k$. | ||
# Обозначим как $\lambda(G)$ минимальное число ребер, которое нужно удалить в графе, чтобы он потерял связность, $\kappa(G)$ - минимальное число вершин, которое нужно удалить в графе, чтобы он потерял связность (для полного графа полагаем $\kappa(G)=n-1$). Докажите, что $\kappa(G) \le \lambda(G) \le \delta(G)$. | # Обозначим как $\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$ с такими параметрами. | # Докажите. что для любых $1 \le \kappa(G) \le \lambda(G) \le \delta(G)$ существует граф $G$ с такими параметрами. | ||
# Докажите, что не существует графов с $\kappa(G) = 3$ и 7 ребрами. | # Докажите, что не существует графов с $\kappa(G) = 3$ и 7 ребрами. | ||
# Пусть $G$ - полный двудольный граф, за исключением $K_{2,2}$. Докажите $\lambda(G)=\delta(G)$, почем единственный способ удалить $\lambda(G)$ ребер, чтобы граф потерял связность - удалить все ребра, инцидентные одной из вершин. | # Пусть $G$ - полный двудольный граф, за исключением $K_{2,2}$. Докажите $\lambda(G)=\delta(G)$, почем единственный способ удалить $\lambda(G)$ ребер, чтобы граф потерял связность - удалить все ребра, инцидентные одной из вершин. | ||
| − | |||
| − | |||
| − | |||
| − | |||
Версия 12:23, 29 сентября 2018
- Постройте граф с $n$ вершинами и $m$ ребрами. Здесь и далее "постройте граф с $n$ вершинами, ..." означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.
- Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$.
- Обозначим как $N[u]$ множество, содержащее вершину $u$, а также соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N[u]$ совпадают для всех вершин $u$.
- Постройте граф с $n$ вершинами, где каждая вершина имеет степень $d$.
- Докажите, что любой граф, содержащий хотя бы две вершины, имеет две вершины одинаковой степени.
- Обозначим как $\delta(G)$ минимальную степень вершины в графе, как $\Delta(G)$ - максимальную степень вершины в графе. Постройте граф с $n$ вершинами, в котором $\delta(G) + \Delta(G) > n$.
- Постройте двудольный граф с $n$ вершинами, в котором $\delta(G) + \Delta(G) > n$.
- Пусть для двудольного графа выполнено условие: для любой пары не соединенных ребром вершин есть вершина, связанная с обеими этими вершинами. Как устроен такой граф?
- Докажите, что для любого графа $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ имеют общий делитель, отличный от 1, тогда и только тогда, когда в графе $G$ есть ребро $uv$.
- Граф называется кубическим, если степень всех вершин равна 3. Три вершины графа образуют треугольник, если они попарно соединены ребром. Постройте кубический граф с $n$ вершинами, не содержащий треугольников.
- Граф называется самодополнительным, если он изоморфен своему дополнению. Приведите примеры самодополнительных графов с 4 и 5 вершинами. Докажите, что если граф является самодополнительным, то он содержит либо $4n$ либо $4n+1$ вершину для некоторого целого положительного $n$.
- Докажите, что для любого целого положительного $n$ существует самодополнительный граф, содержащий $4n$ вершин, а также самодополнительный граф, содержащий $4n+1$ вершину.
- Докажите, что каждый циклический путь нечетной длины содержит простой цикл.
- Докажите или опровергните, что объединение двух любых различных простых путей из вершины $u$ в вершину $v$ содержит цикл.
- Докажите, что граф связен тогда и только тогда когда для любого разбиения его множества вершин $V$ на два непустых непересекающихся множества $X$ и $Y$ существует ребро, соединяющее эти множества.
- Докажите, что в связном графе любые два самых длинных простых пути имеют общую вершину.
- Докажите или опровергните, что в связном графе все самые длинные простые пути имеют общую вершину.
- Обозначим как $\delta(G)$ минимальную степень вершины в графе. Докажите, что если в графе с $n$ вершинами $\delta(G) > (n - 1) / 2$, то он связен.
- Докажите, что либо граф $G$, либо его дополнение $\overline{G}$ связен.
- Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
- Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем четных простых циклов.
- Докажите, что граф с $n$ вершинами и $n + 4$ ребрами содержит два простых цикла, не имеющих общих ребер.
- Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
- Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
- Какое максимальное число точек сочленения может быть в графе с $n$ вершинами?
- Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на цикле. Доказать, что вершинная двусвязность - это $R^*$.
- Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
- Каждое дерево является двудольным графом. А какие деревья являются полными двудольными графами?
- Доказать, что следующие четыре утверждения для связного графа $G$ эквивалентны: (1) любое ребро является мостом (2) $G$ является деревом (3) любой блок $G$ является $K_2$ (4) любое непустое пересечение связных подграфов $G$ связно.
- Доказать, что следующие четыре утверждения для связного графа $G$ эквивалентны: (1) $G$ содержит ровно один простой цикл (2) число вершин и ребер $G$ совпадает (3) $G$ можно превратить в дерево удалением ровно одного ребра (4) множество ребер $G$, которые не являются мостами, образуют один простой цикл.
- Докажите, что любой кубический граф, который содержит точку сочленения, содержит также мост.
- Докажите, что наименьшее число вершин в кубическом графе, в котором есть мост, равно 10.
- Докажите, что если $v$ — точка сочленения в $G$, то $v$ не точка сочленения в $\overline G$.
- Опишите все деревья с диаметром 2.
- Опишите все деревья с диаметром 3.
- Опишите дерево с кодом Прюфера $(i, i,\ldots , i)$.
- Опишите деревья, в коде Прюфера которых нет одинаковых чисел.
- Докажите, что число помеченных неподвешенных деревьев есть $n^{n-2}$, используя теорему Кирхгофа.
- Сколько остовных деревьев у полного двудольного графа $K_{n,m}$?
- Приведите пример графа с двумя непересекающимися остовными деревьями.
- Какое максимальное количество попарно непересекающихся остовных деревьев может быть в графе с $n$ вершинами?
- Пусть связный граф $G$ имеет диаметр $d$. Докажите или опровергните, что у $G$ есть остовное дерево с диаметром $d$.
- Рассмотрим множество остовных деревьев связного графа $G$. Построим граф $S_G$, вершинами которого являются остовные деревья $G$, а две вершины $T_1$ и $T_2$ соединены ребром, если дерево $T_2$ можно получить из $T_1$ удалением одного ребра и добавлением другого. Докажите, что $S_G$ является связным.
- Докажите, что две вершины $T_1$ и $T_2$ в $S_G$ соединены ребром тогда и только тогда, когда их объединение содержит ровно один простой цикл.
- Пусть связный граф $G$ содержит $n$ вершин, докажите, что диаметр $S_G$ не превышает $n - 1$.
- Приведите пример связного графа $G$, содержащего $n$ вершин, для которого граф $S_G$ имеет диаметр $n - 1$.
- Докажите, что для любого $1 \le k \le n - 1$ существует связный граф $G$, содержащий $n$ вершин, такой что диаметр $S_G$ равен $n - k$.
- Обозначим как $\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)$ ребер, чтобы граф потерял связность - удалить все ребра, инцидентные одной из вершин.
