Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 33
Текст из файла (страница 33)
Таблица, определяющая этот предикат Рз(Б), имеет 10 строк (по числу сочетаний из 5 по 3) и 6 столбцов (мощность предметной области): Каждое событие определяет некоторую двумерную двоичную матрицу Я = [де»)„,„„, каждому столбцу которой взаимно однозначно соответствует условие, входящее в событие, строке — совокупность условий, при которых событие имеет место (при которых 83.4, Дифференцирование графов и маграфаа 177 17б Гл. 3. 'Георив графов и мографоа ь 3('э) — 1)~ и ( 1, если уте условие входит в ь-ю совокупность в~= ~ условий, цри которых событие истинно, О в противном случае.
Другими словами, каждое событие определяет модель, матрнцей инцидентности которой является матрица ь/, т. е. условия, входящие в событие, являются буквами модели, совокуцности условий, цри которых событие истинно, — словами модели. Интенсивность участия условий (букв) в событиях (словах) будем характеризовать с ломошью частот их вхождения. Для этого введем частотную матрицу отношений Г = [Я„х„, характеризующую модель ьр, матрица инцидентности которой есть я(Ф) = = [Ьт)мха Частотпной мотрицгй отношений Г = [Лт]„ха называется матрица, каждой строке (столбцу) которой взаимно однозначно соответствует буква, и элемент Л равен числу слов, в которые входят буквы ь и у, если ь ф у, в противном случае (т = у) — числу слов, в которые входит буква ь'. При этом если ь = у, то Л вЂ” собстпвеннал частпотпа буквы, если же т ф у, то Л вЂ” взаимнал частота бука ь и я.
Из определения частотной матрицы отношений Г = [Я„х„ следует, что она сама симметрична относительно главной дйагонали, т. е. Л = /тч, и что собственная частота любой буквы не меньше взаимной частоты этой буквы с любой другой буквой: Л ) Лт. Можно показать, что частотная матрица отяошений Г, характеризующая модель, матрица инцидентности которой Я удовлетворяет соотношению () хЯ =г', (3.3) где Я вЂ” транслонированная матрица Я ( — знак транслоннрования матрицы).
Определим степень участия компонент графа 0 в наперед заданном событии д в графе ьх, другими словами, стелень неоднородности компонент графа относительно заданного события. Будем характеризовать эту неоднородность производной д0/дд графа ьг" цо событию 5. Производной д0/дЯ графа С по событию д называется не- ориентированный взвешенный граф (К ((/, Р)), носитель которого совладает с носителем модели, определяемой этим событием, и пара вершин (и;, и.) взвешена отношением частоты (Л вЂ” Л ) + +(Л вЂ” Л.) их несовместного участия к частоте Л.
совместного участия в событии 5: дьх Л вЂ” 2/ьу + /, (3.9) дЯ Лт причем: (и;, и.) ф У, если (дС/дд)(и;, о ) = оо; (и;, о ) Е (/, если (00/дд)(о;, и ) — конечная величина, отличная от нуля; о; = о, если (д0/д5)(и;, ит) = О. Значение выражения (3.9) называется значением производной но ребре (иб и.). Проиллюстрируем понятие производной от графа цо событию на двух примерах.
Пример'3.3. Пусть заданы граф С (см. рис. 3.8,а), и событие Я вЂ” образование ребрами остова графа С. Йайдем производную ат графа С по событию Я, паторая будет харавтеризавать интенсивность у тастня ребер в образовании остовов графа С. Заданное событие определяет модель, матрипа иннндентностн догорай имеет слелуюший внд: з 6 с Ы е 1 1 1 1 О 1 1 О О 1 1 О 1 1 О 1 О 1 О 1 1 О О 1 1 О 1 1 1 О О 1 1 О 1 О 1 О 1 1 а 6 с 4 е 5 2 2 3 3 2 5 2 3 3 2 2 4 2 2 3 3 2 5 2 3 3 2 2 5 :Элементы этой матрипы апрелеляюг дС/дб, представляюшую собой граф, но- ситель ваторого — (а, Ь, с, тт, е), и дзе вершяны этого графа смеины, если ана- Чвние производной на дуге, образуемой этими вершинами, отлично от нуля и йесвонечностн. Вычисляя аначения производной дС/дб на ребрах графа: +/ь 5 — 2 ° 2+ 5 — 3, 2 +/е 5 — 2 2+4 2 +Уе 5 — 2 2+5 — 3, 2 дС(а 6) Уеэ дС /. 2/., до ( а с ) дС „ / -2/м ддд ' Ли Получаем граф дС/дя (см.
рис. 3.8,а). Пример 3.4. Рассмотрим граф С (рис. 3.9, а), иа лотаром аадано событие И вЂ” абрваование ребрами бааисного пилла относительно остова С' (рнс. 3.9, б) графа С. Вы тислим производную от графа С па событию Я. В этой махрипе ваидому столбпу заанмно однозначно саответстзуег ребра „'графа С (условие, вхоляшее в событие), стропе — сововупнасть ребер, абрааую'6тьих остов графа (сововувность условий, при ваторых ааданное событие имеет сто) (см. рис, 3.8, б). Частотная матрипа отношений Г, соатветствуюшзя марице Я, есть 13.4. Дифференцирование графов и мографов 179 Гл.з. Теория графов и мографоа 178 Пивламетичесвое числа и(С) графе С равна 3: и(С) = яз — я +» = 7 — б + 1 ~ 3. Следовательно, граф садернит 3 базисных днвле.
Событие д авределяет модель виде а Ь с И е г Л 0 0 1 1 1 1 0 Этой мавели саапмтствует частотная мзтридв отношений а Ь с И е г Л 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 1 3 3 2 1 1 З З 2 1 1 2 2 2 1 0 0 О 1 1 1 1 0 0 0 1 1 0 0 1 Р = (Уз х С( ю Вычисляя значение вранзвадной, волучзем граф дС/дд (рнс. 3 9, а). Аиали- Рис. 3.9 д20 д (дОз( дЯедЯЬ дЯа ~дЯЬ/ зируя граф дС/дд, замечаем, нзврнмер, по ребра с и а (или ребра а и Ь) одиневово интенсивна участвуют в заданном событии. Таким образом, для определения производной от графа 0 по событию 5 необходимо: а) построить модель, определяемую заданным событием; б) найти частотную матрицу отношений, соответствующую этой модели; в) вычисляя по частотной матрице отношений значения производной на ребрах графа (уС//дЯ, построить искомый граф д0/дЯ, характеризующий интенсивность участия элементов графа 0 в заданном событии Я.
Производной д»Сз/дЯ» й-го порядка по событию Я называется производная от производной (/с — 1)-го порядка по тому же событию 5: Смешанной производной по событиям Я, и Яь называется производная по событию Я, от производной по событию Яь. Аналогично определяются смешанные производные от графа 0 по событиям Яы 52, ..., Я„. Введенное понятие производной от графа 0 по событию Я дает возможность находить производную и от модели зр(ц) (от мографа (з(ЬУ)(о)).
В случае определения производной от модели, если событие 5 не оговорено, в качестве Я будем считать "образование буквами слова". Значение производной от модели (от мог рафа Ф~) (Я)) на паре (з, 2) есть где частоты /(, /( и // определяются цо частотной матрице отношений Г = [/(/) (Р = я х я). на мографе 0(лу) частоты /(, /и и /у равны соответственно числу весов вершины и;, числу общих весов вершин и(, иу и числу весов вершины и;. Пример 3 б. Вычислим Зурь ((зп ез), (ез, ез)), где магреф С(м) задан не рис. 3.10, а, событие Бз есть событие в обычном ваннмении (т. е.
"образование Дуввзми слова"), событие дз есть "обра'зование вилле нечетной длины в графе ~д'С(м)/дд = (т; С()з е з2 зе Мвтрилз нндилентнасти Цп зедею- 13 1 с 1,3 шея магреф С(~( (рис. 3.10, а), имеет вид ' ~!'~6 Соатветствуюшзя ей частотная метриде отношений г = (3т х (г челове: а Ь с е 1'1 1 0 гз= 1 2 1 1 1 1 2 1 0 1 1 2 Значения вранзводной дС(~1/ддз соответственно равны дС(м( дС(м> дС(м( — (а,Ь)=1, — (Ь,с)=2, — (а,с)=1, доз ' ' доз ' ' ддз дС(ьо дС(м( дС(м( — (Ь,И)=2, — (а,й)шао, — (с,й)=2, ддз ' ' ддз ' ' ддз Хреф дС(~(/ддз нзобренен нв рис. 3.10, б. Событие Бз в графе дС(~1/ддз задает метрилу Цз вида (епсз) (зз,ез) (спев) (зз ее) (Ю ее) Ф=)( 1 1 1 о о 180 Гл.З. Теория графов и мографов 13.4.
Дифференцирование графов и мографов 181 Согласно влтогитмт пах«пленил лрсивлолноя ст трвав ивхояим (»$»$) (»$ сь) (с\ »$) ($П »$) (»$ \$$) 1 1 О О 1 1 О О 1 2 1 1 О 1 1 1 О 1 1 1 дг ~(м) 1 — 2 1+1 — ((оь, от), (от, вь)) = = О. ддь ддя ' ' ' 1 Мы рассмотрели равномерность участия пар элементов в событии 5. Аналогично можно рассмотреть равномерность участия троек, четверок и т. д., и-к элементов в событии 5. Для вывода формулы производной на 3, 4, ..., п элементах обобщим понятие частотной матрицы отношений.
Введем понятие частотной гиперматрицы отношений. Рассмотрим модель )Р = (М, Я1, 52, ..., Яь). Возьмем Ф-мерную матрицу Р = '(Ль' ...'„) (ы 12, . 1)$1 = 1, )М). Позиции по каждому измерению Ф-мерной матрицы перенумеруем числами натурального ряда 1, 2, ..., )М). Каждой букве тп й М поставим во взаимно однозначное соответствие номер из этого натурального ряда и расположим буквы т; б М по соответствующим позициям каждого измерения Ф-мерной матрицы.
Каждый элемент /1$<,„2„ этой матрицы равен числу слов, в которые входят буквы, соответствующие номерам $1, 12, ..., 1))1. Олинаковые индексы в написании не дублируем. Построенную таким образом матрицу будем называть 1)$-мерной частотной матрипей отноияений или (еслн нас не интересует размерность этой матрицы) часпюьпной гиперматрипей отноиьгний. Если среди индексов 11, 12,..., 1)$1 у элемента /1$1$,.з„есть хотя бы два индекса различного написания, то этот элемейт называется взаимной частопюй соответствующих букв, в противном случае — собственной частотой этих букв. Частота /1;2 .;и, имеющая )Ь различных индексов, называется частотой л-го йорядна. При вычислении производной для пары элементов использовались частоты первого и второго порядка.
Производная дС/дЯ графа С по событию 5 на тройках эле- ментов: дС 1 — )-.,-.,-.)= ( 1: .— д5 " ' ' У ..„, $$$$«»,$«$,$«$ — 2 ~~ь А; -)- 3 ° ~ /1 ь, (3.10) $1»с«$» $«Ь $вс $$ЪЬ=«$».»$$ $«с 1 ф у, ь ф )с, у ф Ь. Р($Р) = 1 1 0 1 0 1 2 1 2 0 0 1 2 2 1 1 2 2 3 1 0 0 1 1 1 Производная дс. /дЯ графа С по событию 5 на четверках элементов: дьх 1 — (т»$ ть$ тс$ тг) = / ~ /1- Лв»«$$$«$«ья Л + 3 ~ь Л вЂ” 4 ~ Лум, (3.П) $$3 ьа)ь $11)ь,) ь, у,)с$1= тп, ть,тс$ тг$1 ~ 2$ ь ~ )с$1 »ь 1$ у тс )с$ у Ф ($ й уь (. Производная дС/дЯ графа С по событию 5 на и элементах: дс» — (гУ;,— 211,$ 1 /$«$»$$..$«» ° $ пня +(-1)"".'Х: Л,;....;.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
