Будем рассматривать не сами графы, а их дополнения. (Дополнение графа - это граф, в котором 2 вершины смежны тогда и только тогда, когда они не смежны в исходном). Легко видеть, что все дополнения представляют собой регулярные графы типа (7,2). Приведём пример 2 графов, не изоморфных между собой - цикл длины 7 и объедининие цикла длины 4 и цикла длины 3. В последнем графе есть треугольник, а в первом треугольника нет. Значит, 2 исходных графа тоже не изоморфны - в одном есть 3 вершины, никакая из которых не смежна с другой, а в другом таких 3 вершин нет.
0,0(0 оценок)
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota
Оформи подписку
