Как найти определитель графа

Рассмотрим модель СУ, структурная схема
которой представляет собой сильно
связный граф (см. рис. 8.1). Кроме этого,
будем считать, что отсутствует (либо
игнорируется) информация о входах и/или
о выходах системы. Таким образом, в
данном случае имеем дело с моделью
“собственно системы”. При задании
модели СУ дифференциальным уравнением
аналогом модели собственно системы
является однородное уравнение. Оно
образуется приравниванием нулю правой
части исходного уравнения, в которой
как раз и присутствует входная координата.
Решение же однородного уравнения
определяет собственные движения системы
и, следовательно, устойчивость СУ
(см.разд.2).

Фундаментальной
характеристикой такой модели, формируемой
на основе анализа структуры системы,
является определитель графа.

Определитель графа представляет собой следующую конструкцию,
составленную из передач контуров:

.(8.1)

В
этом выражении присутствуют следующие
группы слагаемых:

	сумма передач всех контуров графа;

 	сумма произведений передач всех пар некасающихся контуров;
сумма произведений передач всех троек попарно

Формирование определителя заканчивается,
когда перечислены все возможные
комбинации из попарно некасающихся
контуров; четные комбинации (пары,
четверки и т. д.) суммируются со знаком
“+”, а нечетные (одиночные контуры,
тройки, пятерки и т. д.) – со знаком “”.

В качестве
примера сформируем и запишем в символьном
виде определитель графа, структурная
схема которого представлена на рис.8.1:

 = 1 – K₁
–K₂–K₃–K₄–K₅–K₆–K₇–K₈
+

+K₁K₆+K₁K₇+K₁K₈+K₂K₈+K₄K₆+K₄K₈+K₅K₆+K₅K₇+K₅K₈+K₆K₇+K₆K₈+K₇K₈
–

– K₁K₆K₇
– K₁K₆K₈
– K₁K₇K₈
– K₄K₆K₈
– K₅K₆K₇
– K₅K₆K₈
– K₅K₇K₈
– K₆K₇K₈

+ K₁K₆K₇K₈+K₅K₆K₇K₈
.

В результате,
определитель этого графа содержит 31
слагаемое.

Можно
заметить, что для формирования троек и
последующих слагаемых определителя
уже можно обойтись без состава контуров;
достаточная информация заложена в
перечне пар некасающихся контуров.
Действительно, для того чтобы пары K_iK_jиK_iK_lобразовали тройкуK_iK_jK_l,
необходимо в перечне пар найти также иK_jK_l.
Причем строгий лексикографический
порядок следования индексов позволяет
при генерации последующих слагаемых
анализировать только те комбинации,
которые отличаются последними индексами.
Эти особенности дают возможность
существенно повысить эффективность
формирования определителя графа.

При задании операторов блоков структурной
схемы передаточными функциями
W_i(s)=B_i(s)/A_i(s)
передача каждого контура является
дробно-рациональной функцией. Если в
(8.1) подставить передачи контуров и
произвести необходимые алгебраические
действия, то определитель графа также
будет приведен к дробно-рациональной
функции:

 =(s) =A(s)
/A_Р(s)
. (8.2)

В выражении (8.2)
A_Р(s)
– “характеристический полином полностью
разомкнутой системы”; он равен
произведению знаменателей передаточных
функций всех звеньев рассматриваемого
графа.

Полином числителя
A(s)определителя
графа 
представляет
собой характеристический полином
контурной части системы. Поэтому
определитель графа является характеристикой,
отвечающей за устойчивость СУ.

Соседние файлы в папке ОСНОВЫ ТЕОРИИ УПРАВЛЕНИЯ

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

  01.05.201449.21 Кб55ZURICHI.TTF

Анализ свободных колебаний систем с конечным числом степеней свободы приводит, как известно, к приравниванию нулю частотного определителя, после развертывания которого образуется частотное уравнение, степень которого соответствует числу степеней свободы рассматриваемой системы. При большом числе степеней свободы развертывание определителя в общем (буквенном) виде связано с серьезными вычислительными трудностями. С другой стороны, известно [6], что характеристический полином системы, как и определитель графа, равен сумме величин деревьев графа  [c.59]

Такое соответствие между факторами графа и чле-нами определителя его матрицы смежностей неслучайно. Можно доказать, что и в общем случае определитель матрицы смежностей (определитель графа) равен  [c.103]

Очевидно, значение определителя А, стоящего в знаменателе (3.13), совпадает со значением определителя графа, матрицей смежностей которого является а[1 3, 1 3] (см. рис. 3.2, а). Ясно также, что граф, соответствующий определителю Д], отличается от графа на рис. 3.2, а только тем, что дуги, идущие в вершину /, вместо весов ац, ai2, <213 имеют веса bi, 62. Ьз-Однако такой подход нельзя признать рациональным. Дело в том, что он требует для решения системы уравнений построения двух графов одного — для определителя, стоящего в числителе, а другого — для определителя в знаменателе. Оказывается, можно построить единый направленный граф системы уравнений, по которому в результате выделения путей и факторов и находится решение системы.  [c.106]

Находим определитель графа Г —шь Существует только один фактор, состоящий из петли [(04, 04] и контура [о)2, шз, 2]. поэтому det(r —(Di) = (—1)2йй(/= = bdf. Для отыскания числителя формулы (3.17) выделяем все пути от (Bi к (й2 и соз, имеющие в качестве дополнения непустой фактор [(Оь <02], [соь (04, (О2],  [c.114]

Находим определители графов  [c.138]

Таким образом, для того чтобы найти факторы графа скоростей Ги, необходимо построить структурное число графа Гщ —юе, у которого удалена вершина 0, раскрыть его и выписать соответствующие подстановки. Цикловые структуры этих подстановок определят соответствующие факторы графа. После этого нетрудно найти определитель графа, стоящий в знаменателе выражения (3.17).  [c.150]

Объединение множеств — 10 Определитель графа — 103 Отображение — 10  [c.214]

Определитель графа потока сигналов может быть записан следующим образом  [c.383]

Вычисляем определитель графа  [c.384]

Для проверки правильности составления структурного числа А вычислим число деревьев графа, равное определителю некоторой матрицы [9]  [c.58]

Иначе говоря, число различных деревьев графа равно определителю матрицы, в которой на пересечении г-й строки и г-го столбца указывается число ребер, инцидентных вершине, а на пересечении г-й строки и /-Г0 столбца — взятое со знаком минус число ребер между вершинами i и /. При составлении указанной матрицы рассматриваются все вершины графа, кроме вершины — корня дерева.  [c.58]

Использование направленных графов при решении линейных уравнений основано на тесной связи между структурой графа и структурой определителя его матрицы смежностей [2, 3].  [c.101]

Отметим важное соответствие между членами определителя в выражении (3.10) и всеми возможными факторами графа, изображенными на рис. 3.2,6 — ж. Оказывается й-й член определителя в точности равен весу k-ro фактора графа. При этом выполняется равенство  [c.102]

Таким образом, формулы (3.9) и (3.11) обозначают одно и то же число, только (3.9) записана через матричные элементы, а (3.11)—через элементы соответствующего графа. Однако между этими формулами есть и существенная с точки зрения организации вычислений разница. Формула (3.9) согласно определению определителя содержит zl слагаемых. Если среди элементов матрицы некоторые а,-,- принимают нулевое значение, то в (3.9) существуют слагаемые, равные нулю. Тем не менее при расчетах по формуле (3.9) с помощью ЭВМ машина будет оперировать с нулями в точности так же, как с ненулевыми элементами. В отличие от (3.9), в формуле (3.11) суммирование ведется по всем имеющимся факторам графа. И если какой-то член определителя равен нулю, то соответствующий фактор графа просто отсутствует.  [c.104]

Для примера вернемся к графу, изображенному на рис. 3.1, а. Так как z = 4, то определитель его матрицы смежностей содержит 4 = 24 члена. Однако из них только два ненулевых, которые соответствуют факторам, представленным на рис. 3.1,6, в, поэтому определитель этого графа равен  [c.104]

Эффективность использования формулы (3.11) тем выше, чем больше нулей содержит матрица. Это утверждение справедливо при одном условии если задача выделения факторов из графа решается проще, чем непосредственное отбрасывание нулевых членов определителя в формуле (3.9) другими способами. Применительно к ЭВМ этот вопрос рассматривается в гл. 4, сейчас же покажем, что даже при ручном подсчете больших определителей использование формулы (3.11) при некотором навыке может дать большую экономию времени, несмотря на то, что человек способен при пользовании выражением (3.9) сразу отбрасывать целые совокупности нулевых членов определителя.  [c.104]

Определитель системы уравнений совпадает с определителем матрицы смежностей А графа на 110  [c.110]

Теперь найдем это же самое отношение из графа Г с помощью формул (3.19) и (3.20). Из рис. 3.9, в видно, что граф Г не имеет ни одного контура, поэтому, согласно формуле (3.19) его определитель равен единице, и есть только один путь от (04 з- б]- Отсюда  [c.123]

Теперь получим тот же результат из графа Г (рис. 3.10, в) не содержащего контуров, с определителем, равным единице Выделяем все возможные пути из 0)4 к a>s. Их три [со , M , соз,  [c.124]

Таким образом, если определитель системы уравнений (3.24) и (3.25) не равен нулю, то она имеет единственное решение, которое, в частности, может быть найдено с помощью направленных графов. Внутрен-. ние моменты на других звеньях легко находятся по формулам  [c.132]

Теперь проделаем то же самое с помощью графа Мэзона. Для этого выполним над структурным графом систему операций QJ . В результате получим граф, изображенный на рис. 3 13,6. Так как он не имеет контуров, то согласно (3.19) его определитель равен единице, поэтому  [c.135]

Такие же результаты получим, если воспользуемся графом Мэзона (рис. 3.14,6). Он имеет два независимых (имеющих общие верщины) контура и поэтому его определитель равен  [c.137]

Основные практические трудности, возникающие при реализации графовых моделей на вычислительных машинах, связаны с выявлением в графах путей и факторов, с помощью которых находятся отдельные члены определителей матрицы системы уравнений. Эту трудность можно обойти, воспользовавшись теоретико-множественным описанием графовых моделей и соответствующими им структурными числами [2. 3].  [c.145]

Таким образом, раскрытие произведения структурных чисел графа равносильно отысканию его факторов. Это становится очевидным, если вспомнить, что каждый фактор соответствует некоторому члену определителя системы уравнений, причем всякий член определителя является произведением элементов матрицы с различающимися между собой вторыми индексами. С другой стороны, при раскрытии структурного числа выписываются столбцы с различными номерами, которые тоже по существу являются вторыми индексами, но только ненулевых элементов той же матрицы. Отсюда ясно, что операция перемножения элементарных структурных чисел равносильна выделению систем различных представителей из семейства множеств, стоящих в структурном числе справа от вертикальной черты и разделенных между собой горизонтальными линиями.  [c.149]

В этой таблице через X обозначен урожай пшеницы (ц/га) в разных хозяйствах района, а через у — себестоимость 1 пшеницы (руб.). Чтобы облегчить вычисление вспомогательны величин, значения независимой переменной X сокращены Н1 К—8, полученные результаты помещены во второй графе х табл. 126. Используя суммы из табл. 126, находим значения определителей системы О = 7-1,4784— (2,386) = 10,3488 — —5.6930=4,6558 Л=50,6-1,4784—21,80-2,3860 = 22,7922 Б = =7-21,80—50,6-2.3860=31,8684. Отсюда а=Л/ )=22,77/4,65= =4,895 й=В/ >=31,868/4,656=6,8445. Эмпирическое уравне ние гиперболы второго порядка оказывается следующим  [c.284]

При удалении путей дз, L в графе остается тот же цикл и определители Ддз и равны АВ удалении пути в графе остаются оба цикла, следовательно, его опреде-  [c.384]

Ю4, Юз, < i] 5) [Ю4, Ю2, Ю1]. Пусть <7 —вес 5-го пути, а rs — определитель графа, полученного из первоначального графа в результате удаления всех вершин, входящих в 5-й путь. Тогда сумма — ) + Zsqsrs по всем возможным путям от Ю4 к Ю1 оказывается в точности равна определителю (3.11), у которого вместо flu, й2, 31 стоят соответственно bi, Ь , Ьз, т. е. 108  [c.108]

В отлнчие от предыдущих примеров, здесь вместо переменной (Об, соответствующей верщине-источнику (шв =1), стоит переменная 0)4. В этом случае определитель графа Гщ—ив равен сумме весов двух факторов один из них состоит из пяти петель, а другой—из трех петель при вершинах oi, m2, Ws и контура [ша, 0)4, мз]. Их веса соответственно равны (—1) (—1) ( г) (13) (1) X X (-1) =-1Уз и ( 1) -1)(12)(-1)(-1)(-1) =/2. Далее, от вершины (Об к вершине (05 имеется только один путь [(OeOis] весом I l. Аналогично графу Гщ — (О граф Гщ— [(05(05] также имеет два  [c.125]

Сначала найдем моменты с помощью графа Коутса. Для это го подсчитаем значение определителя графа  [c.136]

В случае кривой поверхности параметризуется геометрическая часть определителя. На рис. 121 прямой круговой цилиндр задан параметрами положения в пространстве oxyz двух направляющих окружностей. Алгоритмическая часть определителя включает алгоритм построения образующей, параллельной oz и пересекающей направляющие окружности. На рис. 122 а и б) показаны параметрические графы цилиндра. На рис. 123 изображен соответствующий размерный граф.  [c.190]

Таким образом, на всех стадиях определения скоростей и моментов используется один и тот же алгоритм, позволяющий легко автоматизировать весь процесс вычисления. Его основной недостаток состоит в том, как уже отмечалось выше, что он производит много лишних действий, связанных с умножением и сложением нулей при вычислении определителей ред-козаполненных матриц. Применение направленных графов и соответствующего математического аппарата [2, 21] дает возможность избавиться от этого недостатка и тем са.мым значительно сократить машинное время решения задачи.  [c.98]

Преобразованный описанным способом двудольный граф для системы (3.14) изображен на рис. 3.4,6. Он отличается от графа определителя (ЗЛО) только наличием вершины 04 и выходящих из нее дуг (сравните с рис. 3.2, а). Полученный граф будем называть графом Коутса. Таким образом, если подсчитать по формуле (3.11) определитель матрицы смежностей полученного графа (без вершины Ю4, соответствующей столбцу свободных членов), то он как раз совпадает с определителем Д из формулы Крамера (3.13).  [c.108]

Для подсчета определителя Д1 сделаем следующее. Найдем все возможные пути от вершины (й4 (эта вершина всегда является источником, так как она не объединяется ни с какой из М-вершин двудольного графа) к вершине мь В графе на рис. 3.4,6 их пять  [c.108]

Найдем сначала значение 5/0)4 по графу Коутса. Как и в предыдущем примере, его определитель равен произведению весов пяти петель (—1) (—1) (—I) (г г) (1 — з) (—I) = 2(1 — з). Для подсчета числителя выражения соб/а)4 ищем пути из вершины 4 к 0)5. Их три [ 4, 2, 1, Ш5], [о)4, 0)з, 2, 1, б] И [ 4, з, 0)1, о)б]. Веса путей соответственно равны (—1)(1 —12) (1—-м) =  [c.123]

Выписываем сначала определитель полученного графа Коутса det = (- ) (/,) (-1) (-1) (к) (1) (-l) =-ii/j.  [c.135]

Структурные числа матриц, или матричные структурные числа, как и структурные числа графов, в конечном счете используются для подсчета определителей редкозаполненных матриц, т. е. матриц с большим числом нулевых элементов.  [c.155]

Заметим, что несмотря на одинаковую запись структурных чисад матрицы и графа, переход от номеров структурных чисел к элементам определителей матрицы у них осуществляется по-разному. Если область определения отображения, порождаемого структурным числом матрицы, соответствует первым индексам элементов матрицы, а область значений — вторым индексам, то для структурного числа графа область определения — это множество вершин графа, откуда исходят дуги фактора (пути), а область значений — множе ство вершин, куда входят эти дуги. В связи с этим члены определителя в случае использования структурных чисел матриц записываются непосредственно по соответствующим отображениям, а при использовании структурных чисел графов получаемые отображения служат для определения путей и факторов графа. Члены определителя получаются уже как сумма весов дуг, входящих в эти пути и факторы. Имея это в виду, найдем те же выражения для отношений Xk/Xi не из графа Г, а непосредственно  [c.161]

Допускается не наносить на чертеже номера позиций для составных частей, являю-цихся элементами электрической принципиальной схемы, записанных в специфика-1ИЮ изделия в разделах Стандартные изделия и Прочие изделия . Эти элементы определяют по позиционному обозначению, указанному на чертеже на изображении эле-1ента и в спецификации изделия в графе Примечание . Это допущение удобно ис-[ользовать на сборочном чертеже платы или панели, а также для проводов и кабелей, аписанных в спецификации изделия в разделе Материалы . Это допущение удобно, ели применяют провода и кабели одной марки. В остальных же случаях номер пози-,ии является определителем марки соответствующего провода или кабеля.  [c.157]

Контур г-го порядка — совокупность г несоприкасаюшихся контуров первого порядка, у которых нет общих узлов. Контур первого порядка — обычный контур, определение которого дано в этом разделе. Величина называется алгебраическим дополнением для А -го прямого пути графа. Значение А равно определителю подграфа, который не соприкасается (не имеет общих узлов) с А -м прямым путем.  [c.136]

Удаляя из графа найденные пути с принадлежащими им вершинами, находим цлклы в остающихся графах и вычисляем определители этих графов. Как вя яо, при удалении пути Г-АВ оставшемся графе имеется цикл (Ох, 5, О,, 4) с передачей 1,94, Опредетнтмь оставшегося графа  [c.384]

---

Определитель — граф

Cтраница 1

Определитель графа AX1 H состоит из.
 [2]

Определитель графа А согласно правилу циклов вычисляется следующим образом.
 [3]

Определитель графа А и передаточные функции Wni и Wn2 были получены выше. Так что достаточно вычислить определители AI и А2 подграфов прямых путей.
 [4]

Определитель графа равен нулю. Передачу можно найти, преобразовав граф относительно узла / ( рис. РЛЙ.
 [5]

Определитель графа представляет собой знаменатель выражения передачи графа. Представим определитель графа несколько иным способом и затем установим его связь с передачей графа.
 [6]

Однако определитель графа в целом не меняется: все отрицательные знаки компенсируются знаками других слагаемых, что должно быть в случае энергетической пассивной системы.
 [7]

Вычислить определитель графа Коутса рис. 16.23, считая, что определитель графа рис. 16.21, задачи ШЛ 4 известен.
 [8]

А — определитель графа, соответствующего исследуемой системе; Р — — прямые пути, Afc — соответствующие им миноры; индекс а означает исключение ветви, содержащей варьируемый параметр a; F — обратная разность, вычисленная в этой ветви; F — нулевая обратная разность. Для широкого класса структур модели, соответствующие логарифмич.
 [10]

А — определитель графа; РЬ — величина k — ro пути в графе от источника до стока; Д — алгебраическое дополнение пути. Суммирование выполняется по всем возможным путям.
 [11]

А — определитель графа; Afe — алгебраическое дополнение, равное величине определителя части графа, не касающейся &-го пути.
 [12]

А — определитель графа, соответствующего исследуемой системе; Pk — прямые пути, Л — соответствующие им миноры; индекс a означает исключение ветви, содержащей варьируемый параметр a; F — обратная разность, вычисленная в этой ветви; F — нулевая обратная разность. Для широкого класса структур модели, соответствующие логарифмич.
 [14]

При вычислении определителя двунаправленного графа посредством многократного применения формулы разложения ( 11 — 11) выявляются все однонаправленные деревья графа с общим корнем. И, обратно, определитель графа может быть получен путем выявления всех его однонаправленных деревьев с общим корнем и суммирования произведений коэффициентов, соответствующих только одному направлению передачи каждой из ветвей этих деревьев.
 [15]

Страницы:  

   1

   2

   3

УДК 519.1

АЛГОРИТМ ВЫЧИСЛЕНИЯ ОПРЕДЕЛИТЕЛЕЙ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ С ПОЛНЫМИ ЗАТРАВКАМИ, СОХРАНЯЮЩИХ СМЕЖНОСТЬ СТАРЫХ РЕБЕР

Байрамукова Зухра Халитовна

UDC 519.1

ALGORITM OF CALCULATION OF DETERMINANTS OF PREFRACTAL GRAPHS WITH THE FULL PRIMERS, KEEPING OLD EDGES CONTIGUITY

Bayramukova Zuhra Halitovna

Кочкаров Ахмат Магометович д.ф.-м.н., профессор

Северо-Кавказская государственная гуманитарнотехнологическая академия, Черкесск, Россия

Kochkarov Ahmat Magometovich Dr.Sci.Phys.-Math., professor

North-Caucasian State Humanitarian Technological Academy, Cherkessk, Russia

В статье получен алгоритм — рекуррентная формула для вычисления определителей предфрактальных графов с полными затравками, сохраняющих смежность старых ребер в траектории

Ключевые слова: БАЗИСНЫЕ ФИГУРЫ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ, ОПРЕДЕЛИТЕЛИ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ

In the article, the algorithm — a recurrent formula for calculation of determinants of prefractal graphs with the full primers, keeping old edges contiguity in a trajectory was received

Keywords: BASIC FIGURES OF PREFRACTAL GRAPHS, DETERMINANTS OF PREFRACTAL GRAPHS

В настоящее время бурно развивается раздел дискретной математики, направление — спектральная теория графов [1] , основанный на

алгебраических инвариантах графов — его спектрах. Спектральная теория графов позволяет выявить зависимость между спектральными и структурными свойствами графов, характеризовать графы спектрами. Что позволяет разработать приложения спектрального метода как в самой теории графов, так и в комбинаторике, в физике при исследовании физических моделей, в которых спектры графов имеют важное самостоятельное значение. В настоящее время теоретико-графовые (топологические) подходы приобрели для прикладных задач большое значение. Как известно, задачи, структура которых меняется во времени и, более того, размерность этих задач изменяется во времени (увеличивается), можно моделировать с помощью предфрактальных и фрактальных графов [2], [3]. При исследовании сетей больших

размерностей изменяющихся во времени — так называемых больших и малых миров также моделируют с помощью предфрактальных и

фрактальных графов [4]. Чтобы выявить связи между спектральными и структурными свойствами предфрактальных графов необходимо вычислять определители их матриц смежности.

А также при исследовании многих задач математического программирования [5], задач экономики с определением балансов [б], в задачах теории графов [7] часто приходится вычислять определители. Например, в задачах линейного программирования [8], чтобы найти решение систем линейных уравнений ограничения с использованием метода Крамера, необходимо вычислять определители матриц коэффициентов системы ограничения. А в теории графов вычисляются определители матриц смежностей для определения тех или иных инвариантов графов. Как только задачи становятся большой размерности, вычисление определителя усложняется.

В настоящей работе рассматривается вычисление определителей матриц смежностей предфрактальных графов [9] с полными затравками, смежность старых ребер которых в траектории не нарушается. Приведем в начале несколько понятий, часто применяемых в данной работе.

Термином затравка условимся называть какой-либо связный граф H = (W,Q). Для определения фрактального (предфрактального) графа [9], [l0],[ll] нам потребуется операция замены вершины затравкой (3В3). Суть операции 3В3 заключается в следующем. В данном графе G = (v , E ) у намеченной для замещения вершины ~ є V выделяется множество V = {~ }çV, j = l,2,…,V~, смежных ей вершин. Далее из графа G удаляется

вершина v~ и все инцидентные ей ребра. Затем каждая вершина V- єV,

j = l,2,…,V соединяется ребром с (одной и той же, если смежность старых

ребер сохраняется) вершиной затравки H = (W, Q).

Предфрактальный граф будем обозначать через GL =(vl , EL ), где VL -множество вершин графа, а EL — множество его ребер. Определим его

рекуррентно, поэтапно заменяя каждый раз в построенном на предыдущем этапе l = 1,2,…,L-1 графе Gt = (V¡,Et) каждую его вершину затравкой H = (W, Q). На этапе l = 1 предфрактальному графу соответствует затравка G1 = H. Об описанном процессе говорят, что предфрактальный граф Gl =(vl , el ) порожден затравкой H = (W, Q). Процесс порождения предфрактального графа GL , по существу, есть процесс построения последовательности предфрактальных графов G1,G2,…,GL называемый траекторией. Для предфрактального графа Gl , ребра появившиеся на l-том l є {1,2,…, l} этапе порождения, будем называть ребрами ранга l. Новыми ребрами предфрактального графа GL назовем ребра ранга L, а все остальные ребра назовем — старыми.

Если из предфрактального графа GL, порожденного и-вершинной затравкой H , последовательно удалить все старые ребра (ребра ранга l , l = 1,2,…, L -1), то исходный граф распадется на множество связных компонент {fi^}, каждая из которых изоморфна [7] затравке H. Множество компонент {^j[i)} будем называть блоками первого ранга. Аналогично, при удалении из предфрактального графа GL всех старых ребер рангов l = 1,2,…,L — 2, получим множество блоков {fi^} второго ранга изоморфных предфрактальному графу G2. Обобщая, скажем, что при удалении из предфрактального графа GL всех ребер рангов l = 1,2,…,L — r, получим множество {bL)}, r є {1,2,…,L -1} блоков r-го ранга изоморфных предфрактальному графу Gr. Измененным блоком r-го ранга мы будем называть блок r-го ранга, из которого удалена одна вершина затравки и все инцидентные ей ребра.

«Элементарной фигурой» [1] называется : а) граф K2 (ребро) или б) любой граф Cq, q > 1 (простой цикл); «базисной фигурой» и называется любой граф, все компоненты которого являются элементарными

фигурами. Кп1 (с, р) — число базисных фигур с п1 вершинами в предфрактальном графе О1, К*п1 (с, р) — число базисных фигур с п1 -1

вершинами в измененных блоках, имеющих с простых циклов и р компонент.

Для вычисления определителей в данной работе используется Лемма [1].Определитель матрицы смежностей графа О = (V,Е) с N вершинами вычисляется по формуле

А = (-1^ I(-1)р(и)2с(и),

и е.и N

где р(и) — число компонент, с(и)- число простых циклов, содержащихся в и, а UN означает множество всех базисных фигур, содержащихся в графе

О = (V, Е) и имеющих точно N вершин.

В результате применения леммы к предфрактальным графам, получена

Теорема. Определитель матрицы смежностей А1 предфрактального графа О1 с полной п -вершинной затравкой н = (Ж, 0 вычисляется по формуле

|А,| = (- 1)п’ I(- I)р2сКп,(с,р).

Суммирование ведется по множеству чисел базисных фигур с N = п’ вершинами, которое определяет формула

п /

Кп1 (с,р) = I ПКп,’-1 (а,,А,)+

1а =с 1=1

IА■=р

п-1 п—] )

+ I I К]Л(а, А) Сп ПКп,’—1 (а,,А )ПКп’—1 (у,3,) +

}=2 a+Ia,.+Iу =с ,=1 ,=1

А+IАi +Id =р + I Кп1 (а,А)П<‘—1 (у, ,3,)

a+Іуi =с ,=1

А+Ш, = р

и

n—1

Ki(c, p) = Z K*n,i—і (a р)П к„,і—і (a, Д- )+

2 a+a=c i=1

Z b+b=p

n—1 j n—j

+ Z Z Kj—1,1 (a, РС3—1 П K„J—1 (g, d )n Kni—1 (a, b ). +

j=3 Za+Zg +a=c i=1 i=1

Z b+Zd+b=p

+ Z Kn—1,1 (a, ЬЙ<і—1 (g ,d )•

a+Zg =c i=1

b+Zdii=p

Доказательство. Условие теоремы предполагает, что определены множества Kni—1(c,p), K*nl—1(c,p). С увеличением l в предфрактальном графе

появляются новые вершины и новые ребра, то есть его форма усложняется. Для того чтобы систематизировать процесс нахождения чисел базисных фигур Knl (c, p), используем схему:

1) в базисных фигурах графа Gl с nl вершинами отсутствуют ребра 1-го ранга (нет измененных блоков);

2) из старых ребер 1-го ранга сохранено одно ребро (два измененных блока);

3) из старых ребер 1-го ранга сохранен цикл С3 (три измененных блока);

п) из старых ребер 1-го ранга сохранены базисные фигуры затравки(имеется п измененных блоков).

Для подсчета числа базисных фигур по каждому пункту схемы используем правило умножения из комбинаторики. Суммируя количества базисных фигур с равным числом циклов с и компонент р из всех пунктов схемы, получаем

кпі(ср) = X Пк«,/-М,Д)+

Ха =с і=і

ІЛТ^ІЛі-г Xі

Д+ХД + Х8і =р

+ X к>,ь)п<і-і(Гі Л)

а+ V V =с і=1

Здесь каждая сумма получена в соответствующем пункте схемы.

Для вычисления к* (с, р) используем схему:

1) в базисных фигурах нет ребер 1-го ранга (один измененный блок і -1 — го ранга);

2) в базисных фигурах имеется одно ребро 1-го ранга (три измененных блока і -1 — го ранга);

3) имеется цикл С3 из ребер 1-го ранга (четыре измененных блока

і -1- го ранга);

п-1) из ребер 1-го ранга в базисные фигуры измененного блока і — го ранга входят базисные фигуры затравки с п -1 вершинами.

Отсюда следует формула

*

кпі(^ Р) =

п-1

X кП,і-1 (а,Д)П кп,і-1 (а,Д)+

і=1

І п-І

п к*,і-1(у Л )П кпЛ-1(а, Д). +

і=1

і=1

+ X кп-1,1 (а,Д)П<і-1 (V ,Л).

і=1

Теорема доказана.

Вычислим, к примеру, |л2| при п = 4. По теореме имеем:

определитель матрицы смежностей предфрактального графа G2 с полной четырехвершинной затравкой н = (Ж, 0 вычисляется по рекуррентной формуле

И =(- 1)42 I (- 1)Р 2 СК 42 (с, р ) ,

где

K42 (c, p) = X П K41 (а,ß)+

Xa =c i=1

Xßi = Р

iНе можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

3 4- j j

+ X X Kji(a,ß) • C4 • П к 41 (a ,ß )n k*^- ,d)+

j=2 а+Ха + Хп =c i=1 i=1

ß+Xß + Xd =p

+ X K41(a,ß)n K*1(n ,d)

a+Xn =c i=1

ß+Xdi = p

K 41 (c, p) принадлежат множеству всех чисел базисных фигур этапа l = 1, а K *1 (c, p) — множеству всех чисел базисных фигур в измененных блоках. Пусть l = 1. Рассматриваем граф G1 (рис.1).

Рис.1.

Построим все базисные фигуры в графе G1 с 4-мя вершинами

(рис.2).

Рис.2.

Первые три фигуры имеют 0 циклов и 2 компоненты, т.е. К41(0,2) = 3. Остальные три-1 цикл и 1 компоненту, К41(1,1) = 3 . Т.о. по лемме получаем

|41 = (-1)4 (з(-1)220 + 3(-1)121 )= -3 Пусть I = 2. Рассматриваем граф 02 (рис.3) по схеме:

Рис.3.

1) в базисных фигурах графа 02 с N = 42 = 16 вершинами отсутствуют ребра 1-го ранга (нет измененных блоков) (рис. 4а));

2) из старых ребер 1-го ранга сохранено одно ребро (два измененных блока) ( например, рис. 4 б));

3) из старых ребер 1-го ранга сохранен цикл С3 (три измененных

блока) (например, рис.4в));

4) из старых ребер сохранен либо цикл С4 или два ребра, не имеющих общую вершину (4 измененных блока) (рис. 4г)), т.е. базисные фигуры затравки.

Рис.4.

Т.о., все базисные фигуры графа с 16 вершинами содержатся в графах этих 4-х видов.

1) К42 (c, Р) = Е П К41 («/, Д )

Еа =с І=1 ЕД=р

где К41 (а, Д )є {К41 (с, Р )}={К 41 (0,2), К41 (1,1)}={3,3},

К 42 (0,8) = К 41 (0,2) = 34 = 81,

К42 (1,7) = К41 (1,1)К41 (0,2) К41 (0,2)К41 (0,2)+

+ К 41 (0,2) К 41 (1,1) К 41 (0,2) К 41 (0,2)+

+ К 41 (0,2) К 41 (0,2) К41 (1,1) К 41 (0,2) +

+ К41 (0,2)К41 (0,2)К41 (0,2)К41 (1,1)= 4 • 3 • 33 = 324,

К 42 (2,6) = С 4 К 41 (0,2)К421 (1,1)= 6 • 34 = 486,

К 42 (3,5) = С1К 41 (0,2)К431 (1,1) = 324,

К 42 (4,4) = К 41 (1,1)= 34 = 81;

2) к 42 (с, Р) = Е С42К21(0,1)П К41(а ,Д )П КІ1(Уі а ),

Еа + =с і=1 і=1

ЕД+Еаі +1=р

К *1 (ГІ Аі )=К 31 (1,1)=1;

Е 42 (2,7) = К41 (0,2)К321 (1,1)С42 = 3 • 3 • 4 = 54 К42 (3,6) = 2К41 (0,2)К41 (1,1)К321 (1,1)С42 = 108 ,

К42 (4,5) = К421 (1,1)К 321 (1,1)С42 = 54.

3) К 42 (с, р) = Е С43К31(1,1)П КМ А) К^аД)

Е ^ +а+1=с І=1

Е5і +Д+1=Р

к 42 (4,6) = С4 К 3, (1,1)К 41 (0,2)К3, (1,1) = 12,

К42 (5,5) = С4К31 (1,1)К41 (1,1)К3 (1,1) = 12 .

4

*

4) К 42 (с, р) = Е К41 (а,Д)П К’М ,А)

а+ЕГі =с

д+ЕАі=р

К 42 (4,6) = К 41 (0,2)К 31(1,1) = 3.

К 42 (5,5) = К 41 (1,1)К ¿(1,1) = 3.

2=1

Таким образом,

К 42 (0,8) = 81, К42 (1,7) = 324, К42 (2,6) = 486, К42 (3,5) = 324, К 42 (4,4) = 81, К42 (2,7) = 54,

К 42 (3,6) = 108, К 42 (4,5) = 54, КА2 (4,6) = 15, КА2 (5,5) = 15.

Следовательно,

|Л42| = (-1)16(81(-1)820 + 324(-1)721 + 486(-1)622 + 324(-1)523 + 81(-1)424 +

+ 54(-1)722 +108(-1)623 + 54(-1)524 + 15(-1)624 + 15(-1)525 =-375.

Задача вычисления определителей матриц смежности

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

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

затравками, сохраняющих смежность старых ребер в траектории. Для

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

способ (лемма [1]), основанный на рассмотрении структуры графа.

Полученный алгоритм упрощает процесс вычисления, поскольку при его

использовании нет необходимости рассматривать ни матрицу смежности

предфрактального графа, ни его структуру, и сводит к работе с

множеством чисел базисных фигур предыдущего этапа траектории.

Список литературы:

1. Цветкович Д., Дуб М., Захс Х. Спектры графов: теория и применение. Наукова Думка. Киев.1984. 384 с.

2. Кочкаров А.А., Сенникова Л.И. Количественные оценки некоторых связностных характеристик предфрактальных графов. // Прикладная дискретная математика. -2011.№ 4(14) -С. 56-61.

3. Кочкаров А.А. Структурная динамика: свойства и количественные характеристики предфрактальных графов. — М.: Вега-Инфо, 2012.- 120 с.

4. Кочкаров А.А. Новые теоретико-графические подходы в моделировании сложных систем: Автореф. дис. … канд. физ.-матем. наук . М.: ИПМатем. им. М.В. Келдыша. РАН, 2005. 24с.

5. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование.-М.: Высшая школа,1980. 302 с.

6. Малыхин В.И. Математика в экономике.-М.: ИНФРА-М.2000. 356 с.

7. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. -М.:Наука,1990. 384 с.

8. Ашманов С.А. Линейное программирование. — М.: Наука,1981. 340 с.

9. Кочкаров А. М. Распознавание фрактальных графов. Алгоритмический подход.-Нижний Архыз: РАН САО.1998. 170 с.

10. Байрамукова З.Х., Кочкаров А.М. Спектры предфрактальных графов с затравками -циклами, сохраняющих смежность старых ребер.// Научный журнал КубГАУ. №81(07). 2012 года. 10 с.

11. Кочкаров А. А., Кочкаров Р. А. Параллельный алгоритм поиска кратчайшего пути на предфрактальном графе. // Журнал вычислительной математики и математической физики. — Т. 44. № 6.-С. 1147 — 1152.