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