Плоский граф #411411


#0 by Ненавижу 1С
На плоскости задан граф с N вершинами. Каждая пара различных вершин соединена между собой не более чем одним ребром (замкнутая кривая). При этом ребра на плоскости не пересекаются. Есть ли формула, определяющая по числу вершин N максимально возможное число таких ребер?
#1 by mikecool
я отсель скачал себе теорию, щас начал читать
#2 by Ненавижу 1С
Мое решение: N*(N-1)/2 для N<=4 3*(N-2) для N>4
#3 by Torquader
Вообще-то, максимальное число - однозначно, когда система образует набор треугольников, так как если есть фигура с большим числом углов, то её можно разбить на треугольники.
#4 by NewNick
первая строка формулы не понятно зачем нужна)
#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.
#6 by acsent
Ищи по теме "планарные графы"
#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.
#9 by acsent
прав Всякий максимальный планарный граф имеет число ребер m=3n-6, где n-число вершин
#10 by NewNick
для n=2 не пашет ((
#11 by dk
что-то не выстраивается картинка :( "Каждая пара различных вершин соединена между собой не более чем одним ребром" это типа "змея кусает свой хвост" или "не более чем одним" может и ноль означать или типа правильного выпуклого многоугольника и надо рассчитать кол-во непересекающихся ребер?
#12 by mrkorn
>> при N=4 получаем 6 интересно как можно соединить 4 точки 6ю не пересекающимися отрезками?
#13 by NewNick
представь тетраэдр на который сел слон
#14 by NewNick
+ вобшем решение задачи выглядит очень просто - надо добавить еще точку строим еще один тетраэдр на любом имеющемся на плоскости треугольнике и опять зовем слона.
#15 by mrkorn
соединять можем кривыми?
#16 by NewNick
а какая разница ?)
#17 by mrkorn
большая = ребра не могут пересекаться
#18 by acsent
С теорией графов не знаком? Ребро не отрезок, а проста пара вершин, просто для удобства изображают отрезком
#19 by NewNick
аааа типо если это прямые то пересекутся. а если не прямые то подпрыгнут над бумажкой ?)
#20 by NewNick
ап. а решение задачки кто нить выложит ? я вчера минут 30 не мог заснуть пока не решил. явно есть несколько решений. интересно сравнить просто.
#21 by Ненавижу 1С
для N<=4 каждую вершину можно соединить с каждой. Основной случай для N>4. Рассмотрим такой граф. Очевидно он разбивает плоскость на области с границами из трех ребер (иначе можно всегда добавить еще одно ребро, разбив область). Добавляем к графу еще одну вершину, она попадет в некоторую область. Соответственно, можно добавить только 3 ребра. При N=4 это 6. По индукции получаем 3*(N-2).
#22 by Joint
приведите пример одногранника
#23 by Ненавижу 1С
ты это к чему?
#24 by Joint
а прикалывались недавно
#25 by Joint
куб - шестигранник, еще есть пятигранник, 4х гранник ну и т.д.
#26 by NewNick
а теперь осталось доказать что добавление одной вершины для графа с N вершин будет и максимальным кол-вом ребер даст граф с N+1 вершиной и максимальным кол-вом ребер
#27 by NewNick
будет - вычеркнуть
#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 ребер. стало быть граф построенный методом "слона" оптимален )
#33 by Ненавижу 1С
неправда. удалите в графе на рисунке отмеченную верщину
#34 by mikadi
Классическая оценка (действительно, через максимальный плоский граф, в котором все грани - треугольники): m <= 3n-6. (m - кол-во рёбер, n - кол-во вершин).
#35 by mikadi
+ Действует, разумеется, для графов с n>=3. Для n=2 графа с треугольными гранями не существует :)
#36 by Ненавижу 1С
по формуле Эйлера имеем В-Р+Г=2, где В - число вершин, Р - ребер, Г - граней (здесь областей). Каждое ребро принадлежит 2 областям, а как сказали каждая область треугольная. Поэтому: Г=(2/3)*Р. Подставляем и получаем: Р=3*(В-2)
#37 by Ненавижу 1С
доказательство формулы Эйлера есть здесь
#38 by NewNick
если нельзя то делаем инверсию плоскости относительно удаляемой вершины графа (процедура никак не влияющая на условие задачки) и становится можно. но через формулу эйлера конечно красивей ) я про нее сразу подумал но что то протормозил связать кол-во граней и ребер )
#39 by SUA
именно оно кхм... это как? есть еще интересный плоский граф каждая из 6ти вершин связана ровно с 4мя другими             *           *   *             *  *                    * (внешний треугольник, внутренний, и каждая вершина внешнего соединена с 2мя ближайшими внутреннего)
#40 by Torquader
методом переноса диагонали в четырёхугольнике (а это не влияет на количество рёбер) приводится к классическому случаю "со слоном".
#41 by Кириллка
#42 by Кириллка
+41 ыть, не учел "Каждая пара различных вершин соединена между собой не более чем одним ребром".
Тэги: Математика и алгоритмы
Ответить:
Комментарии доступны только авторизированным пользователям

В этой группе 1С