Speaker
Яков Гринберг
(ИППИ РАН)
Description
Полные N-вершинные графы рассматриваются как выпуклые конусы G в вещественном пространстве R размерности N(N-1)/2, орты в котором суть ребра графа, а крайние векторы суть следующие векторы , где - орты пространства R. Показано, что крайние векторы конуса , сопряженного конусу G, можно интерпретировать как сети, имеющие потоковые и сетевые ребра. Показано также, что для любой сети, определяемой полным графом, а также выделенными в нем потоковыми ребрами с заданными интенсивностями потоков и сетевыми ребрами с заданными пропускными способностями, можно определить вектор в пространстве R – вектор сети – что реализуемость в сети соответствующего многопродуктового потока зависит от того, принадлежит ли этот вектор конусу G или нет. Это, в свою очередь, означает, что критерием реализуемости потока является неотрицательность скалярных произведений вектора сети с некоторыми из крайних векторов конусов .
Primary author
Яков Гринберг
(ИППИ РАН)
