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

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

Для каждой компоненты сильной связности из трёх вершин имеется 2 возможных способа установить направление рёбер между этими вершинами. Таким образом, всего возможных вариантов установить направление рёбер в графе равно $2^4 = 16$.

Теперь определим количество способов размещения вершин внутри каждой компоненты сильной связности. Для первой компоненты существует 3! = 6 способов, для второй - также 3! = 6 способов, для третьей и четвертой компонент - по 3! = 6 способов каждая.

Итого, общее количество возможных графов равно $16 \times 6^4 = 9216$. Таким образом, существует 9216 различных графов, удовлетворяющих условиям задачи.