2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Где ошибка?
Сообщение29.03.2017, 19:50 
Заслуженный участник


26/05/14
981
Да.

 Профиль  
                  
 
 Re: Где ошибка?
Сообщение29.03.2017, 20:37 
Аватара пользователя


15/11/15
1297
Москва
Можете дать идею, как вывести ту формулу? Если все точки принадлежат выпуклой оболочке, то вывод очевиден, а на общий случай нет даже мыслей.

 Профиль  
                  
 
 Re: Где ошибка?
Сообщение29.03.2017, 20:51 
Заслуженный участник


04/05/09
4582
Посмотрите на сумму углов всех треугольников и число сторон всех треугольников.
Кстати, количество рёбер лучше записать как $2N+M-3$, где $M$ - число внутренних точек, и тогда видно, что выигрыш зависит только от количества внутренних точек.

 Профиль  
                  
 
 Re: Где ошибка?
Сообщение29.03.2017, 21:04 
Заслуженный участник


26/05/14
981
Работает индукция по количеству точек внутри выпуклой оболочки $M = N - K$. Из произвольной триангуляции удаляем одну внутреннюю точку и все инцидентные рёбра. Получившуюся дырку (многоугольник) триангулируем. Для новой триангуляции формула верна по индукционному предположению. Обозначим степень удаляемой вершины - $v$. Тогда $N$ стало меньше на один. Рёбер выкинули $v$ и добавили $v - 2$ (триангуляция). Подведите баланс и проверьте что формула верна для исходной триангуляции.

Присмотритесь к идее venco. Она изящнее.

 Профиль  
                  
 
 Re: Где ошибка?
Сообщение29.03.2017, 22:08 
Аватара пользователя


15/11/15
1297
Москва
А каждые три точки обязательно не лежат на одной прямой? Иначе число ребер уменьшается

 Профиль  
                  
 
 Re: Где ошибка?
Сообщение29.03.2017, 22:23 
Заслуженный участник


26/05/14
981
Число рёбер не зависит от этого условия. Но ребру запрещено проходить через другую точку.

 Профиль  
                  
 
 Re: Где ошибка?
Сообщение29.03.2017, 22:46 
Аватара пользователя


15/11/15
1297
Москва
Я кажется нашел решение и,по-моему, оно получилось слишком простым. Будем доказывать формулу $2N+M-3$.

Возьмем некоторую произвольную вершину внутри выпуклой оболочки графа и проведем к ней ребра из "выпуклых" вершин(ну, и соединим ребрами "выпуклые" вершины, чтобы получилась выпуклая оболочка). Всего получится $2(N-M)$ ребер. Так как вершины находятся в общем положении, то все оставшиеся вершины будут находится внутри получившихся треугольников. При этом, может получится так, что несколько вершин лежат внутри одного треугольника. Тогда соединяем произвольную висячую вершину с вершинами этого треугольника. Если остались такие треугольники, в которых несколько висячих вершин, то повторяем эту операцию, пока не будут соединены все висячие вершины. Вся эта операция будет завершена через $M-1$ шагов(для $M-1$ оставшихся висячих вершин после первого шага доказательства). Все эти операции сохраняют планарность графа и увеличивают количество ребер на $3$. Отсюда следует, что общее число ребер равно: $2(N-M)+3(M-1)=2N+M-3$.

Возможно это то, что говорил slavav, но я полный ноль в теории графов, поэтому не смог его понять. И, скорее всего, мое доказательство не строгое.

 Профиль  
                  
 
 Re: Где ошибка?
Сообщение30.03.2017, 00:00 
Заслуженный участник


26/05/14
981
Вы доказали формулу для специального вида триангуляции. Индукция или рассуждения про углы треугольников работают для любых триангуляций.

 Профиль  
                  
 
 Re: Где ошибка?
Сообщение30.03.2017, 10:30 
Аватара пользователя


15/11/15
1297
Москва
Я доказал для случая, когда $N$ вершин лежат снаружи, а $M$ вершин лежат внутри. Разве это не общий случай?

 Профиль  
                  
 
 Re: Где ошибка?
Сообщение30.03.2017, 10:52 
Заслуженный участник


26/05/14
981
Нет. Вы доказали формулу для триангуляций специального вида. Я говорю о фразах "Возьмем некоторую произвольную вершину внутри выпуклой оболочки графа и проведем к ней ребра из "выпуклых" вершин..." и "Тогда соединяем произвольную висячую вершину с вершинами этого треугольника.". Что если игроки построят другую триангуляцию?

Общая идея в том чтобы не добавлять новые элементы в существующую конфигурацию (получая специальную триангуляцию), а в том чтобы удалять элементы из произвольной триангуляции. Формула, конечно, будет одной и той же, но доказательство станет применимо к любым триангуляциям.

-- 30.03.2017, 11:31 --

Пусть дана триангуляция множества $S$ с параметрами $N = K + M$, $N = \left\lvert S\right\rvert$, $K = \left\lvert\partial Ch(S)\right\rvert$, $M = \left\lvert Int(Ch(S))\right\rvert$. Проведём индукцию по $M$.
База $M = 0$:
Если все точки $S$ лежат на границе выпуклой оболочки, то любая триангуляция $S$ сводится к триангуляции многоугольника с $K$ вершинами. У неё $K-3 диагоналей и K сторон. Суммарное число рёбер $E(K, M) = K - 3 + K = 2K - 3 = 2K + 3M - 3$.
Шаг индукции $M > 0$:
Индукционное предположение: $E(K, M - 1) = 2K + 3(M - 1) - 3$.
Выберем любую точку из внутренности выпуклой оболочки. Обозначим её степень $v$. Удалим её и $v$ рёбер в неё входящих. После удаления в графе образуется многоугольник с $v$ вершинами. Триангулируем его. Для этого надо будет добавить $v - 3$ рёбер. Уравнение для числа рёбер в триангуляциях до и после удаления вершины:
$E(K, M) - v + (v - 3) = E(K, M - 1)$. Тогда
$E(K, M) = E(K, M - 1) + 3 = 2K + 3(M - 1) - 3 + 3 = 2K + 3M - 3$.
Формула доказана:
$E(K, M) = 2K + 3M - 3$
Заменим обозначения на более привычные:
$E(K, M) = 2K + 3M - 3 = 2K + 3(N - K) - 3 = 3N - K - 3 = E'(N, K)$

 Профиль  
                  
 
 Re: Где ошибка?
Сообщение30.03.2017, 11:51 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Rusit8800 в сообщении #1204414 писал(а):
Двое по очереди соединяют их отрезками. Отрезки могут выходить из одной точки, но не должны пересекаться.
А "отрезки" обязательно прямолинейные? Что-то не соображу, существенно это или нет.

 Профиль  
                  
 
 Re: Где ошибка?
Сообщение30.03.2017, 12:24 
Заслуженный участник


26/05/14
981
Кажется, что не существенно. Думаю, что любой планарный граф можно гомеоморфно перевести в прямолиненый.

 Профиль  
                  
 
 Re: Где ошибка?
Сообщение30.03.2017, 14:18 
Аватара пользователя


15/11/15
1297
Москва
slavav в сообщении #1204809 писал(а):
Общая идея в том чтобы не добавлять новые элементы в существующую конфигурацию (получая специальную триангуляцию), а в том чтобы удалять элементы из произвольной триангуляции

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

-- 30.03.2017, 15:19 --

slavav в сообщении #1204809 писал(а):
Что если игроки построят другую триангуляцию?

Кол-во ребер не изменится

-- 30.03.2017, 15:27 --

Доказательства вроде по сложности не отличаются, но не понятно, почему ваш стиль правильнее.

 Профиль  
                  
 
 Re: Где ошибка?
Сообщение30.03.2017, 14:51 
Заслуженный участник


26/05/14
981
Оба доказательства проверяют некоторый инвариант (каждая новая внутренняя вершина добавляет три ребра).

Rusit8800 в сообщении #1204850 писал(а):
Все равно не понятно, почему моя конфигурация специальная. Можно же добавлением произвольного числа вершин привести ее к общей.

Нет, нельзя. Вы не можете создать эту триангуляцию:
Изображение

К вашему доказательству надо добавить доказательство того что вы берётесь сконструировать любую триангуляцию.

 Профиль  
                  
 
 Re: Где ошибка?
Сообщение30.03.2017, 15:13 
Аватара пользователя


15/11/15
1297
Москва
Можно удалить ребро $AC$, добавить $BE$. Количество ребер не изменится, а общее количество можно считать по той формуле.

-- 30.03.2017, 16:13 --

Хотя надо доказать, что количество ребер не изменяется.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 38 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: epros


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group