автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Модели и алгоритмы решения задач математической физики на ориентированных графах и их приложение в квантовой механике

; г 5 од

I 7 ОПТ 1998

На правах рукописи

СТЕПОВОЙ Дмитрий Владимирович

МОДЕЛИ И АЛГОРИТМЫ РЕШЕНИЯ ЗАД МАТЕМАТИЧЕСКОЙ ФИЗИКИ НА ОРИЕНТИРОВАННЫХ ГРАФАХ И ИХ ПРИЛОЖЕНИЕ В КВАНТОВОЙ МЕХАНИКЕ

05.13.16. - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (автоматика, вычислительная техника и автоматизация)

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Росгов-на-Дону 1998

Работа выполнена в Ростовском государственном университете.

Научный руководитель - кандидат физико-математических наук,

профессор Ерусалимский Я. М.

Официальные оппоненты - доктср физико-математических наук,

доцент Угольницкий Г. А.;

кандидат физико-математических наук, доцент Басангова Е. О.

Ведущая органшация- Кабардино-Балкарский

государственный университет.

Защита диссертации состоится" ^ " МЛ^^ьЛ 1998 г. ъ 4 "1 часов на заседании диссертационного совета К 063.52.12 при Ростовском государственном университете по адресу: 344090, г. Ростов-на-Дону, проспект Стачки 200/1, корп. 2, ВЦ РГУ. к. ¿/Об.

С диссертацией можно ознакомиться в библиотеке РГУ по адресу: ул. Пушкинская 148.

9

Автореферат разослан У " П&Л-и-дЬЛ 1998г.

Ученый секретарь диссертационного совета К 063.52.12,

кандидат физико-математических наук,

старший научный сотрудник /Муратова Г.ВУ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность исследования. В последние годы в связи с бурным развитием науки и техники, областей, относящихся к высоким технологиям (квантовая механика, микроэлектроника, композитные материалы, компьютерные сети и т. п.), особую актуальность приобрели классические задачи (теплопроводности, распространение колебаний и др.) в неклассической постановке. При этом в этих задачах эффективно работают методы теории графов. Диссертационная работа посвящена обоснованию применяемых графовых подходов и разработке алгоритмов решешш краевых задач для классических уравнений математической физики на ориентированных графах.

В последнее время появился ряд работ, посвященных исследованию дискретного аналога оператора Лапласа на неориентированных графах и приложением этих исследований к задачам случайного блуждания частицы по кристаллической решетке, задачам распространения тепла или колебаний по решетке, возникновению и развитию микротрещин в композиционных материалах. В этих работах изучается спектр оператора Лапласа, рассматриваются отношения между спектром лапласиана и геометрией графа, а также выявляются свгпи между спектром оператора Лапласа на всем неориентированном графе и его спектром на подгра фах, рассматриваемого графа. Изучаются вопросы существования гармонических, суб- и супергармонических функций на графах и рассматриваются некоторые их свойства.

Вместе с тем, вопрос об изучешш оператора Лапласа на ориентированных графах остается практически не затронутым, хотя практические приложешш теории графов, как правило, реализуются именно на ориентированных графах.

Целью работы является обоснование и разработка алгортгтмов решения задач, порожденных оператором Лапласа, для дискретных аналогов

классических уравнений математической физики на ориентированных графах.

Научную новизну работы определяют следующие результаты, полученные автором:

1. Сформулирован и доказан принят максимума для субгармонических функций на орграфах.

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

3. Сформулирована и доказана теорема существования и единственности решения задачи Дирихле, порожденной оператором Лапласа, на орграфах с прогрессивно конечной конденсацией.

4. Предложен метод декомпозиции решения задачи нахождения спектра оператора Лапласа.

5. Введена в рассмотрение функция Грина и получена ее связь с амплитудой Грина комплексной марковской цели. На основе этой связи предложен новый метод нахождения амплитуды вероятности для дискретного аналога фейнмановской теории квантовой механики на ориентированных графах.

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

7. Приведена схема решения краевой задачи Дирихле на конечных орграфах и ее реализация в виде паскаль-программы.

Практическое значение работы заключается в следующем:

- рассмотрены приложения полученных результатов для гармонических функций на орграфах в квантовой механике, в частности, предложен эффективный меггод нахождения амплитуда вероятности;

- на основе уравнения теплопроводности на орграфах рассмотрена модель, позволяющая проводить расчет средних температур в системе тел,

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

Апробация работы. Результаты, изложенные в диссертации, докладывались на международной конференции "Нелокальные краезые задачи и родственные проблемы математической биологии, информатики и физики" (Нальчик, 1996), на V международной конференции "Математика. Экономика" (Ростов, 1997), на научной конференции по итогам научно-исследовательской работы (АЧГАА, Зерноград, 1995-1998), на семинаре кафедры алгебры и дискретной математики РГУ (1998).

Публикации. Основные результаты диссертации опубликованы в

[1-6].

Объем и структура диссертации. Работа состоит ил введения, четырех глав, четырех приложений и списка литературы (59 наименований) изложенных на 121 странице машинописного текста, в т. ч. 24 рисунка.

Благодарности. Автор от души благодарит своего научного руководителя к. ф.-м. н., доцента Ерусалимского Я. М. за постоянную заботу и помощь при работе над диссертацией, а также выражает свою признательность к. ф.-м. н., доценту Хейфицу А. И. за идею и привлечение интереса автора к данной теме.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Под ориентированным графом С=(Х,Г) понимаем упорядоченную пару, состоящую из непустого множества X и многозначного отображения Г множества X в X. Здесь и далее ориентированный граф будем называть просто графом, при этом всегда предполагаем, что граф является связным. Напомним1 некоторые поняли и определения.

Определение I. Пусть дан граф С=(Х,Г) , и пусть г^Х, тогда граф г) называют подграфом , индуцированным множеством Ъ.

Траго1гтивньш замыканием отображения Г называется следующее отображение Г множества X в X :

Г(*)= Ми {Г(лг)}и {Г2(*)}и {Г3(х)}и....

Множество {Г(*)} назовем множеством достижимости вершины х.

Определение 2. Говорят что вершина у достижима из вершины х, если уеГ(х). Очевидно, что если вершина у достижима из х, то существует путь [*,>•].

Граф С называется сильно связным, если любые две его вершины достижимы друг из друга.

Нетрудно видеть, что отношение взаимной достижимости вершин графа С=(Х,Г) рефлексивно, симметрично и транзитивно. Следовательно, мы получаем разбиение множества X на классы, объединив в один класс все вершины, достижимые друг из друга. Подграфы, индуцированные классами этого разбиения, и только они, являются компонентами сильной связности графа О.

Пусть {Х.1, Кг,..., Ко} - множество всех компонент сильной связности графа О. Конденсацией графа в называется граф С, вершины к|, кг,...,

'см. тахже Берж К. Теория графов и ее применения. - М.: ИЛ, 1962.

кщ которого соответствуют компонентам сильной связности графа О, и пара (к (, ку ) является дугой в О* тогда и только тогда, когда в С есть дуга,

начало которой принадлежит компоненте К(, а конец - компоненте Ку.

Пример 1. На рис. 1 приведен граф О я его конденсация О*.

в*

Рис. 1.

Определение 3. Граф в=(Х,Г) называется Г-конечньтм, если |Г(х)| < ао для всех х еХ.

Говорят, что граф прогрессивно конечен в вершине х, если в этом графе не существует путей бесконечной длины, начинающихся в х; граф, прогрессивно конечный в каждой своей точке, называется прогрессивно конечным.

Для заданного графа 0=(ХХ) рассмотрим множества

Х(О)={*|Г(*) = 0},

Х(1)={*|Г(х)с:Х(0)},

ад = {*}Г(х) с: *(*-!)},

а<е>

Х(о> + 1) = {х|Г(х)сХ(й>)}.

ясно, что эти определения можно продолжать неограниченно: если а- порядковое число первого рода, то полагаем

Х(а)={х|Г(х)сХ(а-1)}, а если а- порядковое числовторого рода, тол слагаем

Х(а)=[}Х{0).

р<сс

Заметим, что если два порядковых числа а и 0 удовлетворяют условию а<{5, то Х(а)сХ(Р).

Порядком вершины * называется наименьшее порядковое число а, для которого х еХ(а), х еХ(Р) при всех р<а.

Полагаем а=о(х); разумеется некоторые вершины могут не иметь порядка: к таким относятся, например. все вфшины контура.

Функция о(х), определенная вообще говоря не на всем X, называется порядковой функцией графа.

Пример 2. У графа, изображенного на рис. 2, каждая вершина х имеет порядок о(х), который указан на чертеже; лишь одна вершина у имеет трансфинитный порядок. Здесь Х=Х(ш+1).

у ш+Л

Определение 4. Будем говорить, что компонента сильной связности К

графа G имеет порядок а, если o(j>)=a, где у- вершина конденсации графа G, соответствующая компоненте К.,

Определение 5. Множество Х„ -{х еХ: о(х) = л}, где о(х)- порядковая функция графа G=(X,Г)> назовем n-ым кольцом графа G.

Введем пошгтиятраницы и внутренности графа. Вершина х графа G называется граничной, если подграф, индуцированный множеством Г(х), сильно связен. Множество всех граничных вершин графа G называется границей и обозначается oG. Вершина графа, не являющаяся граничной, называется внутренней. Множество всех внутренних вершин графа G называется внутренностью и обозначается intG.

4

Пример 3. Для графа С, изображенного на рис. 3, ипО={1,2;, сЮ={3,4,5.6,7}.

Не всякий граф имеет границу или внутренность. Например, сильносвязный граф не имеет внутренности, поскольку каждая его вершина является граничной. А на рисунке 4 изображен граф, не имеющий границы.

1 2 3 4 5

--> . У ■ ■ ■ ->!!.... >------

Рис. 4.

Замечание 1. Очевидно, чтс границу графа й составляют все вершины, входящие в компоненты сильной связности графа нулевого порядка.

Оператор Лапласа на ориентированном графе С=(Х,Г) задается следующим образом:

уеГ(х)

здесь функция /:Х->К; вес р(х,у)>0 задан на каждой дуге (х,у)^С и удовлетворяет н^авенстау

(1)

уеГ(х)

для всех * из X. Иногда навеса оператора Лапласа накладывается более жесткое ограничение:

(2)

усГ(лг)

В случае, когда р(х,у)=Ш+(х) на каждой дуге (х,у), мы имеем классический лапласиан:

О 1*^еГ(х)

здесь (3+(х)=1 Г(х)| - полустепень исхода вгршины х, т. е. число дуг, исходящих из х.

Определение 6. Функцию / (х): будем называть гармонической на графе в, если (ДР / )(х)=0 для любого I из X такого, что Г(*)*0; и гармонической внутри графа О, если (Др/ ДМ любого х еЫО.

Определение 7. Функцию /; Х-^И будем называть субгармоничесжой (супергармонической) на графе О, если (Др/Х*)£0 ((Др/)(х)20) для любого х еХ такого, что Г(х}*0. Также функция /(х) является субгармонической

(супергармонической) внутри графа G, если (Д?/)(х)>0 ((Др/)(х)<0) для любого х eintG.

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

Определение 8. Функцию /: X-»R будем называть траготивно постоянной в вершине х <зХ графа G~(X,IT). если f (у) = / (х) для всех вершин уеГ(х).

Теорема 1. (Принцип максимума) Субгармоническая функция, не являющаяся транзитивно постоянной ни в одной вершине г = {X \ Х(0)} графа G, не может достигать своего наибольшего значения на этом множестве вершин графа.

Следующая теорема дает оценку значений субгармонической функции внутри графа.

Теорема 2. Пусть граф G~(X,T) не содержит бесконечных компонент сильной связности, причем его конденсация является прогрессивно конечным графом, и пусть функция / субгармонична внутри графа G. Тогда

sup f(x) = sup /(г).

хчХ zecG

Доказан так же дискретный аналог неравенства Гарнаха на орграфах.

Теорема 3. Пусть функция / : X~»R+ супсргармоническая на графе G=(X,r), тогда для каждой дуги (х,у) выполняется неравенство

f(x)>V(x,y)f(y).

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

Теорема 4. Для любого графа G=(X,r) и любой пары функций / ,g:

X—справедливо равенство:

хеш С уеГ(х)ЫаС

У€Г{х)псС

- {х)).

(3)

хешС

хеЫС? уеГ(хУ\Ыв

Равенство (3)- это дискретный аналог первой формулы Грина. Здесь также получена и вторая формула Грина:

£ (хХ/(*)Дг« - £МЛ/(*)) = 2(/М£00-£М/0>)). (4)

Равенство (4) справедливо для любого графа С и любых функций / Х->К.

Четвертый параграф пссвящен задаче Дирихле на орграфах. Пусть С=(ХД") граф и Др- лапласиан на нем. Сформулируем задачу Дирихле:

Найти функцию / (х) гармоническую внутри графа <3 и совпадающую на границе дй с заданной функцией <р(£), т.

Функцию ср(0 будем называть траничной функцией или граничными данными задачи Дирихле.

Теорема 5. ( Теорема существования и единственности решения задачи Дирихле) Пусть граф 0=(Х,Г) не содержит бесконечных компонент сильной связности, причем его конденсация является прогрессивно конечным графом, и пусть на границе графа О задана ограниченная функция <р(£). Тогда задача Дирихле, порожденная оператором Лапласа Др, имеет решение и оно единственно.

Следствие. Пусть на границе конечного графа 0-(Х,Г) задана огра-

хелС

хёяв уеГ(х)

Ар/(дг) = 0, хеЫв;

(5)

ниченная функция фЮ, тогда задача Дирихле для графа в имеет решение и оно единственно.

Определение 9. Под границей компоненты сильной связности

К = ,г( Хк | графа С=(Х,Г) будем понимать множество вершин

Пример 4. Пусть Хк={ 1,2,3,4}- множество вершин компоненты К графа О, изображенного на рис. 5, тогда ¿АГ={8,6,5}.

Замечание 2. Из структуры графа, удовлетворяющего требованиям теоремы 5 следует, что находить решение задачи Дирихле можно последовательно от границы графа, сначала для компонент сильной связности с порядком единица, затем с порядком два и т. д. На каждом шаге для очередной компоненты возникает локальная краевая задача, причем для этой локальной задачи границей считаем границу компоненты, а внутренностью- все вершины рассматриваемой компоненты.

Рис. 5.

Замечание 3. Из доказательства теоремы 5 следует , что решение локальной задачи Дирихле для произвольной компоненты сильней связнссг равносильно решению соответствующей системы линейных алгебраически: уравнений. Поэтому решение задачи Дирихле на всем графе сводится к последовательному решению таких систем.

Во второй главе изучается спектр оператора Лапласа на орграфах.

Здесь рассматривается задача на собственные значения для оператора Лапласа

ГАГ + У = ' (6)

1 /и=0- (7)

Обозначим решения задачи (6)47) Брес(Д). Пусть 0=(Х,Г> граф такой, что его конденсация является прогрессивно конечным графом. В работе доказано, что в этом случае 8рес(Д)сг(0,2).

Рассмотрены некоторые частные случаи.

Пусть С=(Х,Г) прогрессивно конечный граф, тогда

Брес(Д)£{1}. (8)

В частности доказаны следующие теоремы.

Теорема 6. Пусть 0=(Х,Г) - пжный прогрессивно конечный граф такой, что подграф, индуцированный множеством ¡тНй, является однородным степени однородности <1=1, причем не существует вершины хеХ : Г-'(х)=0, тогда для графа С задача (6)-(7) не -¡мест решений, т. е. 5рес(Д)=0.

Напомхшм, следуя [Берж], что конечный граф С=(Х,Г) называют пра-деревом с корнем х|еХ, если

1) в каждую вершину «1 заходит одна-единственная дуга;

2) в х I не заходит ни одна дуга;

3) граф С не содержит контуров.

Теорема 7. Пусть С=(Х,Г) - конечное прадерево, тогда 8рес(Д)={1}.

В общем случае нахождение решения уравнения (6) с граничным условием (7) равносильно решению СЛАУ:

(1 -Я)/(Х>- Хмх,у)/О')=0, где хеыа (9)

у<^Г(х)г,ЫС

Поэтому решение задачи (6>{7) сводится к нахождению собственных значе-. ний матрицы А где

ы-

1, i-Ji

-p{x„xj), Xj cT{Xi)nmtC-, (10)

0, (i j) л (xj г Г(x,) n int G).

Размер матрицы Л равен числу внутренних верцвш графа G. Очевидно, что нумерация вершин роли не траст, поскольку изоморфным графам сосгпзег-стеугог подобные матрицы, дта которых множества собственных значений совпадают.

Во втором параграфе второй главы приведен метод декомпозиции решения задачи нахождения спектра лапласиана.

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

Для каждой компоненты сильной связности К графа G рассмотрим локальную задачу (6)-(7). При этом для этой задачи внутренностью считаем все вериишы компоненты К, а границей- грзтщу компоненты (см. определение 9). Обозначим Spec(A)i множество решений локальной задачи (6)-(7)

*

для компоненты Kj графа G.

Обобщим понятие симметрической разности для произвольного конечного или бесконечного набора множеств.

Определение 10. Симметрической разностью произвольного набора

множеств Xjt i е/, будем называть множество состоящее из элементов х, каждый из которых принадлежит только одному из множеств X, н не принадлежит ни какому другому.

Пример 5. Пусть Xi= {1,2,3}; Х2= {2,4,5};Хз={1,2,5,7}, тогда

+Х,={3,4,7}.

Пусгь К(,1 е/ компоненты сшп>ной связности графа й. Связь между спектром оператора Лапласа на всем графе О и его спектрами на отдельных компонентах сильной связности дает следующая теорема.

Теорема 8. Для произвольного графа О с прогрессивно конечной конденсацией справедливо следующее соотношение

-^-в^Д), с5рес(Л)еи^д)с (Н)

I

Исходя го этой теоремы, предложен следующий метод нахождения 8рес(Д) для конечных графов.

Решаем задачу (б>(7) для всех Енутреншк компонент К{ графа О. Затем просматриваем все значения X : £/?!?«■( Д)(. Если \e-i-SpeciA),, то

оно является собственным значением, т. е. 5рес(Д), а если \ fi-Speci Д),, тогда проверяем существование ненулевого решения уравнения (6) для данного X. Если такое решение существует, то ХеБрес(Д), если нет, то данное X отбрасываем.

В третьей главе рассматривается функция Грина оператора Лапласа.

Первый параграф является вспомогательным. В нем приводятся некоторые сведения из общей теории графов.

Второй параграф посаящен обобщенно гармокичелким функциям.

Здесь рассматривается обобщение оператора Лапласа на ориентированных графах. Пусгь дан граф С=<Х,Г), рассмотрим оператор

-/(*)- £р<*,у)/0)-/(*), (12)

уе.Г(х)

где функция /: Х-+С ( С- множество комплексных чисел), а весовая функция р(х ,у) определенная на множестве и дуг графа р: и~*С\{0}.

Определение И. Оператор Ь называется обобщенным оператором Лапласа или обобщенным лапласианом.

Опредслегше 12. Функция /: Х-»С называется обобщенно гарисшь ческой внутри графа С=(Х,Г)> «ли (I /)(х)=0 для любого л еи^С.

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

Пусть С-(Х,Г) прогрессивно конечный и Г-конечный граф, I- обобщенный лапласиан на кем. Сформулируем задачу Дирихле, порожденную оператором I:

Найти функцию / (х) обобщенно гармоническую внутри графа С н совпадающую на границе Ю с заданной функцией с?©, т. е.

Теорема 9. Пусть граф С=(Х,Г) прогрессивно конечен и Г-конечен н пусть на грашще графа <ХЗ задана однозначная функция Тогда задача Дирихле, порожденная оператором Ь имеет решешге и оно единственно.

В третьем параграфе третьей главы вводится потенциальный оператор и получена его связь с оператором Лапласа.

Пусть граф С=(Х,Г) прогрессивно конечен и Г- конечен. Рассмотрим оператор

Определение 14. Множество функций /(х) таких, что (Р/)(х)=0 Vx eintG, называется ядром оператора Р на графе G.

Теорема 10. Пусть G=(X,F) прогрессивно конечный и Г-коиечный граф, тогда KerL=KerP наG.

Ясно, что сами операторы Ар и А р не совпадают. Пусть G=(X,r) - прогрессивно конечный и Г-к^нечный граф, такой, 4ToVx еХо (Хо - n-ое кольцо, см. определение 5) выполняется

t

¿/(х) = 0, х eintC;

(13)

зд?сь [х ,z]- путь из вершины х в вершину z.

(14)

Г(д:)сХп-|. (15)

Установлена связь между операторами I и Р на графах данной структуры. Справедлива следующая теорема.

Теорема И. Для любого прогрессивно конечного и Г- конечного графа О, удовлетворяющего условию (15), и любой вершины .г сХп (п=1, 2,...), выполняется равенство

Гп-1

(р/)(*)-

/00, (¡б)

п-к

которое называется локальным полиномиальным представлением оператора Р.

В ^твертом параграфе определена функция Грина и получена ее связь с амплитудой Грина комплексной марковской цепи.

Пусть 0=(Х,Г) прогрессивно конечный и Г-конечный граф, а функция / (х) обобщенно гармоническая внутри в, тогда / (.т)еКег Г т. е.

( \ '

I Е Пр^п)

/(:) УхетЮ. (18)

Определение 15. Функцию

назовем функцией Грина обобщенного лапласиана Ь. Тогда, для обобщенно гармонической функции справедливо равенство

/«= хет1°- (20)

-Из НО) видно, что значение обобщенно-гармонической функции внутри прогрессивно конечного и Г-конечного графа можно выразить через значения этой функции на границе графа посредством функции Грина.

Далее рассматривается приложение обобщенно гармонических функций в квантовой механике. Как известно в основе формализма фейнманов-

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

В работе показано, что амплитуда вероятности принадлежит ядру опергтора Р на графе, который является дискретной моделью пространства-времени. Но нахождение амплитуды вероятности по формуле (18) довольно трудоемко. В связи с этим предложен новый метод нахождения амплитуды вероятности. А именно, так как амплитуда вероятности принадлежит Кег Р , то онг. является обобщенно гармонической функцией. Отсюда, для ее нахождения достаточно решить задачу Дирихле, порожденную обобщенным лапласианом на соответствующем графе.

В четвертой главе рассмотрены дискретные аналоги классических уравнений математической физики.

В первом параграфе рассматривается аналог волнового уравнения на орграфах. Поскольку волновое уравнение является нестационарным, то оператор Лапласа на ориентированном графе О принимает следующий вид

здесь функция р(л,д>д)>0 задана на каждой дуге в произвольный

-момент времени и Поэтому, по аналогии с волновым уравнением математической физики, волновое уравнение на графе С можно задать следующим образом

(21)

уег(х)

л1

или в развернутом виде

(22)

£/>(*,у,>)«СМ)-и(*, 0)»8(*,0.' (23)

уеС{х)

здесь функция g(л,t) определена для всех х етгв, а коэффициент к(х) зависит от структуры графа и свойств моделируемого объекта.

Пусть а(х),(3(д:) и ф(х,гД) - заданные непрерывные функции {х еинХЗ, гесС), которые удовлетворяют условиям

сей, а+|Ы). (24)

Граничное условие на ориентированном графе в можно задать следующим образом

а(х)и(г,1)+Р(х)(и(гЛ)-ц(хД))=ф(х,7,Ц (25)

для каждой дуги (х : хеипО и геЮ.

Поставлен вопрос о существовании и единственности решения уравнения (22) с граничным условием (25) и начальными условиями

ди{х,1)

и(х,0

/ = 0 = /(Х)'

/=0 = ^х), (26)

отве • на который дает следующая теорема.

Теорема 12. Пусть граф С=(Х,Г) не содержит бесконечных компонент сильной связности, причем его конденсация является прогрессивно конечным графом, и пусть функции <р(х,2,1), я(х,1) и р(хнепрерывны на [0,Т] для любых вершин гедй, хеииО и любой дут (х,у)еО соответственно, тогда волновое уравнение (22) с граничным условием (25) и начальными условиями (26) имеет решение, и оно единственно.

Замечание А. Решение волнового уравнения на ориентированном графе сводится к последовательному решению ш линейны^ систем обыкновенных дифференциальных уравнений второго порядка, где т- число внутренних вершин конденсации графа.

Второй параграф четвертой главы посвящен уравнению теплопроводности на орграфах.

Уравнение теплопроводности в математической физике имеет вид ди 2

— = о Да + 5.

(Л

Уравнением теплопроводности на ориентированном графе С=(Х,Г) можно назвать следующее равенство

Т/К*Л0«СУ.0-«(*,0)+в(*.0. (27)

Л \уеПг) )

Здесь определена для х еМ.

Рассмотрен вопрос о существовании и единственности решения уравнения (27) с граничным условием (25) и начальным условием

и(х,1)

/ = 0 = /«- (28)

Теорема 13. Пусть граф С=(Х,Г) не содержит бесконечных компонент сильной связности, причем его конденсация является прогрессивно конечным графом, и пусть функции ср(лг,гд); g(x,t) и р(л,}М) непрерывны на [0,Т] для любых вфшин гвдО, ленЦС и любой дуга (х,^)еО соответственно, тогда уравнение теплопроводности (27) с граничным условием (25) и начальным условием (28) имеегг решение и оно единственно.

Замечание 5. Решение уравнения теплопроводности на графе С=(Х,Г) сводится к последовательному решению га линейных систем обыкновенных дифференциальных уравнений первого порядка* где то - число внутренних вершин конденсации графа С.

Также рассмотрено однородное уравнение теплопроводности на графе С^рс,Г).

<1и(х,1) _ г

—=Л(х)[ У£р(х,у,1)и(у,1) - и(х,1)

(29)

снячальньм условием (28) и граничным условием

к(*,0

х есС

<Р(*> О-

(30)

Считаем, что функция <р(хД) непрерывна для любых хеЮ, а функция Р(х,у,т) непрерывна для любой дуги (х,у)еС, при этом предполагаем, что выполняется следующее равенство

Принцип максимума для решения уравнения (29) с граничным и начальным условиями (30) и (28) сформулирован в виде следующей теоремы.

Теорема 14. Пусть неотрицательная функция и(х,0 удовлетворяет уравнению (29) и достигает своего максимума в точке (хоЛ), где хоеииО; Ь)>0, тогда ц(х ,1о)зи(хо,1о) Vх е Г (хо).

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

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

В приложении 2 приведена схема нахождения границы конечного орграфа.

В приложении % приводится общая схема решения задачи Дирихле на конечном графе, а также приведена и обоснована улучшенная схема решения задачи Дирихле, порожденной классическим лапласианом Л.

Общая схема постановки и решения задачи Дирихле на конечных графах:

Пусть дан граф 0=(Х,Г), тогда задача Дирихле на нем решается по

(31)

следующей схеме:

1). Найти границу графа SG. Если граница графа G тривиальна (т. е. если <3G=X), то задача Дирихле не имеет смысла. Иначе

2). Задаем краевые условия на границе cG.

3). В массив MZfl], i=l, 2,..., ш, где m - чисто вершин конденсации G*, заносим номера граничных вершин конденсации. (Массив MZ[i] содержит информацию о том, для каких соответствующих компонент сильной связности графа G решение задачи Дирихле уже найдено).

4). Ищем вершину конденсации с номером ver, такую, что номера концов всех дуг, исходящих из ver, содержатся в массиве MZ.

5). Решаем локальную краевую задачу для компоненты сильной связности графа G, соответствующей вершине конденсации ver.

6). Номер ver заносим в массив MZ.

7). Если массив MZ не заполнен, т. е. если существует вершина конденсации у такая, что значения искомой функции на элементах компоненты сильной связности графа С-, соответствующей этой вершине, неизвестны, то перейти к 4). Иначе - конец.

Приложение 4 содержит листинга программ, реализующих алгоритмы нахождения границы графа и решения задач Дирихле, порожденных лапласианом с вещественными и комплексными весами. Написание и отладка программ осуществлялась в среде Turbo Pascal 7.0.

ЗАКЛЮЧЕНИЕ

Основные результаты диссертации, выносимые на защиту:

1. Сформулирован и доказан принцип максимума для субгармонических функций на орграфах.

2. Сформулирована и доказана теорема существования и единственности решения задачи Дирихле, порожденной оператором Лапласа, на орграфах с прогрессивно конечной конденсацией.

3. Предложен метод декомпозиции решения задачи нахождения спектра оператора Лапласа.

4. Введена в рассмотрение функция Грина и получена ее связь с амплитудой Грина комплексной марковской цепи. На основе этой связи предложен новый метод нахождения амплитуды вероятности для дискретного аналога фейнмановской теории квантовой механики.

5. / оказаны теоремы существования и единственности решений волнового уравнения и уравнения теплопроводности на орграфах, а так же сформулирован и доказан принцип максимума для решения однородного уравнения теплопроводности на орграфе.

6. Приведена схема решения краевой задачи Дирилле на конечных орграфах и ее реализация в виде паскаль-программы.

Основные положения и результаты диссертации представлены в следующих публикациях:

1. Ерусалимский Я. М., Стеновой Д. В. Волновое уравнение и уравнение теплопроводности на конечных ориентированных графах/ Азово-Черномор. гос. агроинж. акад. -Зерноград, 1996. - 11с. -Деп. в ВИНИТИ 07.02.97, N 374-В97.

2. Ерусалимский Я. М., Степовой Д. В. Гармонические функции на ориентированных графах и краевые задачи математической физики// Тез. докл. Междунар. конф. „Нелокальные краевые задачи и родственные проблемы математической биологин, информатики и физики". -Нальчик, 1996. с. 36.

3. Ерусалимский Я. М., Степовой Д. В. Дискретный оператор Лапласа на

1

орграфах и некоторые его приложения И Тез. докл. V междунар. конф. „Математика. Экономика", 26 мая -1 июня 1997 г. Ростов н/Д, 1997.

4. Степовой Д.В. Оператор Лапласа на конечных ориентированных графах/ Азово-Черномор. гос. агроннж. акад. -Зерноград, 1996. - 12 с. -Деп. в ВИНИТИ 27.09.96, N 2899.

5. Степовой Д. В., Ерусалимский Я. М. Некоторые оценки спектра оператора Лапласа на ориентированных графах/ Азово-Черномор. гос. агроинж. акад. -Зерноград, 1997. - 10 с. - Деп. в ВИНИТИ 24.12.97, N 3740 - В97.

6. Степовой Д. В., Ерусалимский Я. М. Потенциальный оператор, функция Грина на ориентированных графах и некоторые их приложения в квантовой механике/ Азово-Черномор. гос. агроинж. акад. -Зерноград, 1997. - 13 с. - Деп. в ВИНИТИ 11.04.97, N 1172- В97,

Подписано к печати 1.10.98 г. Формат 60 х 84 1/16 Объем I п.л. Тиране 100 экз. Заказ Дечагно-ынгояителькая грунта ВНИПТй^ЭСХ