《清华大学组合数学8》由会员分享，可在线阅读，更多相关《清华大学组合数学8（51页珍藏版）》请在金锄头文库上搜索。
1、1 习题讨论 3.52 空间2n个点,证明n2+1条线段任意连接, 必出现一个三角形 大部分同学采用构造方法,证明二分图里两 边互连,最多n2条线段不出现三角形,再加一 条边必出现三角形 但是不够严密,并不是所有的连接都能划分 成二分图 1 2 1 2 1 6个点,不能划分成二分图 2 习题讨论 3.52 空间2n个点,证明n2+1条线段任意连接,必出现一个三 角形 证明:利用反证法 假设存在n2+1条线段中没有三角形,设图中各点度数最大 点p的度数为a,则p与a个点相连, 0a0 r1b1g2的系数= r1b2g1的系数= r2b1g1的系数= (C(4,1)*C(3,1)*C(2,2)+2
2、*C(2,1)/4=4 故若不允许有空盒, 分配方案有4*3=12种 4.8 图的计数 n个顶点的简单图有多少不同的图形? 简单图:过两个顶点没有多于一条的边,且不存 在环的图形 n个无标志顶点的完全图中的边进行二着色,求 不同方案数 完全图中的边数n(n-1)/2 图的计数 n个无标志顶点的完全图中的边进行二着色, 求不同方案数 完全图的置换 边随点动 不仅仅是旋转和翻转 点的全置换,对应对称群 v1 v2 v3 e1 e2 e3 v4 e4 e5e6 4.8 图的计数 以3个顶点为例 顶点的置换: S3=e,(v1v2v3), (v3v2v1), (v2v3), (v1v3), (v1v2
3、) 对应边的置换G=e,(e1e2e3), (e3e2e1),(e1e2), (e1e3),(e2e3) P(G)=(x+y)3+2*(x3+y3)+3*(x+y)(x2+y2)/6 = x3+y3+xy2+x2y v1 v3v2 e1 e2 e3 4.8 图的计数 例例 4个顶点的图 对完全图的边的2着色 S4的每个置换对应6条边的集上的一个置换 顶点边个数 (1)4(1)61个 (1)2(2)(1)2(2)2 6个 (4)1 (2)1(4)1 6个 (2)2 (1)2(2)2 3个 (1) (3) (3)28个 P(x,y) = (x+y)6+9(x+y)2(x2+y2)2+8(x3+y3
4、)2 +6(x+y)2(x2+y2)2/24 v1 v2 v3 e1 e2 e3 v4 e4 e5e6 v2 v1 v3 e1 e6 e5 e4e2 e3 v4 4.8 图的计数 =x +x y+2x y +3x y +2x y +xy +y 6 5 4 2 3 3 2 4 5 6 4.8 图的计数 例例2 求4个顶点的不同构的有向图的个数。 边数12条,每个点出边3条,入边3条 解解 顶点置换有向边置换 (1)4(1)121个 (1)2(2)(1)2(2)5 6个 (4)1 (4)3 6个 (2)2 (2)6 3个 (1) (3) (3)48个 P(x,y) = (x+y)12+6(x+y)2(x2+y2)5+3(x2+y2)6 +8(x3+y3)4+6(x4+y4) /24 4.8 图的计数 x y 的系数：+6(1+)+3 +0+0=5 1 12! 5! 6! 24 2!10! 4! 5! 2 10 P(x,y) = (x+y)12+6(x+y)2(x2+y2)5+3(x2+y2)6 +8(x3+y3)4+6(x4+y4) /24
