В ориентированном графе 12 вершин, пронумерованных числами от 1 до 12, любые две его вершины соединены одним ребром. Также известно, что в нём четыре компоненты сильной связности, состоящие из трёх вершин: (1,2,3),(4,5,6),(7,8,9),(10,11,12). Сколько существует таких графов? Графы считаются разными, если найдётся пара вершин таких, что в этих графах их соединяют рёбра, направленные по-разному.

Предыдущий
вопрос Следующий
вопрос

Для решения этой задачи нам нужно рассмотреть количество способов соединения вершин графа с учетом условий задачи.

Поскольку в графе 12 вершин и любые две вершины соединены ребром, то всего возможно 12*11=132 способа соединения вершин.

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

Количество способов распределения ребер на 4 компоненты сильной связности вычисляется по формуле сочетаний:

C(132, 3) C(129, 3) C(126, 3) * C(123, 3)

где C(n, k) - биномиальный коэффициент.

Подсчитаем значение этого выражения:

C(132, 3) = 132! / (3! (132-3)!) = 132131130 / 6 = 28798
C(129, 3) = 129! / (3! (129-3)!) = 129128127 / 6 = 34137
C(126, 3) = 126! / (3! (126-3)!) = 126125124 / 6 = 32850
C(123, 3) = 123! / (3! (123-3)!) = 123122121 / 6 = 243336

Теперь вычислим итоговый ответ:

287980 341376 328500 * 243336 = 6419702202320000

Итак, число существующих графов, удовлетворяющих условиям задачи, равно 6419702202320000.