Как определить максимальное число ребер в двудольном графе?

Максимальное количество рёбер в двудольном графе достигается, когда каждая вершина одной доли соединена со всеми вершинами другой. dzen.ru www.euroki.org

Для двудольного графа с n вершинами, разделёнными на две доли размерами k и n-k, максимальное число рёбер равно произведению размеров долей: k |* (n - k). www.euroki.org

Чтобы максимизировать количество рёбер, значение k должно быть равно или как можно ближе к n/2. www.euroki.org

Например, если нужно найти максимальное число рёбер в двудольном графе на 12 вершинах, то можно разделить их пополам: по 6 вершин в каждой доле, и из 6 вершин будет исходить 6 рёбер: 6 |* 6 = 36. dzen.ru