Список заданий по ДМ 2к 2019 осень — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 52: Строка 52:
 
# Выразите число треугольников в реберном графе $G_E$ через число треугольников графа $G$ и набор его степеней.
 
# Выразите число треугольников в реберном графе $G_E$ через число треугольников графа $G$ и набор его степеней.
 
# В каком случае связный граф $G$ имеет регулярный реберный граф?
 
# В каком случае связный граф $G$ имеет регулярный реберный граф?
# Постройте граф $G$ с $n \ge 4$ вершинами, для которого граф $G_E$ не эйлеров, а граф $G_E^2$ эйлеров.
+
# Постройте граф $G$ с $n \ge 4$ вершинами, для которого граф $G_E$ не эйлеров, а граф $(G_E)_E$ эйлеров.
# Докажите, что если $G$ содержит $n \ge 5$ вершин, то если $G_E^2$ эйлеров, то и $G_E^3$ эйлеров.
+
# Докажите, что если $G$ содержит $n \ge 5$ вершин, то если $(G_E)_E$ эйлеров, то и $((G_E)_E)_E$ эйлеров.
 
# Постройте минимальный по числу вершин реберный граф, в котором нет гамильтонова цикла.
 
# Постройте минимальный по числу вершин реберный граф, в котором нет гамильтонова цикла.
 
# Докажите, что $G_E$ гамильтонов тогда и только тогда, когда граф $G$ содержит циклический реберно простой путь, содержащий хотя бы одну вершину, инцидентную каждому ребру графа $G$.
 
# Докажите, что $G_E$ гамильтонов тогда и только тогда, когда граф $G$ содержит циклический реберно простой путь, содержащий хотя бы одну вершину, инцидентную каждому ребру графа $G$.

Версия 17:36, 24 сентября 2019

  1. Постройте граф с $n$ вершинами, $m$ ребрами и $k$ компонентами связности. Здесь и далее "постройте граф с $n$ вершинами, ..." означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.
  2. Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$.
  3. Обозначим как $N[u]$ множество, содержащее вершину $u$, а также соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N[u]$ совпадают для всех вершин $u$.
  4. Постройте граф с $n$ вершинами, где каждая вершина имеет степень $d$.
  5. Докажите, что любой граф, содержащий хотя бы две вершины, имеет две вершины одинаковой степени.
  6. Обозначим как $\delta(G)$ минимальную степень вершины в графе, как $\Delta(G)$ - максимальную степень вершины в графе. Постройте граф с $n$ вершинами, в котором $\delta(G) + \Delta(G) > n$.
  7. Докажите, что если в графе с $n$ вершинами $\delta(G) > (n - 1) / 2$, то он связен.
  8. Докажите, что для любого графа $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ имеют общий делитель, отличный от 1, тогда и только тогда, когда в графе $G$ есть ребро $uv$.
  9. Граф называется кубическим, если степень всех вершин равна 3. Три вершины графа образуют треугольник, если они попарно соединены ребром. Постройте кубический граф с $n$ вершинами, не содержащий треугольников.
  10. Граф называется самодополнительным, если он изоморфен своему дополнению. Приведите примеры самодополнительных графов с 4 и 5 вершинами. Докажите, что если граф является самодополнительным, то он содержит либо $4n$ либо $4n+1$ вершину для некоторого целого положительного $n$.
  11. Докажите, что для любого целого положительного $n$ существует самодополнительный граф, содержащий $4n$ вершин, а также самодополнительный граф, содержащий $4n+1$ вершину.
  12. Докажите, что граф связен тогда и только тогда когда для любого разбиения его множества вершин $V$ на два непустых непересекающихся множества $X$ и $Y$ существует ребро, соединяющее эти множества.
  13. Докажите, что в связном графе любые два самых длинных простых пути имеют общую вершину.
  14. Докажите или опровергните, что в связном графе все простые пути, имеющие максимальную возможную длину в этом графе, имеют общую вершину.
  15. Докажите, что либо граф $G$, либо его дополнение $\overline{G}$ связен.
  16. Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
  17. Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем нечётных простых циклов.
  18. Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем чётных простых циклов.
  19. Докажите, что граф с $n$ вершинами и $n + 4$ ребрами содержит два простых цикла, не имеющих общих ребер.
  20. Докажите, что наименьшее число вершин в кубическом графе, в котором есть мост, равно 10.
  21. Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
  22. Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
  23. Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на цикле. Доказать, что вершинная двусвязность - это $R^*$.
  24. Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
  25. Каждое дерево является двудольным графом. А какие деревья являются полными двудольными графами?
  26. Докажите, что любой кубический граф, который содержит точку сочленения, содержит также мост.
  27. Докажите, что если $v$ точка сочленения в $G$, то $v$ не точка сочленения в $\overline G$.
  28. Опишите дерево с кодом Прюфера $(i, i,\ldots , i)$.
  29. Докажите, что число помеченных неподвешенных деревьев есть $n^{n-2}$, используя теорему Кирхгофа.
  30. Сколько остовных деревьев у полного двудольного графа $K_{n,m}$?
  31. Какое максимальное количество попарно непересекающихся остовных деревьев может быть в графе с $n$ вершинами?
  32. Диаметром графа называют максимальное значение кратчайшего пути между двумя его вершинами. Пусть связный граф $G$ имеет диаметр $d$. Докажите или опровергните, что у $G$ есть остовное дерево с диаметром $d$.
  33. Рассмотрим множество остовных деревьев связного графа $G$. Построим граф $S_G$, вершинами которого являются остовные деревья $G$, а две вершины $T_1$ и $T_2$ соединены ребром, если дерево $T_2$ можно получить из $T_1$ удалением одного ребра и добавлением другого. Докажите, что $S_G$ является связным.
  34. Докажите, что две вершины $T_1$ и $T_2$ в $S_G$ соединены ребром тогда и только тогда, когда их объединение содержит ровно один простой цикл.
  35. Пусть связный граф $G$ содержит $n$ вершин, докажите, что диаметр $S_G$ не превышает $n - 1$.
  36. Приведите пример связного графа $G$, содержащего $n$ вершин, для которого граф $S_G$ имеет диаметр $n - 1$.
  37. Докажите, что для любого $1 \le k \le n - 1$ существует связный граф $G$, содержащий $n$ вершин, такой что диаметр $S_G$ равен $n - k$.
  38. Докажите, что если в связном графе есть реберно простой цикл длины $k$, то у графа есть не менее $k$ остовных деревьев.
  39. Обобщение формулы Кэли. Пусть дан полный граф из $n$ вершин, и лес в нём, компоненты связности леса имеют размеры $c_1, c_2, \ldots, c_k$. Докажите, что число способов добавить ребра, чтобы получилось дерево, равно $c_1c_2\ldots c_k(c_1+c_2+\ldots+c_k)^{k-2}$.
  40. Граф называется произвольно вычерчиваемым из вершины $u$, если следующая процедура всегда приводит к эйлеровому циклу: начиная с вершины $u$, переходим каждый раз по любому исходящему из текущей вершины ребру, по которому ранее не проходили. Докажите, что эйлеров граф является произвольно вычерчиваемым из $u$, если любой его простой цикл содержит $u$.
  41. Докажите, что если граф $G$ является произвольно вычерчиваемым из $u$, то $u$ имеет максимальную степень в $G$.
  42. Докажите, что если граф $G$ является произвольно вычерчиваемым из $u$, то либо $u$ - единственная точка сочленения в $G$, либо в $G$ нет точек сочленения.
  43. Доказать или опровегнуть, что если $G$ содержит порожденный тета-подграф (две вершины, соединенные тремя путями), то $G$ не гамильтонов.
  44. Обозначим как $G^3$ граф, в котором две вершины соединены, если они соединены в $G$ путем длины не более 3. Докажите, что если $G$ связен, то $G^3$ гамильтонов.
  45. Граф называется произвольно гамильтоновым, если следующая процедура всегда приводит к гамильтонову циклу: начиная с произвольной вершины $u$, переходим каждый раз по любому исходящему из текущей вершины ребру, другой конец которого мы ранее не посещали, либо обратно в вершину $u$, если непосещенных соседей нет. Опишите все произвольно гамильтоновы графы.
  46. Теорема "Антихватала". Докажите, что если не выполнено условие теоремы Хватала, то найдется граф с такой степенной последовательностью, не содержащий гамильтонова цикла.
  47. Докажите, что если сумма степеней любых двух несмежных вершин графа $G$ не меньше $n+1$, то любые две различные вершины $G$ можно соединить гамильтоновым путем.
  48. Докажите усиленную версию теоремы Редеи-Камеона: в любом сильно связном турнире с $n$ вершинами есть простой цикл любой длины от $3$ до $n$.
  49. Реберным графом для графа $G$ называется граф $G_E$, множество вершин которого совпадает с множеством ребер исходного графа, два ребра $e$ и $f$ соединены ребром в реберном графе, если у них есть общая инцидентная вершина. Докажите или опровергните, что если $G$ является эйлеровым, то реберный граф является гамильтоновым.
  50. Докажите или опровергните, что если $G_E$ является гамильтоновым, то граф $G$ является эйлеровым.
  51. В каком случае ребра реберного графа можно разбить на полные подграфы таким образом, чтобы каждая вершина принадлежала в точности двум из подграфов?
  52. Выразите число треугольников в реберном графе $G_E$ через число треугольников графа $G$ и набор его степеней.
  53. В каком случае связный граф $G$ имеет регулярный реберный граф?
  54. Постройте граф $G$ с $n \ge 4$ вершинами, для которого граф $G_E$ не эйлеров, а граф $(G_E)_E$ эйлеров.
  55. Докажите, что если $G$ содержит $n \ge 5$ вершин, то если $(G_E)_E$ эйлеров, то и $((G_E)_E)_E$ эйлеров.
  56. Постройте минимальный по числу вершин реберный граф, в котором нет гамильтонова цикла.
  57. Докажите, что $G_E$ гамильтонов тогда и только тогда, когда граф $G$ содержит циклический реберно простой путь, содержащий хотя бы одну вершину, инцидентную каждому ребру графа $G$.