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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «<wikitex> # Постройте граф с 7 вершинами и 11 ребрами. # Для каких $n$ и $m$ можно построить граф с $n$...»)
(нет различий)

Версия 11:11, 4 сентября 2017

<wikitex>

  1. Постройте граф с 7 вершинами и 11 ребрами.
  2. Для каких $n$ и $m$ можно построить граф с $n$ вершинами и $m$ ребрами?
  3. Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$. Здесь и далее "постройте граф с $n$ вершинами, ..." означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует.
  4. Обозначим как $N[u]$ множество, содержащее вершину $u$, а также соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N[u]$ совпадают для всех вершин $u$.
  5. Постройте граф с 9 вершинами, где каждая вершина имеет степень 3.
  6. Постройте граф с $n$ вершинами, где каждая вершина имеет степень $d$.
  7. Докажите, что любой граф, содержащий хотя бы две вершины, имеет две вершины одинаковой степени.
  8. Обозначим как $\delta(G)$ минимальную степень вершины в графе, как $\Delta(G)$ - максимальную степень вершины в графе. Постройте граф с $n$ вершинами, в котором $\delta(G) + \Delta(G) > n$.
  9. Постройте двудольный граф с $n$ вершинами, в котором $\delta(G) + \Delta(G) > n$.
  10. Пусть для двудольного графа выполнено условие: для любой пары не соединенных ребром вершин есть вершина, связанная с обеими этими вершинами. Как устроен такой граф?
  11. Докажите, что для любого графа $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ имеют общий делитель, отличный от 1, тогда и только тогда, когда в графе $G$ есть ребро $uv$.
  12. Граф называется кубическим, если степень всех вершин равна 3. Три вершины графа образуют треугольник, если они попрано соединены ребром. Постройте кубический граф с $2n$ вершинами, не содержащий треугольников.
  13. Граф называется самодополнительным, если он изоморфен своему дополнению. Приведите примеры самодополнительных графов с 4 и 5 вершинами. Докажите, что если граф является самодополнительным, то он содержит либо $4n$ либо $4n+1$ вершину для некоторого целого положительного $n$.
  14. Докажите, что для любого целого положительного $n$ существует самодополнительный граф, содержащий $4n$ вершин, а также самодополнительный граф, содержащий $4n+1$ вершину.

</wikitex>