Cтраница 3
В динамической системе происходит постоянное обновление проектов через определенный промежуток времени, так что каждый раз нужно заново повторять процедуру построения максимального независимого множества в соответствующем графе С. В практических ситуациях бывает весьма не просто выполнить множество проектов, соответствующих максимальному независимому множеству на данном отрезке времени, поскольку исполнение некоторых проектов может быть по каким-то причинам отложено. Тогда лучший способ действия состоит в присвоении каждому проекту ( вершине) я; некоторого штрафа рг, который увеличивается с ростом времени отсрочки в исполнении проекта, и в каждый расчетный момент времени надо выбирать из семейства максимальных независимых множеств такое множество, которое максимизирует некоторую функцию штрафов на вершинах, содержащихся в выбранном множестве. [31]
В динамической системе происходит постоянное обновление проектов через определенный промежуток времени, так что каждый раз нужно заново повторять процедуру построения максимального независимого множества в соответствующем графе G. В практических ситуациях бывает весьма не просто выполнить множество проектов, соответствующих максимальному независимому множеству на данном отрезке времени, поскольку исполнение некоторых проектов может быть по каким-то причинам отложено. Тогда лучший способ действия состоит в присвоении каждому проекту ( вершине) xi некоторого штрафа рг, который увеличивается с ростом времени отсрочки в исполнении проекта, и в каждый расчетный момент времени надо выбирать из семейства максимальных независимых множеств такое множество, которое максимизирует некоторую функцию штрафов на вершинах, содержащихся в выбранном множестве. [32]
Например, а ( С5) 2, и множество У 0 2, обведенное кружками на рис. 1, является максимальным независимым множеством. [33]
Оно оказывается весьма существенным для задач максимальной упаковки баз матроидов, минимального покрытия исходного множества Е базами ( или независимыми множествами) матроида, а также отыскания максимального независимого множества двух матроидов на одном и том же множестве Е ( см. [ 1, гл. В настоящем разделе дано понятие увеличивающего или активного пути, интересного тем, что с его помощью всегда можно увеличить независимое множество суммы матроидов, если оно не максимально. Приведено конструктивное описание цикла суммы матроидов, которое существенно используется в дальнейшем. [34]
Частным случаем этой теоремы является результат Сершшского и Ппкара: если граф G локально конечен, а множество V бесконечно н несчетно, то (13.3.3) выполняется для любого максимального независимого множества. [35]
Частным случаем этой теоремы является результат Серпинского и Пикара: если граф G локально конечен, а множество V бесконечно и несчетно, то (13.3.3) выполняется для любого максимального независимого множества. То же равенство (13.3.3) выполняется также, когда V счетно, а локальные степени ограничены в совокупности. [36]
Если Q Ф 0, то немедленно заключаем, что текущее множество Sk было расширено на некотором предшествующем этапе работы алгоритма путем добавления вершины из Qh, и поэтому оно не является максимальным независимым множеством. [37]
Далее предположим, что каждый проект, задаваемый совокупностью средств, необходимых для его реализации, может быть выполнен за один и тот же промежуток времени. Максимальное независимое множество графа 5 представляет тогда максимальное множество проектов, которое можно выполнить одновременно за один и тот же промежуток времени. [38]
Подмножество вершин S V в графе 0 ( V, Е) называется независимым, если никакая пара вершин из S не смежна в G. S называется максимальным независимым множеством, если S не содержится в большем независимом множестве. [39]
С другой стороны, если нам не повезло и мы выбрали на первом шаге Vi, то в результате получится максимальное независимое множество W2, состоящее из единственной вершины. Совпадение дополнения одного максимального независимого множества с другим максимальным множеством в данном примере является случайностью. На рис. 3.27 независимое множество W - vz v4 является максимальным, однако его дополнение не является независимым множеством. [40]
Некоторое множество многогранников будем называть независимым, если никакой из них не выражается через остальные ( ср. В силу леммы Цорна существует максимальное независимое множество В Na, докажем, что оно является базисом. [41]
Далее предположим, что каждый проект, задаваемый совокупностью средств, необходимых для его реализации, может быть выполнен за один и тот же промежуток времени. Rt f ] Kj 0 - Максимальное независимое множество графа G представляет тогда максимальное множество проектов, которое можно выполнить одновременно за один и тот же промежуток времени. [42]
К этому моменту будут уже напечатаны все максимальные независимые множества. [43]
Максимальное независимое множество / 0 есть независимое множество, которое становится зависимым после добавления любой вершины. Заметим, что каждое независимое множество содержится в максимальном независимом множестве. [44]
Максимальное независимое множество есть независимое множество, которое становится зависимым после добавления к нему любой вершины. Заметим, что каждое независимое множество содержится в некотором максимальном независимом множестве. Максимальное число р ( /) вершин, составляющих независимое множество, называется числом ( вершинной) независимости графа. [45]