М416. О максимальном количестве ребер в таком графе, что никакие три ребра не создают треугольник

Задача из журнала «Квант»(1977 №8)

Условие

На плоскости даны $n$ точек $A_{1},\ldots,A_{n}$, никакие три из которых не лежат на одной прямой. Какое наибольшее число отрезков с концами в этих точках можно провести так, чтобы не получилось ни одного треугольника с вершинами в этих точках?

Решение

Проведем максимальное число отрезков с концами в точках $A_{1},\ldots,A_{n}$. Получим некоторый граф с вершинами в этих точках. Отрезки с концами в вершинах графа будем называть ребрами графа. Оценим число ребер в нашем графе.

Назовем степенью вершины в графе число выходящих из неё ребер. Пусть $k$ — максимальная степень вершины в графе, и пусть некоторая вершина $A_{i}$ соединена с $k$ вершинами $A_{j_{1}},\ldots,A_{j_{k}}$ графа (рисунок 1).

kvant1

Тогда степень любой вершины из множества $\left \{ A_{j_{1}},\ldots,A_{j_{k}} \right \}$ не превосходит $n-k$ ($n$ — число вершин графа), поскольку любые вершины из этого множества уже не могут быть соединены ребром (в нашем графе никакие три ребра не образуют треугольника — с вершинами в вершинах графа). Так как $k$ — максимальная степень вершины в графе, степень каждой из оставшихся $n-k$ вершин не превосходит $k$. Поэтому сумма степеней всех вершин графа не превосходит $$k \left(n-k \right )+ \left (n-k \right) k=2k \left (n-k\right).$$ Но легко видеть, что сумма степеней всех вершин графа равна удвоенному количеству его ребер. Следовательно, количеств ребер графа не больше $$k\left(n-k\right)\leqslant\left(\frac{k+(n-k)}{2}\right)^{2}=\frac{n^{2}}{4}.$$ Чтобы получить данное соотношение, мы воспользовались теоремами о среднем арифметическом и среднем геометрическом. Учитывая, что количество ребер графа — число целое, мы получаем, что ребер в нашем графе не больше чем $\left [ \frac{n^{2}}{4}\right]$ (здесь $\left [ x \right]$ означает целую часть числа $x$ — наибольшее целое число, не превосходящее $x$).

Укажем теперь способ построения графа без треугольников с $n$ вершинами, число ребер которого в точности равно $\left [ \frac{n^{2}}{4}\right]$.

Разобьем множество точек $A_{1},\ldots,A_{n}$ на два: $\left [ \frac{n}{2} \right ]$ точек в одном множестве и $n — \left [ \frac{n}{2} \right ]$ — в другом. Соединив все точки точки первого множества с точками второго (как на рисунке 2, где $n=5$), мы получим граф, у которого не будет ни одного треугольника с вершинами в точках $A_{1},\ldots,A_{n}$.

kvant2

Число ребер в этом графе, очевидно, равно $\left [ \frac{n}{2} \right ]\left(n-\left [ \frac{n}{2} \right ]\right)$. Если $n$ — четное, то $$\left [ \frac{n}{2} \right ]\left (n-\left [ \frac{n}{2} \right ]\right)=\frac{n^{2}}{4}=\left [ \frac{n^{2}}{4} \right ].$$Если $n$ — нечетное, то $\left [ \frac{n}{2} \right ]\left(n-\left [ \frac{n}{2} \right ]\right)=$ $\frac{n-1}{2}\left(n-\frac{n-1}{2}\right)=$ $\frac{n^{2}-1}{4}=$ $\left [ \frac{n^{2}}{4}\right].$ Что и требовалось доказать.

Итак, ответ в задаче: максимальное число отрезков равно $\left [ \frac{n^{2}}{4}\right]$(этот результат в теории графов называют теоремой Турана).

Вычисление радиуса сходимости. Формула Коши — Адамара

Пусть дан степенной ряд вида $\sum\limits_{n=0}^{\infty}c_{n}z^n$ с радиусом сходимости $R$, где $c_n$,$z^{n}\in \mathbb{C}$. Тогда для этого ряда справедлива следующая теорема:

Теорема о вычислении радиуса сходимости степенного ряда

  1. Если существует конечный или бесконечный предел$\lim\limits_{n\to\infty}\sqrt[n]{\left | c_n \right |}$, то $$\frac{1}{R}=\lim\limits_{n\to\infty}\sqrt[n]{\left | c_n \right |}. (1)$$
  2. Если существует конечный или бесконечный предел $\lim\limits_{n \to\infty} \left | \frac{c_{n}}{c_{n+1}} \right |$, то $$R=\lim\limits_{n \to\infty} \left | \frac{c_{n}}{c_{n+1}} \right | .(2)$$

Доказательство:

  1. Докажем формулу (1). Пусть $\lim\limits_{n\to\infty}\sqrt[n]{\left | c_n \right |} = \rho$.
    • Если $0<\rho<+\infty$, и $z_0$ — произвольная точка из круга $K=\left \{z:\left |z\right | < \frac{1}{\rho}\right \}$, то $$\lim\limits_{n\to\infty}\sqrt[n]{\left | c_{n} \cdot z_{0}^{n} \right |} = \left | z_{0} \right | \cdot \lim\limits_{n\to\infty}\sqrt[n]{\left |c_{n} \right |} = \left |z_{0} \right | \cdot \rho < 1.$$ По признаку Коши сходимости ряда, ряд сходится в точке $z_{0}$. В силу того, что точка $z_{0}$ — произвольная точка круга $K$, исходный ряд сходится в $K$.
      Предположим, что точка $z_{m}$ не принадлежит кругу $K$, то есть $\left |z_{m} \right | > \frac{1}{\rho}$.Тогда $$\lim\limits_{n\to\infty}\sqrt[n]{\left | c_{n} \cdot z_{m}^{n} \right |} = \left | z_{m} \right | \cdot \lim\limits_{n\to\infty}\sqrt[n]{\left |c_{n} \right |} = \left |z_{m} \right | \cdot \rho > 1.$$ По признаку Коши, ряд расходится.
      Значит, ряд сходится в круге $K$, и расходится вне его замыкания. Это значит, что $\frac{1}{\rho}$ — радиус сходимости исходного ряда.
      Круг сходимости $K$ c нанесенными точками $z_{0}$ и $z_{m}$ показать
    • Если $\rho = 0$, то $\forall z \in \mathbb{C}$ выполняется следующее: $$\lim\limits_{n\to\infty}\sqrt[n]{\left | c_{n} \cdot z^{n} \right |} = \left | z \right | \cdot \rho = 0 .$$ По признаку Коши ряд сходится в точке $z$. В силу произвольности точки $z$ ряд сходится на всей комплексной плоскости. И это значит, что радиус сходимости ряда $R=+\infty$.
    • Пусть $\rho = +\infty$. Тогда $\forall z \neq 0$ $$\lim\limits_{n\to\infty}\sqrt[n]{\left | c_{n} \cdot z^{n} \right |} = \left | z \right | \cdot \rho = +\infty. $$ По признаку Коши, ряд расходится в точке $z$. Отсюда выходит, что радиус сходимости $R = 0$.
  2. Доказательство (2) по сути идентично доказательству (1). Различие в том, что будет использоваться признак Даламбера сходимости ряда. Для этого выполним следующие преобразования: $$ R=\lim\limits_{n \to\infty} \left | \frac{c_{n}}{c_{n+1}} \right | = \frac{\lim\limits_{n \to \infty}\left | c_{n} \right |}{\lim\limits_{n \to \infty}\left | c_{n+1} \right |} = \frac{1}{(\frac{\lim\limits_{n \to \infty}\left | c_{n+1} \right |}{\lim\limits_{n \to \infty}\left | c_{n} \right |})} = \frac{1}{\lim\limits_{n \to\infty} \left | \frac{c_{n+1}}{c_{n}} \right |}.$$
    Пусть $\lim\limits_{n \to \infty}\left | \frac{c_{n+1}}{c_{n}} \right | = \rho$

    • Если $0<\rho<+\infty$, и $z_0$ — произвольная точка из круга $K=\left \{z:\left |z\right | < \frac{1}{\rho}\right \}$, то $z_0$ так же по модулю меньше, чем $\frac{1}{\rho}$. Отсюда следует, что $$\lim\limits_{n \to \infty}\left | \frac{c_{n+1} \cdot z_{0}^{n+1}}{c_{n} \cdot z_{0}^{n}}\right |=\left | z \right | \cdot \lim\limits_{n \to \infty}\left | \frac{c_{n+1}}{c_{n}}\right |=\left |z \right | \cdot \rho < 1.$$ По признаку Даламбера сходимости ряда, ряд сходится в точке $z_{0}$. В силу того, что точка $z_{0}$ — произвольная точка круга $K$, исходный ряд сходится в $K$.
      Предположим, что точка $z_{m}$ не принадлежит замыканию круга $K$, то есть $\left |z_{m} \right | > \frac{1}{\rho}$. Тогда $$\lim\limits_{n \to \infty}\left | \frac{c_{n+1} \cdot z_{0}^{n+1}}{c_{n} \cdot z_{0}^{n}}\right |=\left | z \right | \cdot \lim\limits_{n \to \infty}\left | \frac{c_{n+1}}{c_{n}}\right |=\left |z \right | \cdot \rho > 1.$$ По признаку Даламбера, ряд расходится.
      Значит, ряд сходится в круге $K$, и расходится вне него. А это значит, что $\frac{1}{\rho}$ — радиус сходимости исходного ряда.
    • Пусть $\rho = 0$, то $\forall z \in \mathbb{C}$ выполняется следующее:$$\lim\limits_{n \to \infty}\left | \frac{c_{n+1} \cdot z_{0}^{n+1}}{c_{n} \cdot z_{0}^{n}}\right |=\left |z \right | \cdot \rho = 0. $$ По признаку Даламбера, ряд сходится в точке $z$. В силу произвольности $z$ ряд сходится на всей комплексной плоскости. И это значит, что радиус сходимости ряда $R=+\infty$.
    • Пусть $\rho = +\infty$. Тогда $\forall z \neq 0$ $$\lim\limits_{n \to \infty}\left | \frac{c_{n+1} \cdot z_{0}^{n+1}}{c_{n} \cdot z_{0}^{n}}\right |=\left |z \right | \cdot \rho = +\infty. $$ По признаку Даламбера, ряд расходится в точке $z$. Отсюда выходит, что радиус сходимости $R = 0$.
Пример 1 показать

Пример 2 показать

Замечание

Пределы в формулах (1) и (2) могут не существовать. Однако существует универсальная формула для вычисления радиуса сходимости.

Теорема

Радиус сходимости$R$ степенного ряда $\sum\limits_{n=0}^{\infty}c_{n}z^n$ высчитывается по формуле:
$$R = \frac{1}{\varlimsup\limits_{n \to \infty}\sqrt[n]{\left | c_{n} \right |}},$$
где $\frac{1}{0}=+\infty$ и $\frac{1}{+\infty}=0.$

Доказательство

Доказательство данной теоремы основано на применении обобщенного признака Коши: $$\varlimsup\limits_{n \to \infty}\sqrt[n]{\left | c_{n} \cdot z^{n} \right |} = \left | z \right | \cdot \varlimsup\limits_{n \to \infty}\sqrt[n]{\left |c_{n} \right |}. $$
Предположим, что ряд сходится в точке $z_{0}$, тогда из обобщенного признака Коши сходимости числового ряда с неотрицательными членами следует, что $\left | z_{0} \right | \cdot \varlimsup\limits_{n \to \infty}\sqrt[n]{\left |c_{n} \right |}<1$. Отсюда получаем, что $$\left | z_{0} \right | < \frac{1}{\varlimsup\limits_{n \to \infty}\sqrt[n]{\left | c_{n} \right |}}.$$
Пусть ряд расходится в точке $z_{m}$. Тогда $\left | z_{m} \right | \cdot \varlimsup\limits_{n \to \infty}\sqrt[n]{\left |c_{n} \right |}>1$. Отсюда $$\left | z_{m} \right | > \frac{1}{\varlimsup\limits_{n \to \infty}\sqrt[n]{\left | c_{n} \right |}}.$$
То есть, если $z$ по модулю меньше чем $\frac{1}{\varlimsup\limits_{n \to \infty}\sqrt[n]{\left | c_{n} \right |}}$, то ряд сходится в данной точке, а если $z$ по модулю больше, то ряд в данной точке расходится. Из определения радиуса сходимости следует, что
$$R=\frac{1}{\varlimsup\limits_{n \to \infty}\sqrt[n]{\left | c_{n} \right |}}.$$

Список использованной литературы:

Вычисление радиуса сходимости, формула Коши-Адамара

Тест по материалу данной статьи


Таблица лучших: Вычисление радиуса сходимости, формула Коши-Адамара

максимум из 7 баллов
Место Имя Записано Баллы Результат
Таблица загружается
Нет данных

Критерий потенциальности поля

Теорема

Для того чтобы дифференцируемое в области $G$ поле было потенциальным необходимо, а в случае односвязной области и достаточно, чтобы выполнялось условие
$$\frac{\partial P(x,y)}{\partial y}=\frac{\partial Q(x,y)}{\partial x}.(1)$$

Доказательство:

Необходимость:

Пусть поле $(P(x, y), Q(x, y))$ непрерывно дифференцируемо и потенциально. Тогда
$$P(x, y) = \frac{\partial U(x,y))}{\partial x},\quad Q(x, y) = \frac{\partial U(x,y))}{\partial y},$$ откуда
$$\frac{\partial Q(x,y))}{\partial x}=\frac{\partial^2 U(x,y)}{\partial x\,\partial y},\quad
\frac{\partial P(x,y))}{\partial y}=\frac{\partial^2 U(x,y)}{\partial y\,\partial x}.$$

Так как производные $\frac{\partial P}{\partial y}$ и $\frac{\partial Q}{\partial x}$ непрерывны, то смешанные производные $U_{x,y},\,U_{y,x}$ также непрерывны, а следовательно, равны. Условие (1) выполнено в области $G$.

Достаточность:

Пусть поле $(P, Q)$ задано в односвязной области $G \subset \mathbb{R}^{2}$ и выполнено условие (1).

Возьмем произвольную простую замкнутую ломанную $L \subset G$. Так как область $G$ односвязна, то ограничиваемая ломанной $L$ область $\Omega \subset G$ и к ней применима формула Грина:
$${ \underset { L }{ \int } \left(P\,dx+Q\,dy\right)}={ \underset { \Omega }{ \iint } (\frac{\partial Q}{\partial x} — \frac{\partial P}{\partial y})dx\,dy}=0.(2)$$

Таким образом, интеграл (2) равен нулю для любой простой замкнутой ломанной $L$.

Покажем, что интеграл (2) равен нулю для любой простой замкнутой ломанной (даже имеющей точки самопересечения).

Для трехзвенной ломанной интеграл (2) всегда равен нулю, если эта ломанная замкнута. Если три её вершины не лежат на одной прямой, то трехзвенная ломанная будет простой и по доказанному интеграл (2) равен нулю. Если же все три вершины лежат на одной прямой, то и в этом случае интеграл равен нулю(иллюстрация 1).
Иллюстрация 1
Докажем, что интеграл (2) равен нулю для любой $n$-звенной замкнутой ломанной индукцией по числу звеньев.

Пусть выполнено условие (1) и интеграл (2) равен нулю по любой замкнутой ломанной, число звеньев которой меньше, чем $n$. Покажем тогда, что он равен нулю и для любой $n$-звенной ломанной. Если ломанная $L(A_{1},A_{2},\cdots,A_{n},A_{1})$ простая, то это уже доказано. Пусть у $L$ есть точки самопересечения. Предположим, что два звена, $A_{1}A_{2}$ и $A_{k}A_{k+1}$, пересекаются. Тогда либо они пересекаются в единственной точке $B$(иллюстрация 1), либо эти два звена пересекаются по целому отрезку. В этом случае точки $A_{1},\,A_{2},\,A_{k},\,A_{k+1}$ лежат на одной прямой(иллюстрация 2).

Иллюстрация 2
Рассмотрим случай, когда звенья пересекаются в единственной точке. За последующими рассуждениями проще следить по иллюстрации 2. В случаях 1 и 2 ломанная $L$ будет объединением замкнутых ломанных $L_{1}(B, A_{k+1},\cdots,A_{n},A_{1},B)$ и $L_{2}(B, A_{2},\cdots,A_{k},B)$. Количество звеньев $L_{1}$ и $L_{2}$ меньше $n$. По предположению индукции интеграл (2) по каждой из этих ломанных равен нулю. Следовательно, он равен нулю и по их объединению ломанной $L$.

Аналогично рассматривается и второй случай, когда точки $A_{1},A_{2},A_{k},A_{k+1}$ лежат на одной прямой и отрезки $A_{1}A_{2}$ и $A_{k}A_{k+1}$ пересекаются. Без ограничения общности можно считать, что точка $A_{k}$ лежит на отрезке $A_{1}A_{2}$. Тогда $L$ есть объединение замкнутых ломанных $L_{1}(A_{k}, A_{k+1},\cdots,A_{n},A_{1}, A_{k})$ и $L_{2}(A_{k},A_{2},\cdots,A_{k+1},A_{k})$, имеющих меньше, чем $n$ звеньев. Интеграл (2) по $L_{1}$ и $L_{2}$ равен нулю. Следовательно, он равен нулю и по ломанной $L$.

Так как интеграл (2) равен нулю на любой замкнутой ломанной $L\subset G$, то в силу теоремы об условиях независимости величины криволинейного интеграла второго рода от пути интегрирования, поле $(P,Q)$ будет потенциальным. Что и требовалось доказать!

Пример 1 показать

Пример 2 показать

Пример 3 показать

Список использованной литературы:

Критерий потенциальности поля

Предлагаем пройти тест на закрепление знаний по данной статье


Таблица лучших: Критерий потенциальности поля

максимум из 8 баллов
Место Имя Записано Баллы Результат
Таблица загружается
Нет данных