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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «# Постройте граф с $n$ вершинами, $m$ ребрами и $k$ компонентами связности. Здесь и далее "пост…»)
 
Строка 15: Строка 15:
 
# Докажите, что либо граф $G$, либо его дополнение $\overline{G}$ связен.
 
# Докажите, что либо граф $G$, либо его дополнение $\overline{G}$ связен.
 
# Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
 
# Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
 +
# Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем нечётных простых циклов.
 +
# Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем чётных простых циклов.
 
# Докажите, что граф с $n$ вершинами и $n + 4$ ребрами содержит два простых цикла, не имеющих общих ребер.
 
# Докажите, что граф с $n$ вершинами и $n + 4$ ребрами содержит два простых цикла, не имеющих общих ребер.
# Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
+
# Докажите, что наименьшее число вершин в кубическом графе, в котором есть мост, равно 10.
# Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
 
# Какое максимальное число точек сочленения может быть в графе с $n$ вершинами?
 

Версия 16:55, 7 сентября 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.