В двудольном графе 2п вершин, но нет кратных рёбер. Какое наибольшее количество рёбер может быть в таком графе?
от

1 Ответ

Дано:

Количество вершин в двудольном графе = 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.
от