Где ошибка?

[slavav]

Да.

[Rusit8800]

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

[venco]

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

[slavav]

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

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

[Rusit8800]

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

[slavav]

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

[Rusit8800]

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

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

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

[slavav]

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

[Rusit8800]

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

[slavav]

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

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

-- 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)$

[Someone]

Rusit8800 в сообщении #1204414 писал(а):

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

А "отрезки" обязательно прямолинейные? Что-то не соображу, существенно это или нет.

[slavav]

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

[Rusit8800]

slavav в сообщении #1204809 писал(а):

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

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

-- 30.03.2017, 15:19 --

slavav в сообщении #1204809 писал(а):

Что если игроки построят другую триангуляцию?

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

-- 30.03.2017, 15:27 --

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

[slavav]

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

Rusit8800 в сообщении #1204850 писал(а):

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

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


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

[Rusit8800]

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

-- 30.03.2017, 16:13 --

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