文章目录

• • 前言
  • 七、树与图的一些计数问题（偏数学）
  • • 容斥原理
    • • 知识点
      • 例题
      • • e g 1 : eg1: eg1: 完全子图染色问题
        • e g 2 : eg2: eg2: D A G DAG DAG计数
        • 生成树计数
        • • 知识点
          • 例题
          • 环计数问题
          • 练习题

            前言

            由于图论学习总结内容过多，全放在一篇博客过于冗长现进行拆分，本文是树与图的一些计数问题部分，其他部分地址见：图论学习总结(For XCPC)

            七、树与图的一些计数问题（偏数学）

            容斥原理

            知识点

            待更新

            例题

            e g 1 : eg1: eg1: 完全子图染色问题

            A 和 B 喜欢对图（不一定连通）进行染色，而他们的规则是，相邻的结点必须染同一种颜色。今天 A 和 B 玩游戏，对于 n n n 阶 完全图 。他们定义一个估价函数 F ( S ) F(S) F(S)，其中 S S S 是边集， S ⊆ E S\subseteq E S⊆E. 的值是对图 G ′ = ( V , S ) G'=(V,S) G′=(V,S) 用 m m m 种颜色染色的总方案数。他们的另一个规则是，如果 ∣ S ∣ |S| ∣S∣是奇数，那么 A A A 的得分增加 F ( S ) F(S) F(S)，否则 B B B 的得分增加 F ( S ) F(S) F(S). 问 A A A 和 B B B​ 的得分差值。

            一看这道题的算法趋向并不明显，因此对于棘手的题目首先抽象出数学形式。得分差即为奇偶对称差，可以用 -1 的幂次来作为系数。我们求的是我们求的是 A n s = ∑ S ⊆ E ( − 1 ) ∣ S ∣ − 1 F ( S ) Ans=\sum_{S\subseteq E}(-1)^{|S|-1}F(S) Ans=∑S⊆E​(−1)∣S∣−1F(S)​

            e g 2 : eg2: eg2: D A G DAG DAG计数

            ​ 待更新

            生成树计数

            知识点

            • 矩阵树定理

              例题

              环计数问题

              练习题

              #2542. 「PKUWC2018」随机游走 - 题目 - LibreOJ (loj.ac)

              P4707 重返现世 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)