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

1) Создать матрицу смежности (не бинарную)
2) Найти диаметр(сложить (1)+ (1)^2, привести к квадратной)
3) Возвести ее в квадрат (и так далее(3, 4, диаметр графа))

Определение связности графа.

Алгоритм определения связности графа.

Возводим матрицу S В n-ую степень

Здесь в матрице SⁿS_IJ- пути из V_iв V_j длиной n.

2. Если в матрице d’ нет нулевых элементов граф является связным (к=1), d(G)- диаметр графа - кратчайший путь между вершинами.

3.связность графа (X(G)) наименьшее число вершин, удаление которых делает граф несвязным.

Если X(G)=n, то граф называется n-связным.

Сильная связность графа.

Граф G = <V,U> называется сильно связным, если любая пара вершин соединена путем.

Максимальной по включению вершин сильно связанный подграф графа называется его компонентой сильной связности.

Граф называется несильно связанным, если число его компонент сильной связности больше 1.

 

Алгоритм порождения контуров в графе.

По очереди удаляете из графа рёбра. Если удаление ребра не приводит к появлению висячих узлов и не разваливает граф на две части, тогда ОК. Если приводит или разваливает — возвращаете ребро на место. Когда переберёте всё рёбра, граф превратится в дерево и удалёнными окажутся N рёбер. Это значит, что в графе N независимых контуров. Для каждого удалённого ребра строите по дереву путь, соединяющий его вершины. Вместе с самим ребром этот путь образует один из независимых контуров.

Определение сильной связности графа.

Алгоритм определения сильной связности графа и числа его компонент сильной связности графа:

Максимальная степень, в которую необходимо возвести матрицу смежности графа S(G) для определения компонент сильной связности равна диаметру d(G) этого графа:

D(g) = maxminl_k (u_i,u_j), где l_k (u_i,u_j) – длина пути от вершины u_i до вершины u_j.

Цикломатика

Для исследования циклов в графе используют цикломатическую матрицу C(G)=[c_ij­]: каждому циклу графа взаимно однозначно сопоставляется вектор-строка матрицы C(G); каждый элемент этой строки определяется как

1, если j-е ребро входит в i-й цикл,

0 в противном случае.

Базисом векторного пространства называются всякая система линейно независимых векторов, порождающая данное пространство. Любой вектор графа G может быть представлен в виде комбинации векторов базиса циклов.

Деревом называется связный граф, не содержащий ни одного цикла.

Остовный подграф графа – это подграф, содержащий все вершины графа.

Остовом называются остовный подграф являющийся деревом.

Хордой остова D в связном графе G называется всякое ребро графа, не принадлежащие D. Любой подграф состоящий из хорды и остова, имеет точно один цикл.

Цикломатическое число v(G) графа G равно числу хорд любого остова в G. Если связанный граф G имеет n вершин и m ребер, то v(G) = m – n + 1. Если граф G содержит k компонент связанности, то если цикломатическое число есть v(G) = m – n + k. Цикломатическое число определяет меру связности графа.

Лесом называется граф, не содержащий циклов. Иными словами, если граф состоит из нескольких компонент связности, каждая из которых является деревом, то данный граф является лесом.

Остовным лесом называется граф, каждая компонента которого является остовным деревом.

Цикломатический ранг x(G) (ранг разреза) – это число ребер в его остовном лесе. Количество базисных циклов в графе G определяется цикломатическим числом графа v(G).

Теорема №1 (Эйлер)

Число базисных циклов графа постоянно и равно его цикломатическому числу.

Часто матрицу инциденции А и цикломатическую матрицу С называют первой матрицей инциденций и второй матрицей инциденций.

Теорема №2

Вторая и первая матрица инциденций линейного графа G связаны операцией матричного умножения: C(G) xA(G) = 0(mod 2).

Базисная система разрезов образует базис в пространстве разрезов, или пространстве коциклов. Эта система может быть записана в виде соответствующей базисной матрицы разрезов, или базисной коцикломатической матрицы (хорды справа).

Теорема №3

Граф является двудольным тогда и только тогда, когда все его циклы имеют четную длину (четны).

В двудольном графе не обязательно каждая вершина из V₁ соединена с каждой вершиной из V₂, но если это так, то граф называется полным двудольным графом и обозначается K_m,n, где m – число вершин V₁, а n – число вершин V₂. Полный двудольный граф называется звездным графом (звездой, граф Кёнинга) и является деревом.

Коцикломатика

Коцикломатика (если спросят) – нахождение разрезов графа.

Разделяющим множеством связного графа называется такое множество его ребер, удаление которых из графа делает его несвязным.

Разрезом называется такое разделяющее мн-во, которое не имеет собственного разделяющего подмножества(коцикл).

Лес – граф, не содержащий циклов, т.е. если граф состоит из нескольких компонент связности, каждая из которых является деревом, то данный подграф является лесом.

Коциклический ранг χ(G) (ранг разреза) – это число ребер в его остовном лесе: χ(G) = n-k (n – кол-во вершин, k – количество компонент связности)

Теорема Эйлера: Число базисных циклов графа постоянно и равно его цикломатическому числу.

Алгоритм нахождения разрезов:

1) рисуем остов.

2) строим коцикломатическую таблицу (это когда сначала указываются ребра остова, а потом хорды)

3) по диагонали (в ребрах) выставляем единицы – базис. Дальше логика такая:
Удаляется ребро остова. Множество вершин при этом распадается на два непересекающихся подмножества V1 и V2. Множество всех ребер графа, каждое из которых соединяет вершину из V1 с вершиной из V2, является разрезом графа. Множество всех разрезов для каждого ребра остова является базисной системой разрезов для данного остова.

4) путем сложения разрезов из базиса (2^χ - χ -1 раз) порождаем все подмножество коциклов(разрезов) графа.

 

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

Продифференцировать граф 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).