Question

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

Answer 1

В двудольном графе на 101 вершине наибольшее количество рёбер может быть достигнуто, когда каждая вершина из одной доли соединена со всеми вершинами другой доли. По определению двудольного графа, вершины разделены на две доли, и рёбра могут идти только между вершинами разных долей.

Предположим, что в первой доле у нас 50 вершин, а во второй 51 вершина. Каждая вершина из первой доли соединена со всеми 51 вершиной из второй доли, тогда общее число рёбер будет равно:

Число рёбер = Количество вершин в первой доле * Количество вершин во второй доле Число рёбер = 50 * 51 = 2550

Таким образом, наибольшее количество рёбер в двудольном графе на 101 вершине составляет 2550.