#0
by Ненавижу 1С
На плоскости задан граф с N вершинами. Каждая пара различных вершин соединена между собой не более чем одним ребром (замкнутая кривая). При этом ребра на плоскости не пересекаются. Есть ли формула, определяющая по числу вершин N максимально возможное число таких ребер?
#3
by Torquader
Вообще-то, максимальное число - однозначно, когда система образует набор треугольников, так как если есть фигура с большим числом углов, то её можно разбить на треугольники.
#5
by Torquader
первая строка нужна, чтобы определить, что при N=0 получаем 0 при N=1 получаем 0 при N=2 получаем 1 при N=3 получаем 3 при N=4 получаем 6 Далее строится предположение, что если мы к максимальному числу добавим максимальное, то получится тоже максимальное. То, что при N=4 максимально 6, но наружу смотрят только 3, мы получаем указанную формулу, но возникает вопрос, если у нас не максимальное число, но видно не три точки, а четыре, то верно ли это будет ? Например 6+3=9, но и 5+4=9.
#7
by NewNick
я говорил что : при N=3 получаем 3 при N=4 получаем 6 этот же результат дает и вторая строка )
#8
by Torquader
Таки и вторая строка при N>2 даёт тот же результат. N=3 N(N-1)/2=3 3*(N-2)=3 N=4 N(N-1)/2=6 3*(N-2)=6 То есть причин, по которым нужно вводить первую формулу, нет, так как при N=2 получаем 1, а при N<2 получаем 0.
#11
by dk
что-то не выстраивается картинка :( "Каждая пара различных вершин соединена между собой не более чем одним ребром" это типа "змея кусает свой хвост" или "не более чем одним" может и ноль означать или типа правильного выпуклого многоугольника и надо рассчитать кол-во непересекающихся ребер?
#12
by mrkorn
>> при N=4 получаем 6 интересно как можно соединить 4 точки 6ю не пересекающимися отрезками?
#14
by NewNick
+ вобшем решение задачи выглядит очень просто - надо добавить еще точку строим еще один тетраэдр на любом имеющемся на плоскости треугольнике и опять зовем слона.
#18
by acsent
С теорией графов не знаком? Ребро не отрезок, а проста пара вершин, просто для удобства изображают отрезком
#19
by NewNick
аааа типо если это прямые то пересекутся. а если не прямые то подпрыгнут над бумажкой ?)
#20
by NewNick
ап. а решение задачки кто нить выложит ? я вчера минут 30 не мог заснуть пока не решил. явно есть несколько решений. интересно сравнить просто.
#21
by Ненавижу 1С
для N<=4 каждую вершину можно соединить с каждой. Основной случай для N>4. Рассмотрим такой граф. Очевидно он разбивает плоскость на области с границами из трех ребер (иначе можно всегда добавить еще одно ребро, разбив область). Добавляем к графу еще одну вершину, она попадет в некоторую область. Соответственно, можно добавить только 3 ребра. При N=4 это 6. По индукции получаем 3*(N-2).
#26
by NewNick
а теперь осталось доказать что добавление одной вершины для графа с N вершин будет и максимальным кол-вом ребер даст граф с N+1 вершиной и максимальным кол-вом ребер
#28
by NewNick
почему вы отсчет с N=4 начинаете понять не могу никак, логичней с N=3 начинать. но видимо дело вкуса )
#29
by Torquader
вот это, как раз, самое спорное. То есть берут изначально максимальный граф и в него добавляют вершину и определяют максимум рёбер, но возникает вопрос, а что если был не максимальный граф, и мы добавили вершину - случаи, когда число рёбер совпадает с максимальным, можно легко получить переносом ребра в четырёхугольнике.
#30
by SUA
По определению плоского графа. Это такой граф вершины которого лежат в одной плоскости а ребра не пересекаются. Теперь при N>=3 Делаем так: 1) перемещаем некоторые 3 вершины так чтобы весь граф попал в треугольник образованный этими вершинами. Если это сделать не получается (получается четырех- и более угольник), то число ребер не максимально - можно соединить 2 несоседних вершины ребром. 2) внутри графа все области - треугольники Если нет - то также в любом 4х- и более угольнике можно добавить ребро что граф останется плоским. 3) далее, поскольку все области - треугольники, то они могут быть получены в некоторой последовательности "методом слона" вотЪ
#31
by SUA
или если в если мы берем не максимальный граф (N вершин), добавляем вершину и ребрами из нее делаем граф максимальным, то это то же самое, что мы добавляем в каком-то многоугольнике (k углов) внутри одну вершину графа и соединяем ее со всеми вершинами этого многоугольника. При этом, чтобы сделать исходный граф максимальным - надо разбить k-угольник на треугольники (добавится k-3 ребра), а в (N+1)-угольнике добавится k ребер. То есть, одна вершина добавить всегда ровно 3 ребра.
#32
by NewNick
уху я так же рассуждал. удаление одной вершины всегда дает удаление максимум 3 ребер. стало быть граф построенный методом "слона" оптимален )
#34
by mikadi
Классическая оценка (действительно, через максимальный плоский граф, в котором все грани - треугольники): m <= 3n-6. (m - кол-во рёбер, n - кол-во вершин).
#35
by mikadi
+ Действует, разумеется, для графов с n>=3. Для n=2 графа с треугольными гранями не существует :)
#36
by Ненавижу 1С
по формуле Эйлера имеем В-Р+Г=2, где В - число вершин, Р - ребер, Г - граней (здесь областей). Каждое ребро принадлежит 2 областям, а как сказали каждая область треугольная. Поэтому: Г=(2/3)*Р. Подставляем и получаем: Р=3*(В-2)
#38
by NewNick
если нельзя то делаем инверсию плоскости относительно удаляемой вершины графа (процедура никак не влияющая на условие задачки) и становится можно. но через формулу эйлера конечно красивей ) я про нее сразу подумал но что то протормозил связать кол-во граней и ребер )
#39
by SUA
именно оно кхм... это как? есть еще интересный плоский граф каждая из 6ти вершин связана ровно с 4мя другими * * * * * * (внешний треугольник, внутренний, и каждая вершина внешнего соединена с 2мя ближайшими внутреннего)
#40
by Torquader
методом переноса диагонали в четырёхугольнике (а это не влияет на количество рёбер) приводится к классическому случаю "со слоном".
#42
by Кириллка
+41 ыть, не учел "Каждая пара различных вершин соединена между собой не более чем одним ребром".
Тэги: Математика и алгоритмы
Ответить:
Комментарии доступны только авторизированным пользователям
Похожие вопросы 1С
В этой группе 1С
- в RDP не работают Буфер обмена ?
- Почему-то не работает раскладка клвиатуры в 1С 8.0...
- ЗИК Ошибка в дате рождения. Как изменить начисление в ПФР не трогая прошлые периоды?
- Расчет пени в УТ
- HELP Ошибка при обмене (((( ВыгрузитьИзмененияДанныхДляУзла
- Как наложить условие на строкоый реквизит неограниченной длины
- Определение внутреннего идентификатора в 1С
- Проектирование Регистра сведений
- Склонение месяца
- Как отразить в УПП начисление для расчета среднего, не перенося всех документов?
- СКД: Расшифровка в СКД
- Где взять файл правил обмена для стандартной УПП.
- Нули посля запятой в числе при выводе макета.
- дополнительные отпуска - УПП
- Одинаковые позиции в номенклатуре
- Во время реструктуризации ИБ вылетел из конфигуратора...
- Как в форме списка документа добавить флажок с возможностью изменять его значение
- НДСПоПартиямЗапасов -- кто-нибудь разбирался с суммами, которые туда конфа пишет?
- Я новичок, помогите!
- Как узнать значение предыдущей и последующей строки в табличном поле?