[已标记为低质量]图计数 : 从入门到出门

· · 个人记录

引言

学计数问题就像围城,城外的人不想进去,城里的人不想出来.

前前排提示

本文不全是多项式和生成函数.

前排提示

本文含有以下内容 :

请对以上内容感到不适者自行 Ctrl + W.

保证不出现以下内容 :

保证对于博客中 100 \% 的和式,为有明确界限的和式.

保证对于博客中 100 \% 的 \LaTeX , 其前后有空格.

附 : 博客中出现以及未来可能会出现的题目题单一份

前置知识

咱也不知道.

目录

慢慢整.

不支持 HTML 的 [TOC] , 真可惜.

约定与图论基础

图(Garph) : 定义由点集 V 与边集 E 组成的二元组叫做图,以下令 G<V,E> 表示一个点集为 V ,边集为 E 的图. 如无特殊说明,通常认为题目中的图具有 n 个点与 m 条边.

无向图(Undirected Graph) : 每条边不标定方向.

有向图(Directed Graph) : 每条边标定方向.

边(Edge) : 一个有序或无序的二元组,例如一条从 u 连向 v 的边,记作 (u,v)

完全图(Complete Graph) : 对于一个图 G<V,E> ,若 \forall u,v \in V(u \not= v),(u,v),那么这是一个完全图. 有 n 个结点的完全图记为 K_n .

竞赛图(Tournament Graph) : 对于一个完全图,将其每条边标定一个方向就得到了竞赛图.

度(Degree) : 与一个顶点 u 关联的边的条数称作该顶点的度. 记无向图一点 u 的度为 d_u. 记有向图一点 u 入度(positive deg)为 pd_u,出度(negative deg)为 nd_u.

三元环(Three-Vertex Cycle) : 一个三元环为由三个点 u,v,w 组成的无序三元组 <u,v,w> ,且满足 (u,v),(v,w),(w,u) \in E .两个三元环 G_1,G_2 不同当且仅当 \exists u \in G_1 且 u \not\in G_2 .

有向无环图 : 简称 DAG.

三元环计数

主要内容 : 组合数学.

无向图三元环计数

首先三元环并不能特别多,但是 \mathrm{O} (n ^ 3) 的复杂度明显不是很好,此题正解为 \mathrm{O} (m \sqrt{m}) .

首先记录每个点的度,将每条边按照如下的方式重定向 :

对于一条边 (u,v) , 如果 :

以上这一步使得每个点出边总是 \sqrt{m} 的水平.

然后枚举每个点 , 对于枚举到的一个点 u , \forall (u,v) \in E , 将 v 打上标记 u ,对于 u 的出边集均执行这个操作后,再次枚举 v 且枚举 v 的出边,如果存在点 w 使得 w 的标记为 u ,那么就找到了一个三元环.

P6815 [PA2009]Cakes 统计一下即可,但是图很稠密,链前会被卡常 (悲),但是 std::vector 很快 (喜).

CF985G Team Players 比赛编号985

正难则反,容斥一下.

先把所有三元组分类计数 :

最后记所有三元环为 x_tot

那么就是求 x_0 了.

容斥一下可知 : x_tot - x

P4619 [SDOI2018]旧试题

完全不可做的奇葩反演卡常题,但是这道题确实用了三元环计数.

下辈子补上.

有向图三元环计数

按照上面的算法正常跑,在找到一个三元环时特判三边方向是否全部合法即可.

完全图三元环计数

任意选三个点就是合法三元环.

三元环个数为 \binom{n}{3} .

竞赛图三元环计数

转化为求其补集 :

发现如果是一个完全图,其三元环个数为 \binom{n}{3},考虑其中哪些是不合法的三元环即可.

三元环个数为 :

\large{\binom{n}{3} - \sum^{n}_{i = 1} \binom{nd_i}{2}}

竞赛图三元环期望

给定点数 n , 与图中 m 条边的方向,求三元环期望个数.

依然补集转化 :

统计出入度,在上一题基础上再扣除一部分 :

令 ind_u 表示点 u 的入度.

令 outd_u 表示点 u 的出度.

那么点 u 未标定边数量表示为 : ud_u = n - 1 - pd_u - nd_u

三元环期望个数为 :

\large{\binom{n}{3} - \sum^{n}_{i = 1} (\binom{nd_i}{2} + \frac{nd_i \cdot ud_i}{2} + \frac{\binom{ud_i}{2}}{4})}

Prufer 序列与 Caylay 定理

LGV 引理

矩阵树定理

Kirchhoff 矩阵树定理能够求解图的生成树计数问题.

二分图计数

二分图的性质真是奇妙,性质就和竞赛图一样多.

建议翻到最后看看彩蛋.

sub1

求有 n 个有标号结点,黑白染过色的二分图个数.

不同仅当颜色或者边不同.

首先枚举黑白个数然后枚举哪些边连上就行,因为只能黑连白.

个数为 :

\large{\sum_{i = 0}^{n}\binom{n}{i}2^{i(n - i)}}

sub2

求有 n 个有标号结点的联通的二分图个数.

考虑从上面拓展.因为这个图连通,那么只需指定任何一点的颜色即可确定其余所有点的颜色,那么一个连通块就是 2 种状态.

然后考虑枚举一下有多少个连通块然后每个连通块的染色方案,整一个 EGF.

令 F(x) 表示 sub1 的EGF,G(x) 表示 sub2 的EGF.

&F(x) = \sum_{n = 0}^{\infty} \frac{\sum_{i = 0}^{n}\binom{n}{i}2^{i(n - i)}x^n}{n!}\\ &F(x) = \sum_{n = 0}^{\infty} \frac{2^nG^n(x)}{n!} \end{aligned}

然后因为 :

\sum_{n = 0}^{\infty} c^n\frac{x^n}{n!} = e^{cx}

那么 :

F(x) = e^{2G(x)}

那么多项式对数函数求 \frac{1}{2}\ln F(x) 即可.

sub3

求有 n 个有标号结点的二分图个数.

考虑

简单图计数

有标号简单图无向计数

首先考虑可行的所有边,显然,为 \frac{n(n - 1)}{2} 条.

每条边都可以选或者不选,乘法原理可知,数量为 :

\large{2^{\frac{n(n - 1)}{2}}}

DAG 计数

其他

这一部分就是想到哪写到哪了.

二叉树计数

求 n 个点的二叉树有几种形态.

著名的卡特兰数.

\large{C_n = \frac{\binom{2n}{n}}{n + 1}}

证明 : 令 f(x) 表示 有 x 个点的二叉树的不同形态个数.

那么通过枚举根节点左右子树分别有多少个结点可得以下递推式 :

f(x) = \sum^{x - 1}_{i = 0} f(i) \cdot f(n - i - 1)

做其 \mathrm{OGF} 得到 :

F(x) = \sum^{\infty}_{ n = 0} f(n)x^n

那么对于 F(x) \cdot F(x) , 其 x^n 项的系数为 f(n + 1), 那么对于 x \cdot F(x) \cdot F(x) , 其 x^n 项的系数为 f(n) .

列出等式如下 :

x \cdot F(x) \cdot F(x) = F(x)

解方程求得 :

F(x) = \frac{1 - \sqrt{1 - 4x}}{2x}

然后直接泰勒展开日过去得到通项.

单独考虑 $\sqrt{1 - 4x}$ 这一部分,对其做广义二项式展开. 根据 : $$ (1 + x)^\alpha = \sum^{\infty}_{k = 0} \binom{\alpha}{k} x^k $$ 有 : $$\begin{aligned} \sqrt{1 - 4x} &= (1 - 4x)^{\frac{1}{2}}\\ &= \sum_{k = 0}^{\infty} \binom{\frac{1}{2}}{k} (-4x)^k\\ &= 1 + \sum_{k = 1}^{\infty} \frac{(\frac{1}{2})(-\frac{1}{2})(-\frac{3}{2})\cdots (\frac{3 - 2k}{2})}{k!} (-4x)^k \\ &= 1 + \sum_{k = 1}^{\infty} (-1)^{n - 1} \frac{1 \times 3 \times 5 \cdots \times (2k - 3)}{2^k k!} (-4x)^k \\ &= 1 - 2 \sum_{k = 1}^{\infty} \frac{(2k - 2)!}{k!(k - 1)!} x^k \\ \end{aligned}$$ 然后代入原式 : $$ F(x) = \sum_{n = 0}^{\infty} \frac{\binom{2n}{n}}{n + 1} x^n $$ 即可得到通项. ### 三叉树计数 希望 [$\mathrm{\color{black}{L}\color{red}{ast\_Order}}$](https://www.luogu.com.cn/user/88028) 能看到这个. 求 $n$ 个点的三叉树有几种形态. [OEIS链接](http://oeis.org/A001764) $$ \large{T_n = \frac{\binom{3n}{n}}{2n+1}} $$ ## 彩蛋 : 二分图最大匹配计数 没有这种算法,这是一个 $\mathrm{\# P-Complete}$ 问题,乐. 也就是对于一个 $\mathrm{P}$ 类问题,如果从求解转化为求解的个数,那这就是一个 $\mathrm{\# P}$ 问题(sharp - P problem). 众所周知网络流是 $\mathrm{P}$ 问题,于是二分图最大匹配自然也是.