244
правки
Изменения
Новая страница: «# Во всех задачах этой серии графы неориентированные, ребро соединяет две различные верш…»
# Во всех задачах этой серии графы неориентированные, ребро соединяет две различные вершины, между парой вершин есть не более одного ребра. Какое максимальное число ребер может быть в графе с $n$ вершинами?
# Какое максимальное число ребер может быть в графе с $n$ вершинами и двумя компонентами связности?
# Какое максимальное число ребер может быть в графе с $n$ вершинами и $k$ компонентами связности?
# Постройте граф с $n$ вершинами, $m$ ребрами и $k$ компонентами связности. Здесь и далее «постройте граф с $n$ вершинами, ...» означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.
# Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$. Опишите все такие графы.
# Обозначим как $N[u]$ множество, содержащее вершину $u$, а также соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N[u]$ совпадают для всех вершин $u$. Опишите все такие графы.
# Постройте граф с $n$ вершинами, где каждая вершина имеет степень $d$.
# Докажите, что любой граф, содержащий хотя бы две вершины, имеет две вершины одинаковой степени.
# Докажите, что в графе число вершин нечетной степени четно.
# Докажите, что если в графе ровно две вершины нечетной степени, то они лежат в одной компоненте связности.
# Обозначим как $\delta(G)$ минимальную степень вершины в графе, как $\Delta(G)$ - максимальную степень вершины в графе. Для заданных $n$ и $k$ постройте граф с $n$ вершинами, в котором $\delta(G) + \Delta(G) = k$.
# Для заданных $n$, $d$ и $D$ постройте граф с $n$ вершинами, в котором $\delta(G) = d$, $\Delta(G) = D$.
# Докажите, что для любого графа $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ имеют общий делитель, отличный от 1, тогда и только тогда, когда в графе $G$ есть ребро $uv$.
# В графе $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ равны тогда и только тогда, когда в графе $G$ есть ребро $uv$. Что можно сказать про граф $G$?
# Граф называется кубическим, если степень всех вершин равна 3. Какое минимальное число вершин может быть в кубическом графе?
# Три вершины графа образуют треугольник, если они попарно соединены ребром. Постройте кубический граф с $n$ вершинами, не содержащий треугольников.
# Постройте граф с $n$ вершинами и максимальным числом ребер, не содержащий треугольников.
# Внутренним автоморфизмом графа называется биекция $\varphi:V\to V$, такая что $uv$ является ребром тогда и только тогда, когда $\varphi(u)\varphi(v)$ является ребром. Сколько внутренних автоморфизмов у полного графа $K_n$?
# Внутренним автоморфизмом графа называется биекция $\varphi:V\to V$, такая что $uv$ является ребром тогда и только тогда, когда $\varphi(u)\varphi(v)$ является ребром. Постройте граф, который не имеет внутренних автоморфизмов, содержащий минимальное число вершин.
# Вершина графа называется висячей, если она имеет степень $1$. постройте граф, не имеющий внутренних автоморфизмов, у которого нет висячих вершин.
# Какое максимальное число ребер может быть в графе с $n$ вершинами и двумя компонентами связности?
# Какое максимальное число ребер может быть в графе с $n$ вершинами и $k$ компонентами связности?
# Постройте граф с $n$ вершинами, $m$ ребрами и $k$ компонентами связности. Здесь и далее «постройте граф с $n$ вершинами, ...» означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.
# Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$. Опишите все такие графы.
# Обозначим как $N[u]$ множество, содержащее вершину $u$, а также соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N[u]$ совпадают для всех вершин $u$. Опишите все такие графы.
# Постройте граф с $n$ вершинами, где каждая вершина имеет степень $d$.
# Докажите, что любой граф, содержащий хотя бы две вершины, имеет две вершины одинаковой степени.
# Докажите, что в графе число вершин нечетной степени четно.
# Докажите, что если в графе ровно две вершины нечетной степени, то они лежат в одной компоненте связности.
# Обозначим как $\delta(G)$ минимальную степень вершины в графе, как $\Delta(G)$ - максимальную степень вершины в графе. Для заданных $n$ и $k$ постройте граф с $n$ вершинами, в котором $\delta(G) + \Delta(G) = k$.
# Для заданных $n$, $d$ и $D$ постройте граф с $n$ вершинами, в котором $\delta(G) = d$, $\Delta(G) = D$.
# Докажите, что для любого графа $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ имеют общий делитель, отличный от 1, тогда и только тогда, когда в графе $G$ есть ребро $uv$.
# В графе $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ равны тогда и только тогда, когда в графе $G$ есть ребро $uv$. Что можно сказать про граф $G$?
# Граф называется кубическим, если степень всех вершин равна 3. Какое минимальное число вершин может быть в кубическом графе?
# Три вершины графа образуют треугольник, если они попарно соединены ребром. Постройте кубический граф с $n$ вершинами, не содержащий треугольников.
# Постройте граф с $n$ вершинами и максимальным числом ребер, не содержащий треугольников.
# Внутренним автоморфизмом графа называется биекция $\varphi:V\to V$, такая что $uv$ является ребром тогда и только тогда, когда $\varphi(u)\varphi(v)$ является ребром. Сколько внутренних автоморфизмов у полного графа $K_n$?
# Внутренним автоморфизмом графа называется биекция $\varphi:V\to V$, такая что $uv$ является ребром тогда и только тогда, когда $\varphi(u)\varphi(v)$ является ребром. Постройте граф, который не имеет внутренних автоморфизмов, содержащий минимальное число вершин.
# Вершина графа называется висячей, если она имеет степень $1$. постройте граф, не имеющий внутренних автоморфизмов, у которого нет висячих вершин.
