|
Рассмотрим некоторый граф. Верно ли, что каждой вершине графа можно сопоставить отрезок на плоскости так, что отрезки, соответствующие вершинам a и b, пересекаются тогда и только тогда, когда вершины a и b соединены ребром. задан 27 Сен '12 19:00 
dmg3
показано 5 из 6
показать еще 1
|
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
27 Сен '12 19:00
показан
1199 раз
обновлен
30 Сен '12 14:37
Связанные исследования
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Приветствую Вас! С возвращением!
А прямолинейность отрезков важна? Все-таки граф - топологический объект.
Прямолинейность важна. В этом смысле название не совсем точно. Вообще задача появилась из олимпиадной задачи: Можно ли на плоскости расположить а)6 б)7 отрезков так, чтобы каждый пересекался ровно с двумя другими. Участник решил пункт б), доказав, что невозможно построить граф соответствующий данной картинке, а в качестве решения пункта а нарисовал граф и сказал, что раз граф существует, то и конфигурация существует. Вот мне хотелось не просто сказать, что утверждение не доказано, а привести контрпример.
Если именно с двумя, то многоугольник подходит.
Тут вопрос о другом: не решить задачу, а оценить существующее решение.
Простите, с тремя.
Решение участником пункта б) однозначно верно (вероятно, он писал что-то вроде "предположим, что конфигурация существует. но тогда всего будет 7х3/2=10.5 пересечений отрезков"?). У пункта а) верный ответ, а вот насчет решения пока ничего сказать наверняка не могу.
Я как-то видел, как заслуженные олимпиадники использовали такой же прием, поэтому осмелюсь предположить, что он верный, но формально у меня за сутки не получилось ни доказать, ни опровергнуть его правильность ((