Роман Надыршин
22.09.2020 19:32:47
Другой предмет 10-11 класс
50 баллов
сколько существует попарно неизоморфных графов с 10 вершинами и 43 ребрами
Ирина Каминкова
0
22.09.2020 21:54:01
Предполагаем граф без петель и кратных ребер.

В полном графе с 10 вершинами имеется 10*9/2 = 45 ребер.
Дополнением к данному графу будет граф с 2-мя ребрами.
Графы изоморфны тогда и только тогда, когда изоморфны их дополнения, поэтому достаточно перечислить все попарно неизоморфные графы с 10 вершинами и 2 ребрами.
В графе с 2 ребрами циклов нет.
Неизоморфных графов с 2 ребрами 2:
1) "уголок", в котором двумя ребрами соединены 3 точки
2) две "палки", в которых двумя ребрами соединены 2*2=4 точки

Ответ: 2

Регистрация
Войти с помощью
Необходимо принять пользовательское соглашение
Войти
Войти с помощью
Восстановление пароля
Пожаловаться
Задать вопрос