随机图 G( n,p)是具有 n 个标号的顶点的图,并且图中的每一顶点对都以概率 p 被随机且独立地选择为图 G 的边。特别地,当 p =2/1时,得到一个概率空间,其中 n 个顶点上的所有标号图是等概率的。对于有顶点集 V 和边集 E 的简单图 G =( V,...随机图 G( n,p)是具有 n 个标号的顶点的图,并且图中的每一顶点对都以概率 p 被随机且独立地选择为图 G 的边。特别地,当 p =2/1时,得到一个概率空间,其中 n 个顶点上的所有标号图是等概率的。对于有顶点集 V 和边集 E 的简单图 G =( V,E),G 的 f-染色 c 是广义的边染色,使每个颜色类在任一顶点 v 上至多出现 f( v)次,其中 f(v)是分配给 v 的正整数。给出随机图 G (n,2/1)是 f-第一类的一个充分条件。展开更多
文摘随机图 G( n,p)是具有 n 个标号的顶点的图,并且图中的每一顶点对都以概率 p 被随机且独立地选择为图 G 的边。特别地,当 p =2/1时,得到一个概率空间,其中 n 个顶点上的所有标号图是等概率的。对于有顶点集 V 和边集 E 的简单图 G =( V,E),G 的 f-染色 c 是广义的边染色,使每个颜色类在任一顶点 v 上至多出现 f( v)次,其中 f(v)是分配给 v 的正整数。给出随机图 G (n,2/1)是 f-第一类的一个充分条件。
