Посчитать количество графов в котором хотя бы одна вершина имеет степень N - 1

Question

Как посчитать количество неориентированных графов из N вершин , где ни у одной вершины нет степени N-1. Графы без петель и кратных ребер.

До чего пришел : Всего графов на N вершинах можно построить 2^N*(N-1)/2 Нужно из этого количества графов в которых хотя бы у одной вершины степень N-1.

Answer 1

Edit исправил, т.к. первоочередное то, что в первом абзаце, а не то, что в заголовке.

Количество нужных графов из симметрии равно количеству графов, где нет ни одной изолированной вершины. А для них есть такой код.

cnk - количество сочетаний из n по k.

(1 - 2 *((n - k) & 1)) - это -1 в степени (n - k) для чередования знаков - принцип включения, исключения, видимо

(1 << (k * (k - 1) // 2) - это 2 в соотв. степени

def cnk(n, k):
    k = min(k, n - k)
    if k <= 0:
        return 1 if k == 0 else 0
    res = 1
    for i in range(k):
        res = res * (n - i) // (i + 1)
    return res

def numconn(n):
    res = 0
    for k in range(n + 1):
        res += (1 - 2 *((n - k) & 1)) * cnk(n,k) * (1 << (k * (k - 1) // 2))
    return res

for n in range(2, 10):
    print(n, numconn(n))

2 1
3 4
4 41
5 768
6 27449
7 1887284
8 252522481
9 66376424160

P.S. Поискал результаты в oeis - вот они, и формула у меня же и используется

БЛОГ НА HUSL

Посчитать количество графов в котором хотя бы одна вершина имеет степень N - 1

Ответы (1 шт):