Question

Какое наибольшее число рёбер может быть в двудольном графе на 93 вершинах?очень срочнооо помогите умоляю

Answer 1

Пусть обе доли полностью соединены друг с другом. Рассмотрим случай, когда в одной доле 47 вершин, а в другой - 46:

(47 * 46 + 46 * 45) : 2 = 46 * 46 = 2116 - число "отсутствующих" рёбер.

Логично, что это число должно быть как можно меньше. Пусть для меньшего числа отсутствующих рёбер в одной доле должно быть 47+k рёбер, тогда в другой доле будет 46-k рёбер:

((47+k) * (46+k) + (46-k) * (45-k)) = (2162 + 93k + k² + 2070 - 91k + k²) : 2 = 2116 + k + k²

Это больше первого результата, значит, предположение неверно.

Всего в полном графе на 93 вершины будет 93 * 92 : 2 (=4278) рёбер, у нашего графа отсутствует как минимум 2116 рёбер.

4278 - 2116 = 2162 ребра.

Ответ: 2162 ребра.

Answer 2

Для нахождения наибольшего числа ребер в двудольном графе на 93 вершинах необходимо знать, какое количество вершин находится в каждой доле. Предположим, что количество вершин в первой доле равно n, а количество вершин во второй доле равно m. Тогда общее количество вершин равно n + m = 93.

Максимальное количество ребер в двудольном графе достигается, когда каждая вершина из первой доли соединена со всеми вершинами второй доли. Таким образом, общее количество ребер равно n × m. Но для того, чтобы граф был двудольным, нужно убедиться, что нет ребер, соединяющих вершины внутри одной доли.

Если мы распределим вершины равномерно между двумя долями, то максимальное количество ребер будет достигаться, когда количество вершин в каждой доле будет максимально близко. Таким образом, мы можем выбрать n = m = 46 (или n = 47 и m = 46) и получить максимальное количество ребер:

n × m = 46 × 46 = 2116

Таким образом, в двудольном графе на 93 вершинах максимальное количество ребер равно 2116.