Список заданий по ДМ 2к 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$. Постройте граф, не имеющий внутренних автоморфизмов, у которого нет висячих вершин.