Enumeration of labelled flower wheel graphs.pdf Точкой сочленения связного графа называется его вершина, после удаления которой вместе с инцидентными ей рёбрами граф становится несвязным. Блок - это связный граф без точек сочленения, а также максимальный связный нетривиальный подграф, не имеющий точек сочленения. Корневой граф имеет одну выделенную вершину, называемую корнем. Колесо Wn - граф с n ^ 4 вершинами, который образован соединением единственной вершины со всеми вершинами (n - 1)-цикла [1, с. 63]. Граф W4 изоморфен полному графу K4. Цветочно-колёсный граф с m лепестками - это связный граф с одной точкой сочленения, у которого все m блоков (лепестков) - колёса, причём вершина, являющаяся осью колеса, не может быть точкой сочленения. Цветочно-колёсные графы представляют топологию коммуникационных, компьютерных и других сложных сетей [2]. Кроме того, перечисление графов тесно связано с теорией случайных графов; рандомизация колёсных подграфов сети может использоваться для защиты данных пользователей социальных сетей [3]. Теорема 1. Число FW(n,m) помеченных цветочно-колесных графов с n вершинами и m лепестками при n ^ 7 и m ^ 2 равно . n! JL fm\fn - 2m - г - 2\ • FW (n-m> = m^SUl m-1 где r = min(m, n - 3m - 1). те zn Доказательство. Пусть Cm(z) = E FW(n,m) -, NWn - число помеченных n=4 n! колёс с n вершинами, RWn - число помеченных корневых колёс с n вершинами, R(z) = те zn = те RWn -г. n=4 n! Так как метку для оси колеса Wn можно выбрать n способами и число циклов с n - 1 помеченными вершинами равно (n - 2)!/2, то NWn = n(n - 2)!/2 при n ^ 5, NW4 = 1. Поскольку корень колеса Wn не должен быть вершиной-осью колеса, то метку для него можно выбрать n - 1 способами и при n ^ 5 имеем RWn = (n - 1)NWn = n!/2. Однако в случае W4 (полный граф) осью может быть любая вершина и RW4 = nNW4 = = 4. Поэтому имеем z4 1 те z4 z5 R(z) = - +1 E zn = - + , z 4. () 6 2 n=5 6 2(1 - z) Граф с одной точкой сочленения может рассматриваться как корневой граф с корнем в точке сочленения. Такой граф можно получить склейкой в одну вершину непомеченных корней блоков. После склейки для непомеченной вершины вводится новая метка. Снятию метки с корня соответствует операция деления соответствующей производящей функции на z, а введению метки - операция умножения производящей функции на z [4, 5]. С учётом перестановок блоков вокруг точки сочленения получим z / R(z) \m_ z / z3 z4 \m_ z3m+1(1 + 2z)m m(z) = m! v= m v"6 + 2(1 - z)J = m!6m(1 - z)m ' те С помощью бинома Ньютона и ряда (1 - z)-m = ^ (kmm-1)zk найдём ym • ~_ / yl .I2 z / у 1 Iz cm (z)=mmm |( 7) k mm-0 Следовательно, имеем FW(n,m) = n![z 1]Cm(z)z n 1, где [z 1] -оператор формального вычета: n! l~-1l m / m\ / k + m ^ 0i i+k+3m-n FW (n,m) = m^ [z-1]EE . ' i 2V m!6m i=o k=o\ i/\ m - 1 _ n! ^ /m\ /n - 2m - i - 2N. ^ m!6mj=0\ i у \ m - 1 Поскольку биномиальный коэффициент обращается в ноль при m < i и n - 2m - i - 2 < < m - 1, верхний предел суммы равен r = min(m, n - 3m - 1). ■

Скачать электронную версию публикации