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