1. На шахматной доске размера 3х5 в одной из клеток находится белый конь (так как клеток 15, таких конфигураций можно придумать тоже 15). Каждая из конфигураций будет считаться вершиной некоторого графа. Конь из исходного положения может перейти «буквой Г» в новую конфигурацию. Сделав это, мы получим воображаемое ребро графа. Если конь может переместиться несколькими способами, значит, из исходной «вершины» выходят несколько «рёбер». Из новой вершины, возможно, удастся переместиться (и даже, быть может, многими способами) в «сверхновую вершину». Все эти способы дадут нам ещё несколько «рёбер». И так далее – пока конь не зайдёт в тупик или не начнёт циклически ходить по одним и тем же полям. Проделав эту процедуру для каждого исходного положения коня, мы окончательно узнаем, сколько же есть «рёбер» у этого необычного графа.

Вопросы:
Как выглядит этот граф в обычном изображении (вершины=точки на плоскости, рёбра=отрезки кривых на плоскости)? Будет ли он связным? Если НЕТ, то из скольких кусков он состоит? Будет ли он однородным? Есть ли у него висячие вершины? Есть ли точки сочленения? Дерево ли это? Лес ли это? Чего больше: рёбер или вершин? Не мультиграф ли это? Или, чего доброго, это псевдограф?

задан 19 Апр '15 22:15

изменен 20 Апр '15 8:29

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


9917

Этот граф легко рисуется по описанию. Проще всего сделать так: заполнить таблицу 3x5, вписав в каждую клетку степень соответствующей вершине. Она равна числу ходов коня из этой вершины в пределах поля. Получится 8 вершин степени 2 (их можно нарисовать в последнюю очередь), 4 вершины степени 3 и 3 вершины степени 4. Далее рисуем отдельно 7 вершин и проводим нужные соединения. В конце дорисовываем 8 вершин степени два, деля рёбра на 2 части. Все свойства после этого становятся видны: граф связен, не имеет висячих вершин и т.п.

(20 Апр '15 6:59) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,540

задан
19 Апр '15 22:15

показан
180 раз

обновлен
20 Апр '15 6:59

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

по почте:

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

по RSS:

Ответы

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

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