|
|
发表于 2025-2-13 09:45:22
|显示全部楼层
可能用图来表示会简单一点，n个非空开区间两两之间是否有非空交集，可以用含n个有编号顶点的简单无向图表示，如果一个图编号之后能作为这种区间图，会有这些性质
(1) 每个导出子图一定也都能作为区间图
(2) 区间图不会是超过3个顶点的圈
(3) 如果某个顶点u和图G中其它所有顶点都相邻，或者与其它所有顶点都不相邻，那图G能作为区间图，当且仅当G-u能作为区间图
然后列举了n=1~5的情况
当n=1, 2, 3时所有的n顶点简单无向图都能作为区间图，带编号的n阶图一共有 2^[n(n-1)/2] 种，|S|=2^[n(n-1)/2] = 1, 2, 8
当n=4时除了长为4的圈以外，其它图都能作为区间图，C4编号有3种方式，所以|S|=2^6 - 3 = 61
当n=5时无编号5阶图有34种，其中只有7种图不能作为区间图 (它们都含有C4或C5作为导出子图)，其它图都能构造出对应的区间
这7种图编号分别有15, 30, 10, 15, 60, 60, 12种方式，所以剩下的5阶图编号方式一共有2^10- (15+30+10+15+60+60+12) = 822 种，|S|=822
对更大的n列举结果或者验证的话，就挺麻烦了 |
|
