Дано:
Количество вершин в двудольном графе = 2p.
Найти:
Наибольшее количество рёбер в таком графе.
Решение:
В двудольном графе с двумя множествами A и B, количество рёбер ограничено произведением количества вершин в этих множествах. Обозначим количество вершин в A как a, а в B как b. Тогда a + b = 2p.
Наибольшее количество рёбер в двудольном графе равно a * b.
Для максимизации a * b, лучше всего взять a = p и b = p. Тогда:
a * b = p * p = p^2.
Следовательно, максимальное количество рёбер = p^2.
Ответ:
Наибольшее количество рёбер в двудольном графе с 2p вершинами равно p^2.