Расскажите, пожалуйста, про самодополнительный граф. Если дан квадрат со сторонами $%ABCD$%, где $%A$% - верхняя левая вершина, а остальные по часовой стрелке, и соединены вершины в порядке $%ADBC$%, то его дополнительный граф $%BACD$% изоморфен ему.
Что означает величина $%n(n-1)/4$%?

задан 13 Ноя '14 23:51

изменен 14 Ноя '14 21:12

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

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

Пусть дан граф с $%n$% вершинами. Для удобства раскрасим его рёбра в красный цвет. Все рёбра, которые в этот граф не входят, образуют дополнительный граф. Его рёбра раскрашиваем синим. Граф называется самодополнительным, если он изоморфен своему дополнению. Это значит, что красная и синяя "картинки", нарисованные отдельно, являются одинаковыми при удачно подобранном соответствии между вершинами.

Для полного графа с 4 вершинами (квадрат плюс диагонали) можно рассмотреть красные рёбра AB - BC - CD. Это даёт граф из трёх отрезков, соединённых в линию (т.н. линейный граф). Оставшиеся рёбра CA - AD - DB образуют такой же граф.

Другим примером самодополнительного графа является контур пятиугольника. Внутри него получается "звёздочка", и если её изъять и "разогнуть", то снова будет пятиугольник.

Общее число рёбер полного графа равно $%n(n-1)/2$%. Поэтому самодополнительный граф обязан иметь половину от этого количества рёбер, а это как раз $%n(n-1)/4$%. Такое возможно лишь в случае, если $%n$% делится на 4 или даёт при делении на 4 в остатке 1. Это условие (наличие ровно $%n(n-1)/4$% рёбер) необходимо для самодополнительности графа, но не достаточно.

ссылка

отвечен 14 Ноя '14 0:09

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

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

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

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

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

отмечен:

×1,273

задан
13 Ноя '14 23:51

показан
1261 раз

обновлен
15 Ноя '14 14:33

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

по почте:

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

по RSS:

Ответы

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

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