Question

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

Answer 1

2500 ребер верный ответ)

Answer 2

Двудольный граф на 100 вершинах может иметь наибольшее количество ребер, если каждая вершина в одной доле соединена со всеми вершинами в другой доле. Пусть у нас есть доли A и B, каждая из которых содержит по 50 вершин. Тогда каждая вершина из доли A будет соединена со всеми вершинами из доли B. Таким образом, количество ребер будет равно количеству вершин в доле A, умноженному на количество вершин в доле B. В данном случае это будет 50 * 50 = 2500 ребер.

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