树与图的一些计数问题(图论学习总结部分内容)

admin2024-05-15  0

文章目录

    • 前言
    • 七、树与图的一些计数问题(偏数学)
      • 容斥原理
        • 知识点
        • 例题
          • 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 SE. 的值是对图 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=SE(1)S1F(S)

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

​ 待更新

生成树计数

知识点
  • 矩阵树定理
例题

环计数问题

练习题

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

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!