最优线性排列(optimal linear arrangment )图的一种标号.指标记图的节点的一种方法.图的一个线性排列二是指用不同的正整数标记图的节点的一种方法.用两端点标号差的绝对值来标记相应的边.用f (G)表示图的所有边标号的和,用f(G)表示图的所有线性排列二中f (G)的最小值.满足fn(G) = f(G)的线性排列二称为最优线性排列.f(G)称为图的价格.求图的最优线性排列是一个NP完全问题.