Могут ли быть не изоморфны два графа, если каждый из них имеет 13 вершин и 76 рёбер?

задан 18 Июн '15 0:13

10|600 символов нужно символов осталось
1

Графы здесь имеются в виду простые -- без петель и кратных рёбер (без этого ограничения задача делается слишком простой).

В полном графе с 13 вершинами рёбер имеется $%\frac{13\cdot12}2=78$%. Это значит, что дополнения обоих графов имеют по 2 ребра. Изоморфизм графов равносилен изоморфизму их дополнений, поэтому в условии задачи можно заменить 76 на 2. Становится ясно, что такие графы не всегда изоморфны: в одном из них рёбра могут не иметь общей вершины, а в другом они могут иметь общую вершину. Поэтому графы могут быть не изоморфны.

ссылка

отвечен 18 Июн '15 0:47

10|600 символов нужно символов осталось
0

Могут. У полного графа на 13-и вершинах 78 ребер. 76 получится, если удалить любые 2 ребра. Если в одном графе удалить 2 ребра, выходящие из одной вершины, а в другом - из разных, то такие графы неизоморфны.

ссылка

отвечен 18 Июн '15 0:39

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,050

задан
18 Июн '15 0:13

показан
445 раз

обновлен
18 Июн '15 0:47

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru