Перечисление графов. Производящая функция для числа помеченных графов с р вершинами
13.03.2012 |Определение: Пусть G=(V,E) есть (p,q)-граф, где V={v1,…,vp}-множество вершин (узлов), E={e1=(vi1, vj1), …, eq=(viq, vjq)}-множество неориентированных ребер без петель, т.е. ik ≠jk, k=1,2,…q. Пусть множество Р={1,2,…,p}. (p,q)-граф G=(V,E) является помеченным графом, если взаимнооднозначная функция f:V→P приписывает пометку для любой вершины v из V из G. Пометки f1, f2 графа G одинаковы, если существует изоморфизм φ: G→G , сохраняющий пометки вершин f1(v)=f2(φ(v)).
Теорема: Производящая (порождающая) функция Gp(x) для числа помеченных графов с р вершинами задаётся соотношением:
Gp(x) = (1+x)m = ∑Cmkxk, m = Cp2.
Доказательство: Пусть V={1,2,…,p} есть множество из р вершин. Каждые 2 вершины можно соединить следующим образом:
число рёбер m = Cp2. Из этого набора m рёбер можно выбрать k рёбер, образующих (р,к) граф, Cmk способами, тогда Gp(x) = ∑Cmkxk = (1+x)m – производящая функция для числа помеченных графов с p вершинами. Коэффициент при xk равен числу помеченных графов с p вершинами и k рёбрами.
Замечание: Gp(1) = (1+1)m = 2m – число помеченных графов с р вершинами.
