ЗАБА Математические олимпиады и олимпиадные задачи
Задачная база >> Разное >> Математический кружок. 2-й год >> Графы-2 >> ИзоморфизмУбрать решения
С.А.Генкин, И.В.Итенберг, Д.В.Фомин. Математический кружок, 2-й год. Графы-2. Изоморфизм

Задача 2:

Докажите, что не существует графа с пятью вершинами, степени которых равны 4, 4, 4, 4, 2.

Решение:

Поскольку из всех вершин, кроме одной выходит по 4 ребра, то и из пятой вершины также должно выходить четыре ребра.

Задача 3:

Докажите, что существует граф с 2n вершинами, степени которых равны 1, 1, 2, 2, …, n, n.

Решение:

Используйте индукцию по n.

Задача 4:

Верно ли, что два графа изоморфны, если

а) у них по 10 вершин, степень каждой из которых равна 9?

б) у них по 8 вершин, степень каждой из которых равна 3?

в) они связны, без циклов и содержат по 6 ребер?

Решение:

а) Верно. Каждая вершина соединена с каждой.

б) Нет

в) Нет

Задача 5:

В связном графе степени четырех вершин равны 3, а степени остальных вершин равны 4. Докажите, что нельзя удалить ребро так, чтобы граф распался на две изоморфные компоненты связности.

Решение:

Если это ребро соединяет вершины с одинаковыми степенями, то в каждой компоненте нечетное число нечетных вершин. В противном случае только в одной компоненте будет вершина степени 2.



Задачная база >> Разное >> Математический кружок. 2-й год >> Графы-2 >> ИзоморфизмУбрать решения