Максимальное количество ребер у двудольного графа

[Gefrey__]

Здравствуйте! Нужно найти максимальное количество ребер у двудольного графа. Я рассуждаю следующим образом:
Пусть $\mathbb{G}(\mathbb{V},\mathbb{E})$ - граф, где $\mathbb{V}$ - конечное множество всех вершин, а $\mathbb{E}$ - множество всех неупорядоченных пар. $|\mathbb{V}| = n $. Пусть одна из долей имеет $m$ вершин, тогда другая имеет $n-m$ вершин. Т. к. в графе пара вершин может соединяться только одним ребром и в графе нет петель, то очевидно, что количество ребер равно $m\cdot(n-m)$. Возьмём производную по m и приравняем к нулю. Получается $n = 2m$ или $m = \frac{n}{2}$. Подставим теперь это в формулу количества рёбер и получим ответ $\frac{n^2}{4}$.

Возникает вопрос: а если $n$ нечётно? То есть не представляется в виде $n = 2m$. На ум приходит положить $n = 2m + 1$, но будет ли это максимумом? И если да, то почему?

[Sender]

А в каких точках значение функции $m\cdot(n-m)$ может превысить значение в точке $n=2m+1$?

[Gefrey__]

Sender
$n = 2m$.

[SiberianSemion]

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

[Sender]

Gefrey__ в сообщении #1413379 писал(а):

$n = 2m$.

Это единственная точка? Что насчёт $n=2m+\frac{1}{2}$, например? Вообще, раз $n$ уже задано, наверное, лучше рассуждать о значениях $m$ в зависимости от $n$.

[Gefrey__]

Sender
Кажется понял, что вы хотели сказать. Т.к. $n = 2m$ экстремум, то если $n$ нечётно, максимум нужно искать в окрестности этой точки. Т. к. я оперирую целыми числами, у нас появляется два кандидата $n = 2m - 1$ и $n = 2m + 1$. Легко убеждаемся, что оба варианта ведут нас к одному и тому же ответу.

-- 03.09.2019, 14:50 --

SiberianSemion
Спасибо за вариант, но меня интересует более формальное решение.

[Sender]

Забудьте пока про целые числа, вы квадратное неравенство решить можете?

[arseniiv]

Gefrey__
Тут же обычный поиск наибольшего значения (непрерывной и дифференцируемой функции) на отрезке: надо проверять границы и все экстремумы внутри. Раз в $[0; n/2]$ экстремумов внутри нет вообще в любом случае, даже в чётном, функция на отрезке монотонна, и на его целочисленных точках $[0; n/2]\cap\mathbb Z$ она, разумеется, тоже будет монотонна. Останется заметить, что отображение $m\mapsto n-m$ меняет местами половины $[0; n]$ и никак не сказывается на значениях $m(n-m)$.

[Gefrey__]

Sender
Хорошо, забываю. Тогда отвечаю на первый вопрос: значение функции $m \cdot (n-m)$ может превысить значение в точке $n = 2m + 1$ в точках $m = \frac{n-x}{2}$ (как вы верно заметили, правильно выражать $m$ через $n$), где $|x| < 1$.

-- 03.09.2019, 15:37 --

arseniiv
Спасибо за ответ! Это как раз то, к чему я пытался придти.