Cтраница 3
Следующая теорема устанавливает связь между базисами транспортного многогранника и остовными деревьями соответствующего полного двудольного графа. [31]
Для непустоты ( k, - усеченного транспортного многогранника баланса уже недостаточно. [32]
Верно ли, что граф всякого невырожденного классического транспортного многогранника является гамильтоновым, но не является панцикли-ческим. [33]
Верно ли, что для всякого вырожденного усеченного транспортного многогранника порядка тхп существует невырожденный усеченный транспортный многогранник того же порядка с неменьшим числом вершин. [34]
Поэтому, поскольку для числа граней всякого транспортного многогранника М ( а, Ь) порядка тхп справедливо неравенство fa-i ( М ( a, b)) тп, то из теоремы 3.2 получается следующий факт. [35]
Среди многогранников задач линейного программирования достаточно полно изучены транспортные многогранники, и в первую очередь многогранники классической транспортной задачи. [36]
Витцчалл [45] высказали гипотезу о том, что центральный транспортный многогранник порядка т х п при взаимно простых числах тип имеет максимальное число вершин. [37]
Очевидно, что правильный ( k, - усеченный транспортный многогранник Mh t ( a, b) порядка тхп является с ( - симплексом тогда и только тогда, когда он содержит d - - вершин. В случае 1) всякий правильный ( k, - усеченный транспортный многогранник является 0-симплексом. [38]
Ясно, что всякий ( k, - усеченный транспортный многогранник порядка тхп при min ( m, га) 2 явлается либо правильным, либо вырождается в точку. [39]
В этом параграфе рассматривается асимптотическое поведение некоторых классов транспортных многогранников. Показано, что с ростом порядка отношение числа многогранников с максимальным количеством граней к общему числу многогранников стремится к единице, а отношение числа многогранников с минимальным, либо максимальным количеством вершин - к нулю. [40]
В настоящее время получены лишь необходимые условия непустоты трехиндексного планарного транспортного многогранника. В данном пункте приводятся некоторые из них. [41]
Рассмотрим теперь вопрос о том, какова максимальная размерность трехиндексного планарного транспортного многогранника. Ответ на этот вопрос дает следующая теорема. [42]
Поэтому, принимая во внимание, что размерность всякого невырожденного трех-индексного планарного транспортного многогранника порядка mxnxk равна числу ( m - l) ( n - l) ( k - l), заключаем, что многогранник М ( А0, В0, С0) будет ( т - 1) ( п - 1) ( k - 1) - симплексом. [43]
Очевидно, что при р 2 этот многогранник является классическим транспортным многогранником. [44]
Следующая теорема составляет основу излагаемого ниже подхода к задачам перечисления вершин транспортного многогранника. [45]