一道来源于编译器优化中的图论难题
$G(V,E)$是一个有向图，V是顶点的集合,E是边的集合。并且已知存在一个边上的权函数$f: E->bar(Z^-)$。其中$bar(Z^-)$表示非负整数集。现在将G看成一个无向图，那么对于这个无向图中任何一个环路,我们可以定义环路上的权重为环路上所有边的权重的有向和
（也就是边的权重取和，但是边取权重时，如果边e的方向同环路方向相同，取边权重为f(e)，如果相反，取边权重为-f(e))。
如果所有环路的权重的最大公约数为d,而且d>1,求证，存在函数$g: V->bar(Z^-)$，使得对于任意边$e= (:u,v:) in E$,定义
$f'(e)=f(e)+g(v)-g(u)$,那么$f$'的值域为$d bar(Z^-)$,也就是存在顶点到非负整数集的函数g,使得对应的调整后的边到非负整数集的权重函数$f'$取值都是
d的倍数，当然也要求是非负整数。
相关的编译器优化方面资料：http://bbs.emath.ac.cn/thread-173-6-1.html
页:
[1]