Опубликовано 03.01.2018 по предмету Математика от Гость

Верно ли что все регулярные графы типа (7,4( ( 7 вершин степень которых равна 4) изоморфны ?

Ответ оставил Гость

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

Не нашел нужный ответ?

Если ответ по предмету Математика отсутствует или он оказался неправильным, то попробуй воспользоваться поиском других ответов во всей базе сайта.


Найти другие ответы
Самые новые вопросы