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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «# Во всех задачах этой серии графы неориентированные, ребро соединяет две различные верш…»)
 
Строка 18: Строка 18:
 
# Внутренним автоморфизмом графа называется биекция $\varphi:V\to V$, такая что $uv$ является ребром тогда и только тогда, когда $\varphi(u)\varphi(v)$ является ребром. Сколько внутренних автоморфизмов у полного графа $K_n$?
 
# Внутренним автоморфизмом графа называется биекция $\varphi:V\to V$, такая что $uv$ является ребром тогда и только тогда, когда $\varphi(u)\varphi(v)$ является ребром. Сколько внутренних автоморфизмов у полного графа $K_n$?
 
# Внутренним автоморфизмом графа называется биекция $\varphi:V\to V$, такая что $uv$ является ребром тогда и только тогда, когда $\varphi(u)\varphi(v)$ является ребром. Постройте граф, который не имеет внутренних автоморфизмов, содержащий минимальное число вершин.
 
# Внутренним автоморфизмом графа называется биекция $\varphi:V\to V$, такая что $uv$ является ребром тогда и только тогда, когда $\varphi(u)\varphi(v)$ является ребром. Постройте граф, который не имеет внутренних автоморфизмов, содержащий минимальное число вершин.
# Вершина графа называется висячей, если она имеет степень $1$. постройте граф, не имеющий внутренних автоморфизмов, у которого нет висячих вершин.
+
# Вершина графа называется висячей, если она имеет степень $1$. Постройте граф, не имеющий внутренних автоморфизмов, у которого нет висячих вершин.

Версия 15:37, 31 августа 2024

  1. Во всех задачах этой серии графы неориентированные, ребро соединяет две различные вершины, между парой вершин есть не более одного ребра. Какое максимальное число ребер может быть в графе с $n$ вершинами?
  2. Какое максимальное число ребер может быть в графе с $n$ вершинами и двумя компонентами связности?
  3. Какое максимальное число ребер может быть в графе с $n$ вершинами и $k$ компонентами связности?
  4. Постройте граф с $n$ вершинами, $m$ ребрами и $k$ компонентами связности. Здесь и далее «постройте граф с $n$ вершинами, ...» означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.
  5. Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$. Опишите все такие графы.
  6. Обозначим как $N[u]$ множество, содержащее вершину $u$, а также соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N[u]$ совпадают для всех вершин $u$. Опишите все такие графы.
  7. Постройте граф с $n$ вершинами, где каждая вершина имеет степень $d$.
  8. Докажите, что любой граф, содержащий хотя бы две вершины, имеет две вершины одинаковой степени.
  9. Докажите, что в графе число вершин нечетной степени четно.
  10. Докажите, что если в графе ровно две вершины нечетной степени, то они лежат в одной компоненте связности.
  11. Обозначим как $\delta(G)$ минимальную степень вершины в графе, как $\Delta(G)$ - максимальную степень вершины в графе. Для заданных $n$ и $k$ постройте граф с $n$ вершинами, в котором $\delta(G) + \Delta(G) = k$.
  12. Для заданных $n$, $d$ и $D$ постройте граф с $n$ вершинами, в котором $\delta(G) = d$, $\Delta(G) = D$.
  13. Докажите, что для любого графа $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ имеют общий делитель, отличный от 1, тогда и только тогда, когда в графе $G$ есть ребро $uv$.
  14. В графе $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ равны тогда и только тогда, когда в графе $G$ есть ребро $uv$. Что можно сказать про граф $G$?
  15. Граф называется кубическим, если степень всех вершин равна 3. Какое минимальное число вершин может быть в кубическом графе?
  16. Три вершины графа образуют треугольник, если они попарно соединены ребром. Постройте кубический граф с $n$ вершинами, не содержащий треугольников.
  17. Постройте граф с $n$ вершинами и максимальным числом ребер, не содержащий треугольников.
  18. Внутренним автоморфизмом графа называется биекция $\varphi:V\to V$, такая что $uv$ является ребром тогда и только тогда, когда $\varphi(u)\varphi(v)$ является ребром. Сколько внутренних автоморфизмов у полного графа $K_n$?
  19. Внутренним автоморфизмом графа называется биекция $\varphi:V\to V$, такая что $uv$ является ребром тогда и только тогда, когда $\varphi(u)\varphi(v)$ является ребром. Постройте граф, который не имеет внутренних автоморфизмов, содержащий минимальное число вершин.
  20. Вершина графа называется висячей, если она имеет степень $1$. Постройте граф, не имеющий внутренних автоморфизмов, у которого нет висячих вершин.