razdel2_dmat_10

Метод Магу для нахождения максимальных внутренне устойчивых подмножеств орграфа

Пусть U - максимальное внутренне устойчивое множество вершин в орграфе D=(V,X), A(D)={a_ij}- матрица смежности орграфа D. Каждой вершине v_iорграфа поставим в соответствие булеву переменную y_i по следующему правилу: если v_i U , то y_i = 0 (или =1).

Тогда для любых двух вершин v_i, v_j(ij) выполняется: если вершина v_i  U, а v_jГv_i (ij), то вершина v_j U . Запишем это выражение с помощью логических связок, учитывая при этом, что, если v_jГv_i, то a_ij = 1, а если v_j  Гv_i , то a_ij = 0. В результате получим (y_i&a_ij)   1. Преобразуем это выражение:   1 или    1.

Рассмотрим конъюнкцию по всем вершинам

= (   )  1.

Если a_ij=0, то =1, 1 =1 и эту дизъюнкцию можно опустить. Если a_ij=1, то =0 и 0 =  . Тогда

= (  )  1.

Раскрывая в данном выражении скобки и пользуясь законом поглощения А  (А&В)  А, приведем данную формулу к ДНФ. Тогда каждый дизъюнктивный член … даст внутренне устойчивое множество, причем это множество образуют те вершины, которые не входят в данный член. Т.к. каждый дизъюнктивный член содержит только переменные с отрицанием, то к множеству U нельзя добавить ни одной переменной y_i, содержащейся в элементарной конъюнкции, а значит, каждое множество U является максимальным внутренне устойчивым множеством.

Пример.

Найти максимальные внутренне устойчивые множества вершин для орграфа D, заданного матрицей смежности

Решение.

Запишем формулу Ф для данного орграфа

Ф= (  )=(  )(  )(  )(  )(  )(  )1.

Упростим эту формулу, пользуясь законами А&А=А, А(В&А)=А, А(В&С)=(АВ)&(АС)

Ф=(  )(  )(  )

(    )(  )

      

  )

    1.

В результате имеем четыре внутренне устойчивых множества: {v₂,v₄}, {v₁,v₄}, {v₂,v₅}, {v₃,v₅}.

Содержание