Решить алгоритмическую задачу на python (подсчет вариантов построения графа)
Не могу решить алгоритмическую задачу. Очевидно здесь какой-то сложный перебор. Можете помочь советом по реализации (какой алгоритм использовать). Буду еще больше благодарен если напишите программку.
Заранее огромное спасибо!
Ответы (1 шт):
Пусть есть граф R с единственной вершиной степени n-1
Его дополнением будет граф Q с единственной вершиной степени 0, т.е. остальная часть графа связна. Дополнение - это такой граф, у которого есть ребро там, где у исходного графа нет связи и наоборот - если у исходного есть ребро, то в дополнении ребра нет. Понятно, что дополнений ровно столько же, сколько исходных графов.
Таким образом, нужно найти количество помеченных связных графов L с n-1 вершинами, и умножить на n - т.к. в списке из n-1 вершин есть n мест, куда можно вставить новую вершину.
R(n) = L(n-1) * n
Проверяем на приведённых примерах: (исключая 1,2 как тривиальные, и для них связность меньшего графа интерпретировать можно по-разному)
R(3) = L(2)*3 = 1*3 = 3
R(4) = L(3)*4 = 4*4 = 16
Чтобы убедиться в правильности подхода, проверьте, что
R(5) = L(4)*5 = 38*5 = 190
Это можно сделать брутфорсом - сгенерировать 2^(n*(n-1)/2) возможных графов и проверить, в скольких из них только одна вершина имеет степень n-1
Как найти количество помеченных связных графов? Сами погуглите.