17) Дифференцирование графов.

Продифференцировать граф G по событию S – построить производную графа G по событию S.

Событие – процесс, происходящий при выполнении определенных условий.

Каждое событие определяет матрицу инцедентности Q , столбцами которой являются условия, а строками – события. Q=[q_ij]=1(если условие участвует в образования события) или 0 (иначе).

Чтобы продифференцировать граф по событию S, нужно:

1)Построить модель, определяемую заданным событием.

2)Построить частотную матрицу отношений F=[f_ij]_n*n –матрицу, каждой строке(столбцу) которой взаимно однозначно соответствует условие и элемент f_ij , равный числу событий, в котором входят условия i и j (если i не равен j, иначе (при i=j) f­_ij равен числу событий, в которых участвует условие i). При этом, если i=j , то f_i – собственная частота условия, а если i<>j, то f_ij – взаимная частота условий i и j. Частотная матрица отношений F симметрична относительно главной диагонали.

F=Q^T*Q.

3)Построить производную графа G по событию S- неориентированный взвешенный граф <V,(U,P)>, носитель которого совпадает с носителем модели, определяемой этим событием, и пара вершин (v­_i,v_j) взвешена отношением частоты их несовместного участия к частоте совместного участия в событии S.

- значение производной на ребре

(v_i,v_j).

Билет №18: Порождение полных подграфов графа

Полный граф – граф, каждая вершина которого соединена ребром с остальными. Все вершины смежны.

Плотность графа – максимальная мощность носителя полного подграфа

1) Каждая пара вершин смежна.

2) При добавлении хотя бы 1-ой вершины свойство 1 нарушается.

Алгоритм порождения полных подграфов

1. Сопоставляем корню синтезируемого дерева заданный граф.

2. Фиксируем в графе вершину U₀ c максимальной степенью, сопоставив ее концу исходящей из корня дуги. Строим , исходящих из корня дуг ( -мощность носителя неокрестности вершины u_o). Конец каждой из этих дуг взаимно однозначно сопоставляем вершине неокрестности .

3. Каждый конец u_α построенных дуг взвешиваем окрестностью G(u_α) вершины u_α графа, сопоставленного рассматриваемому корню.

4. Считаем конец u_α построенного яруса корнем нового дерева.

5. Устанавливаем, взвешена ли вершина u_α символа . Если нет, то переходим к п.2, если да, то к п.6.

6. Пути между концами дуг, исходящих из корня синтезированного дерева, и висячими вершинами однозначно определяют полные подграфы заданного графа.

ЗАКОН ПОГЛОЩЕНИЯ:

Если k-м ярусе дерева вершины U_i , U_j смежны, поддерево с корнем U_i построено и если в поддереве с корнем U_j появляется дуга с вершиной U_i, то соответствующая ветвь не строится.

19)Внутренняя устойчивость графа. Порождение вершинно пустых подграфов.

Множество внутренней устойчивости графа — это множество несмежных вершин.

Максимальным множеством внутренней устойчивости  называется внутренне устойчивое множество, добавление любой вершины к которому, делает это множество неустойчивым.

В каждом графе без петель и кратных рёбер можно выделить семейство

Ψ = {ψ₁, ψ₂, ..., ψ_i}

всех внутренне устойчивых подмножеств. Эти подмножества различаются количеством входящих в них элементов. Число внутренней устойчивости η(G) определяется мощностью внутренне устойчивого подмножества, содержащего наибольшее число элементов, т.е. характеризует максимальное число несмежных вершин графа:

η(G) = max | ψ_i |

Пример: граф, представленный на рис. 22, имеет: Ψ_i = { Ψ₁, Ψ₂, Ψ₃, Ψ₄, Ψ₅}, Ψ₁ = {x₁, x₄, x₆}, Ψ₂ = {x₂, x₅}, Ψ₃ = {x₂, x₆}, Ψ₄ = {x₃, x₄, x₅}, Ψ₅ = {x₄, x₅}. Число внутренней устойчивости η(G) = 3.

Рис. 22

Иногда по аналогии с числом внутренней устойчивости рассматривают число внутренней полноты χ(G), которое определяет максимальное число вершин графа G, образующих полный подграф. Для графа G, представленного на рис. 22, семейство внутренне полных подмножеств имеет вид:

Φ = {φ₁, φ₂, φ₃, φ₄,}, φ₁ = {x₁, x₂, x₃}, φ₂ = {x₁, x₃, x₅}, φ₃ = {x₂, x₄}, φ₄ = {x₅, x₆},

а число внутренней полноты χ(G) = max |φ_i| = 3,φ Φ.

Очевидно, что поиск максимальных внутренне устойчивых множеств путем простого перебора является неэффективной процедурой, поэтому для поиска максимальных внутренне устойчивых множеств существует специальный алгоритм — алгоритм Магу.

Алгоритм Магу состоит из следующих этапов:

1.            Для графа составляется матрица смежности.

2.            По таблице смежности выписываются все парные дизъюнкции.

3.            Выражение приводится к ДНФ.

4.            Для любой элементарной конъюнкции выписываются недостающие элементы, которые и образуют множество внутренней устойчивости.