acm程序设计竞赛 数学基础 刘汝佳 - 图文

数学基础

(版本2009)

刘汝佳

Mathworld.wolfram.com

例1. 同构计数

?一个竞赛图是这样的有向图

–任两个不同的点u、v之间有且只有一条边–不存在自环

?用P表示对竞赛图顶点的一个置换。当任两个不同顶点u、v间直接相连的边的方向与顶点P(u)、P(v)间的一样时，称该图在置换P下同构

?对给定的置换P，我们想知道对多少种竞赛图在置换P下同构

例1. 同构计数?例：有顶点1、2、3、4和置换P：P(1)=2，P(2)=4，P(3)=3，P(4)=1?对于下图的四种竞赛图，在置换P下同构1 2 12121234 343434分析

?先把置换它分解成为循环, 首先证明长度为L的偶循环将导致无解

–对于点i1, 记P(ik)=ik+1, 假设i1和iL/2+1的边方向为i1->iL/2+1, 那么有i2->iL/2+2, i3->iL/2+3, …, iL/2+1->i1, 和假设矛盾!

?假设确定其中k条独立边后其他边也会确定, 则答案为2k

?考虑两类边: 循环内边和循环间边.