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