Олимпиадная задача: изоморфизм графов с одинаковыми степенями вершин
Верно ли, что два графа изоморфны, если
а) у них по 10 вершин, степень каждой из которых равна 9?
б) у них по 8 вершин, степень каждой из которых равна 3?
в) они связны, без циклов и содержат по 6 рёбер?
Показать ответ
а) Верно; б)-в) неверно.
Разобрать решение
а) В таком графе каждая вершина соединена со всеми остальными. б) См. контрпример:
в) См. контрпример:
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.