一类平面多物品流可行性研究

Feasibility Study on One Class of Planar Multicommoldity Flows

将Ｐ．Ｄ．Ｓｅｙｍｏｕｒ的平面无向图的条件进一步放宽，提出了一类平面多物品流问题．假定图Ｇ是一个平面无向图，Ｇ中一些源、汇同在一顶点，其对应的汇、源可以连接与该顶点邻接的顶点，其余的源（汇）可以连接与之相对应的汇（源），而不破坏图的平面性．把图Ｇ经适当变形，转变为含有参变量（需求）和约束条件的图Ｇａ，给出了图Ｇ存在多物品流的一个充分必要条件，提出了验证其多物品流可行性的一个方法．

It is supposed that G is an undirected graph in which all the sources/ sinks can be joined to the corresponding sinks/sources or the vertices adjacent to a vertex on which the corresponding sources and sinks are located, without destroying the planarity. Graph G is changed into graph Ga which contains parameters and constraint conditions, and then the necessary and sufficient condition is given for the existence of multiicommodity flows satisfying given demands. Finally, a method is put forward for testing the feasibility of multicommodity flows in G.