Cтраница 3
Далее предположим, что каждый проект, задаваемый совокупностью средств, необходимых для его реализации, может быть выполнен за один и тот же промежуток времени. Максимальное независимое множество графа 5 представляет тогда максимальное множество проектов, которое можно выполнить одновременно за один и тот же промежуток времени. [31]
С другой стороны, если нам не повезло и мы выбрали на первом шаге Vi, то в результате получится максимальное независимое множество W2, состоящее из единственной вершины. Совпадение дополнения одного максимального независимого множества с другим максимальным множеством в данном примере является случайностью. На рис. 3.27 независимое множество W - vz v4 является максимальным, однако его дополнение не является независимым множеством. [32]
Если оа - первый невычеркнутый после о объект, находим все o - oe, ja1 ( и вычеркиваем их. Продолжая в том же духе, мы получаем максимальное множество неэквивалентных объектов. Таким образом, решето, отбраковывающее изоморфные объекты, является специальным случаем рекурсивного решета. [33]
Далее предположим, что каждый проект, задаваемый совокупностью средств, необходимых для его реализации, может быть выполнен за один и тот же промежуток времени. Rt f ] Kj 0 - Максимальное независимое множество графа G представляет тогда максимальное множество проектов, которое можно выполнить одновременно за один и тот же промежуток времени. [34]
Дело в том, что любой канал обладает одноэлементными максимальными множествами, а именно х, AX-Y. Это не имеет места для расширяющих множеств, а следовательно, и для ограниченных максимальных множеств. Читатель легко может построить примеры каналов, не имеющих для данных е, К соответствующих расширяющих множеств, а также каналов, представляющих каждый из возможных случаев, рассматривая их с точки зрения существования максимальных множеств. [35]
Первые основаны на известных системах счисления, вторые - яа законах теории соединений. Цель, преследуемая в первую очередь при Применении кода, состоит в получении возможно максимального множества N при данных тип. [36]
Обозначим через W множество максимальных множеств. Множество W непусто, так как - А непротиворечиво и, следовательно, является подмножеством некоторого максимального множества. В самом деле, если существует k подпред-ложений предложения А, то существует не более чем 2 максимальных подмножеств. [37]
Если Л - граф - несвязный, рассматриваем его связные компоненты. Так как последние не имеют общих вершин, то окраска каждой отдельной компоненты не ограничивает окраску других компонент. Поэтому максимальное множество красных дуг 77-графа состоит из суммы максимальных множеств красных дуг отдельных компонент. [38]
Присоединив к каждой компоненте все белые С-дуги, которые входят в ее вершины, получим ЛС-граф. Белые С-дуги одной компоненты не ограничивают окраску дуг других компонент, потому что они не входят в вершины других компонент. Следовательно, максимальное множество красных дуг ЛС-графа состоит из суммы максимальных множеств красных дуг каждой компоненты. [39]
Когда сегменты перемещаются изнутри вовне и обратно, должны передвигаться соответствующие элементы в стеках 1ST и OST. Этот шаг может повлечь за собой сдвиг элементов вперед и назад много раз, и было бы более эффективно сдвигать элементы группами, а не по отдельности. Для этой цели определим связку как максимальное множество элементов в 1ST и OST, соответствующих обратным ребрам такое, что размещение одного обратного ребра определяет размещение всех других. [40]
Цикл 52 выполняет модификацию массава СОЧЕТ, соответствующего увеличению паросочетания вдоль такой цепи. Отметим, что если во время выполнения нашей процедуры некоторой вершине v е V приписывается значение ЯО-ВЫЙ [ и ]: ложь, то эта процедура либо находит затем чередующуюся цепь, проходящую через эту вершину, либо устанавливает, что не существует ни одной цепи, проходящей через эту вершину и не пересекающей ни одной из ранее найденных цепей. Отсюда легко следует, что процедура ФАЗА находит максимальное множество непересекающихся кратчайших чередующихся цепей. Корректность всего алгоритма следует из анализа метода Диница, проведенного в предыдущем разделе. [41]
Если Л - граф - несвязный, рассматриваем его связные компоненты. Так как последние не имеют общих вершин, то окраска каждой отдельной компоненты не ограничивает окраску других компонент. Поэтому максимальное множество красных дуг 77-графа состоит из суммы максимальных множеств красных дуг отдельных компонент. [42]
Присоединив к каждой компоненте все белые С-дуги, которые входят в ее вершины, получим ЛС-граф. Белые С-дуги одной компоненты не ограничивают окраску дуг других компонент, потому что они не входят в вершины других компонент. Следовательно, максимальное множество красных дуг ЛС-графа состоит из суммы максимальных множеств красных дуг каждой компоненты. [43]
Следовательно, для графа, приведенного на рис. 3.1, множество х7, XB -, xz, х5 является максимальным, а х -, xs, xz не является таковым. Множества xt, x3, х7 и z4, хе также являются максимальными независимыми множествами, и, значит, в данном графе больше одного независимого множества. Следует также отметить, что число элементов ( вершин) в разных максимальных множествах, как следует из приведенного выше примера, не обязательно одинаковое. [44]
Вспомогательной сети равен единице. Нетрудно заметить, что увеличивающая кратная цепь, найденная на каждой итерации главного цикла процедуры MAXPSA ( см. предыдущий раздел), имеет вид одиночной увеличивающей цепи. Теперь ясно, что во вспомогательной бескон-туриой сети длины / 2 поток идет вдоль максимального множества путей длины / 2 из s в t с попарно непересекающимися множествами промежуточных вершин. Этому множеству есте-ств нным образом соответствует максимальное множество чере - ДУКщихся цепей длины / с попарно непересекающимися множествами вершин ( под максимальным мы подразумеваем такое множество, которое нельзя увеличить на дополнительную чередующуюся цепь длины / и на множество вершин, не содер-жа. [45]