Диссертация (Математическое моделирование в задачах планирования и организации железнодорожных перевозок методами теории графов и комбинаторной оптимизации и численные методы их решения), страница 9

. . , 1) .Граф2– полный, значит множество верхних нулей функциивид:1 = (1, 0, . . . , 0) ,2 = (0, 1, . . . , 0) ,... = (0, 0, . . . , 1) .2имеет48Любой набор ∈ max (2 )⊆является нулем функции1 ,однако, ниодин такой набор не является её верхним нулём, то естьmax (2 ) ⊆ (1 ), max (2 ) ̸⊆ max (1 ) ,⊆⊆⊆что является заключением Леммы 2.2.1 и подтверждает (2.2.5).Введём обозначение для числа единиц в максимальном верхнем нуле мо­нотонной булевой функции:max0 = |supp ()| : ∈ max max ( ) .|·|⊆Следствие 2.2.1. Пусть заданы графы 1 = ( , ℰ1 ) и 2 = ( , ℰ2 ) такие,что ℰ1 ⊆ ℰ2 . Тогдаmax0 1Доказательство.Рассмотрим произвольный элемент множества максималь­ных верхних нулейграфов имеем> max0 2 . ∈ max max (2 ) .|·|⊆Согласно Лемме 2.2.1, для заданных ∈ (1 ) .По определению максимального верхнего нуля монотонной булевой функ­ции∀ ∈ (1 ) ∃ ′ ∈ max max (1 ) : ′ > ,⊆|·|и тогда имеемmax0 1= |supp (′ )| > |supp ()| = max0 2 ,что и требовалось доказать.Утверждение 2.2.2.

Пусть задан граф = ( () , ℰ ()) , и пусть верши­ны и в графе не смежны. Тогдаmax0 Доказательство.> max0 ∪}︀ > max0 − 1 .{︀{ , }(2.2.6)Непосредственно из Следствия 3.2.1 верно первое неравен­ствоmax0 > max0 {︀}︀ ,∪ { , }и для доказательства второго неравенстваmax0 ∪{︀}︀ > max0 − 1{ , }49рассмотрим произвольный верхний нуль функциивида = (1 , . .

. , ) .Случай1. = 0 и = 0 . Тогда рассматриваемый набор {︀}︀ и, согласно Лемме 2.2.1, являетсяфункции Предположим, чтотакже является нулем∪{ , }максимальным верхним нулем, потому что в противном случае мы бы получили,опять же, согласно Лемме 2.2.1, что(︂∃ ∈ max max )︂′⊆|·|∪{︀{ , }}︀: ′ > , ′ > ,и, по определению максимального верхнего нуля монотонной булевой функции,выполняется неравенство|supp (′ )| > |supp ()| ,что противоречит условию максимальности рассматриваемого набора.Следовательно, для случая 1 утверждение доказано:max0 Случай= max0 ∪{︀}︀ > max0 − 1 .{ , }2.

= 1 , = 0 .ребра { , } , набор Для определенности, пустьТогда при добавленииции∪{︀}︀{ , }снова является нулем функ­и, как показано выше, также и максимальным верхним нулемфункции.3. = 1 , = 1 .СлучайПустьТогда при добавлении ребранулем функции∪}︀ .{︀{ , }{ , }получаем, что наборне являетсяВ этом случае можем указать набор⎧⎨′ = ∀ ∈ [] ∖ {} ,′:⎩′ = 0 .Полученный набор′будет нулем функции∪построению, имеем:|supp (′ )| = |supp ()| − 1 ,{︀}︀ ,{ , }при этом, по50и по определению максимального верхнего нуля функции, имеем:max0 ∪{︀}︀ > |supp (′ )| = |supp ()| − 1 = max0 − 1 ,{ , }что и требовалось доказать.Следствие 2.2.2. Пусть заданы граф = ( () , ℰ ()) , и семейство по­парно различных ребер, не являющихся ребрами графа:{1 , 2 , . .

. , } ⊂(︀ () )︀2∖ ℰ () .Тогдаmax0 ∪ {1 ,2 ,..., }Доказательство.Применяя> max0 − .раз Утверждение 2.2.2 к графу,убеждаемсяв справедливости следствия.На основе Утверждения 2.2.2 можно модифицировать Алгоритм1 из Под­раздела 2.2.1 таким образом, что работа алгоритма будет продолжаться до пол­ного исчерпания вершин в остающемся множественульфункции ,0 , и при этом будет найдендля которого одновременно будет вычислена величинаmax0 − |supp ()|для оценки отклонения количества единиц в полученном наборе от количестваединиц в максимальном верхнем нуле функции.Алгоритм 2:Алгоритм ( , 0 ) .Входные данные: , 0 , ∈ []Выходные данные: 0 , Ind , = 0 для всех ∈ 0Ind = 0для ∈ 0 выполнять(︀)︀если − | ( , 0 )| , –вершина в ←− 1 ←− 0 для всех ∈ ( , 0 )0 ←− 0 ∖ ({ } ∪˙ ( , 0 ))Ind ←− 1конец циклаподграфе⟨0 ⟩ = ′ то51В Алгоритме 2 для данного значенияного множества0и для каждой вершины исход­осуществляется последовательная проверка, является лирассматриваемая вершина(︀| ( , 0 )| , )︀–вершиной.

Если таких вершин0 на выходе алгоритма= 0 , двоичный набор ненет, то никаких действий не производится и множествосовпадает с входным множеством, признак Indопределен. В случае, когда такая вершинаство0получается из входного множествавершиныи ее окрестности, Indпринимает значениеАлгоритм 3:0будет найдена, выходное множе­посредством «удаления» из него= 1 и соответствующая компонента набора1.Алгоритм ( , 0 ) .Входные данные: , 0Выходные данные: ∈ max ( )⊆пока 0 ̸= ∅ выполнять= 1пока (Ind = 1) & 0 ̸= ∅ выполнять ←− 0 ( , 0 )Ind ←− Ind ( ( , 0 ))Indконец циклапока (Ind = 0) & 0 ̸= ∅ выполнять ←− + 1 ( , 0 )Ind ←− Ind ( ( , 0 ))конец циклаконец циклаВ ходе реализации АлгоритмаАлгоритму2,3происходит непрерывное обращение кв результате выполнения которого формируется наборченный набор из множества нулей функцииАлгоритма.Полу­и является результатом работы3.Утверждение 2.2.3.

Пусть – (, )–вершина графа = ( () , ℰ ()) , ∈ () . Тогда существует набор ′ ∈ max ( ) такой, что ′ = 1 , и⊆52выполняется неравенство|supp (′ )| > max0 − .Доказательство. Пусть,рой вершины имеемпо определению{1 , 2 , . . . , } =∖2(︁ℰ () ∩графа, для некото­(︀ ( ) )︀)︁2, –вершиной в графе)︁⟨︀⟩︀ (︁1 ( ) = () , ℰ () ∪ {1 , 2 , . . . , } ,тогда вершина(︀ ( ) )︀(,)–вершиныявляетсяполученном добавлением рёбер в окрестности вершиныдо полного индуци­рованного подграфа.Согласно Утверждению 2.2.1, имеем для1 :∃ : = 1 , ∈ max max (1 ) ,|·|⊆и, согласно Следствию 3.2.2 из Утверждения 2.2.2, имеем также дляmax0 1Поскольку> max0 − .

∈ max max (1 ) ,|·|⊆1 :то|supp ()| > max0 − .По определению верхнего нуля функции, существует набортакой, что′ > ′ ∈ (1 )и, следовательно,|supp (′ )| > |supp ()| > max0 − ,что и требовалось доказать.В Алгоритме 1 поискпервой найденной –вершины, -вершины.в очередном цикле работы, ведется доТакой подход минимизирует число действий втекущем цикле работы алгоритма, но, возможно, дает не лучшее решение вслучае обращения к Алгоритму 3 в части оценки отклонения числа единиц вполученном наборе от числа единиц в максимальном верхнем нуле рассматри­ваемой монотонной булевой функции. Возможно, лучшая оценка может бытьопределена посредством реализации алгоритма поиска с возвратом, входнымиданными для которого является не множество вершин графа, полученное врезультате Алгоритма 1, а множество вершин исходного неориентированногографа конфликтов.53Поиск с возвратом.Алгоритм поиска с возвратом реализует на каждом ша­ге выбор вершины неориентированного графа, количественные характеристикикоторой являются наилучшими среди всех элементов текущего множества вер­шин.

Такой подход предполагает большее количество действий для каждоготекущего цикла, однако, можно ожидать более точное приближение к макси­мальному верхнему нулю.Алгоритм 4:Входные данные: , = 0Выходные данные: ∈ max ( ) , [оценка отклонения числа единиц в⊆полученном наборе отmax0 ]пока 0 ̸= ∅ выполнять ∈ 0 ̸= ∅ вычислить параметры , такие, что является ( , )–вершиной в графе ⟨0 ⟩ , в множестве 0 выделить′подмножество 0 ⊆ с минимальными значениями параметра . Среди′∈ 0′ с максимальнымвыделенных вершин 0 выделить вершину 0значением параметра ]0 ←− 1 ←− + 0{︀}︀0 ←− 0 ∖ { } ∪ ( , 0 )[для всех вершинконец циклаДля набора ∈ max ( ) ,⊆полученного посредством реализации Алго­ритма 4, справедлива оценка точности решения:max0 − |supp ()| 6 .Приведем оценку вычислительной сложности Алгоритма4.

из текущего множества 0 необходимо вычислитьколичество вершин в окрестности ( , 0 ) и количество рёбер, недостающих⟨︀⟩︀в окрестности ( , 0 ) , чтобы индуцированный подграф ( , 0 ) сталполным. Следуя определенному принципу, удаляем вершины ∪ ( , 0 )⟨︀⟩︀и рёбра ∈ { } ∪ ( , 0 )до полного исчерпания вершин в текущеммножестве 0 . Для входных данных заданной размерностиДля каждой вершины () = {1 , . . . , } ,ℰ () = {1 , . .

. , } ,54получаем следующую оценку.4 осуществляется не более итераций,в каждой из которых требуется не более () действий для вычисления пара­метров и , и не более () действий для операции исключения вершины иеё окрестности из текущего графа. Таким образом, Алгоритм 4 имеет вычисли­Всего за время работы Алгоритмательную сложность:(︀ )︀ ( · + ) = 2 .В некоторых случаях посредством параллельной реализации Алгоритма 3и Алгоритма 4 может быть получена точная оценка числа единиц в максималь­ном верхнем нуле рассматриваемой монотонной булевой функции.