Cтраница 4
Доказать, что двудольный граф никогда не является ( /, 0) - критическим. [46]
В [7] определен двудольный граф с п входами и п выхо-ходами, называемый ( п - i / j) - эспандером. Он обладает тем свойством, что для каждого подмножества, состоящего из n / i входов, существует n / j выходов, таких, что в каждый из этих выходов ведет ребро из данных n / i входов. [47]
Если С - двудольный граф, то D2 ( G) является просто объединением двух возможных транзитивных ориентации G, а пространство дуплекса - в некотором смысле комбинацией графовой топологии и котопологии. Все количественные выводы остаются неизменными; в частности, топологические порядки связей те же самые для исходной молекулы и дуплекса. [48]
Если С - двудольный граф, то iya0p0, а равенство достигается только для полных двудольных графов. [49]
Если G - регулярный двудольный граф, то он имеет совершенное паросочетание. [50]
Пусть G есть регулярный двудольный граф с In вершинами. [51]
Сеть Петри представляет собой двудольный граф, т.е. граф, содержащий вершины двух типов: позиции ( обозначаются окружностями, рис. 66) и переходы ( обозначаются в виде линий-планок), а также направленные ребра, которые могут соединять вершины разных типов. [52]