В ориентированном графе 12 вершин, пронумерованных числами от 1 до 12, любые две его вершины соединены одним ребром. Также известно, что в нём четыре компоненты сильной связности, состоящие из трёх вершин: (1,2,3),(4,5,6),(7,8,9),(10,11,12). Сколько существует таких графов? Графы считаются разными, если найдётся пара вершин таких, что в этих графах их соединяют рёбра, направленные по-разному.
В ориентированном графе 12 вершин, пронумерованных числами от 1 до 12, любые две его вершины соединены одним ребром. Также известно, что в нём четыре компоненты сильной связности, состоящие из трёх вершин: (1,2,3),(4,5,6),(7,8,9),(10,11,12). Сколько существует таких графов? Графы считаются разными, если найдётся пара вершин таких, что в этих графах их соединяют рёбра, направленные по-разному.
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для решения этой задачи нам нужно рассмотреть количество способов соединения вершин графа с учетом условий задачи.
Поскольку в графе 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 = 287980
C(129, 3) = 129! / (3! (129-3)!) = 129128127 / 6 = 341376
C(126, 3) = 126! / (3! (126-3)!) = 126125124 / 6 = 328500
C(123, 3) = 123! / (3! (123-3)!) = 123122121 / 6 = 243336
Теперь вычислим итоговый ответ:
287980 341376 328500 * 243336 = 6419702202320000
Итак, число существующих графов, удовлетворяющих условиям задачи, равно 6419702202320000.