Question

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

Answer 1

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

В этом случае количество ребёр будет равно n*m

В нашей задаче известно, что граф содержит 100 вершин.

Пусть количество вершин в одной доле равно n. Тогда в другой доле будет 100 - n вершин.

Количество ребёр тогда равно n(100 - n)

n(100 - n) = -n² + 100n

График полученного выражения - парабола, ветви которой направлены вниз (т.к. коэффициент при n² меньше 0)

Следовательно наибольшее значения будет в вершине данной параболы

$n = \frac{-100}{2 \times (-1)} = \frac{100}{2} = 50$

Тогда количество рёбер равно 50(100 - 50) = 2500

Answer 2

Maximum Number of Edges in a Bipartite Graph with 100 Vertices

In a bipartite graph with \( n \) vertices, the maximum number of edges can be achieved when all vertices in one partition are connected to all vertices in the other partition. This can be calculated using the formula:

Maximum number of edges = \( m \times n \)

Where: - \( m \) = number of vertices in the first partition - \( n \) = number of vertices in the second partition

In this case, with 100 vertices, the maximum number of edges in a bipartite graph can be calculated as:

Maximum number of edges = \( m \times n = 50 \times 50 = 2500 \) Therefore, the maximum number of edges in a bipartite graph with 100 vertices is 2500.