能集齐所有路径数的有向无环图构造

KeyTo9_Fans

给定m，要求构造一个顶点数为n（n≥2）、边数为m、无重边、1号点入度为0、n号点出度为0的有向无环图，

使得任意给定一个整数p，满足0≤p≤P，

都可以保留图中的某些边（去掉其余的边），使得从1号点出发，到达n号点的路径条数恰好是p条

对于不同的m，可以满足上述要求的最大的P是多少？

例如：

当m=0时，P的最大值是0

当m=1或2时，P的最大值是1

当m=3或4时，P的最大值是2

当m=5时，P的最大值是3

当m=6时，P的最大值是4

当m=7时，P的最大值是5

……

当m=5050时，P的最大值介于2^99到(2^5050-1)之间

其中，下界2^99来自101个顶点的全序图，无论p是几，都有办法去掉某些边，使得从1号点出发，到达n号点的路径条数恰好是p条

上界(2^5050-1)是因为去掉图中某些边的方案数是2^5050种，最多只能凑出0条、1条、2条、……、(2^5050-1)条，共计2^5050种不同的路径条数

有办法求出更准确的阶吗？