В графе G на множестве вершин {0, 1, . . . , 66} ребром соединены пары вершин x, y, для которых выполняется 13(x − y) ≡ ±4 (mod 67). Является ли граф G связным? Обоснуйте ответ

задан 15 Дек '15 22:55

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

Является. Сравнение равносильно тому, что $%x-y\equiv10\pmod{67}$%. Числа 67 и 10 взаимно просты, откуда всё следует. То есть имеются соединения 0 - 10 - 20 - ... - 60 - 70=3 - 13 - ... - 63 - 73=6 - 16 - ... - 76=9 - 19 - ... - 69=2 - 12 - ... - 72=5 - 15 - ... - 75=8 - 18 - ... - 68=1 - 11 - ... - 71=4 - 14 - ... - 74=7 - 17 - ... - 57 - 67=0, то есть все числа задействованы, и граф не только связен, но даже гамильтонов.

ссылка

отвечен 16 Дек '15 0:16

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

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

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

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

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

отмечен:

×1,307
×499
×37

задан
15 Дек '15 22:55

показан
639 раз

обновлен
16 Дек '15 0:16

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

по почте:

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

по RSS:

Ответы

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

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