Рассмотрим некоторый граф. Верно ли, что каждой вершине графа можно сопоставить отрезок на плоскости так, что отрезки, соответствующие вершинам a и b, пересекаются тогда и только тогда, когда вершины a и b соединены ребром.

задан 27 Сен '12 19:00

изменен 27 Сен '12 19:32

Приветствую Вас! С возвращением!

А прямолинейность отрезков важна? Все-таки граф - топологический объект.

(27 Сен '12 21:16) DocentI

Прямолинейность важна. В этом смысле название не совсем точно. Вообще задача появилась из олимпиадной задачи: Можно ли на плоскости расположить а)6 б)7 отрезков так, чтобы каждый пересекался ровно с двумя другими. Участник решил пункт б), доказав, что невозможно построить граф соответствующий данной картинке, а в качестве решения пункта а нарисовал граф и сказал, что раз граф существует, то и конфигурация существует. Вот мне хотелось не просто сказать, что утверждение не доказано, а привести контрпример.

(27 Сен '12 22:08) dmg3

Если именно с двумя, то многоугольник подходит.

(27 Сен '12 22:46) un75
1

Тут вопрос о другом: не решить задачу, а оценить существующее решение.

(27 Сен '12 23:54) DocentI
1

Простите, с тремя.

(28 Сен '12 7:53) dmg3

Решение участником пункта б) однозначно верно (вероятно, он писал что-то вроде "предположим, что конфигурация существует. но тогда всего будет 7х3/2=10.5 пересечений отрезков"?). У пункта а) верный ответ, а вот насчет решения пока ничего сказать наверняка не могу.
Я как-то видел, как заслуженные олимпиадники использовали такой же прием, поэтому осмелюсь предположить, что он верный, но формально у меня за сутки не получилось ни доказать, ни опровергнуть его правильность ((

(30 Сен '12 14:37) chameleon
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×2,301
×102

задан
27 Сен '12 19:00

показан
639 раз

обновлен
30 Сен '12 14:37

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

по почте:

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

по RSS:

Ответы

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

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