close

Вход

Забыли?

вход по аккаунту

?

Спектр графа при реберном расширении.

код для вставкиСкачать
Секция математики
Секция математики
УДК 517.19
В.Б. Мнухин, М.В. Черноусов
qoejŠp cp`t` oph peaepmnl p`qxhpemhh
Получены выражения для характеристического многочлена графа
при операции реберного расширения. Как следствия, найдены новые семейства коспектральных графов и графов с целочисленным спектром.
Далее все графы предполагаются конечными, без петель и кратных
ребер. Используемые обозначения стандартны, в частности, полный nвершинный граф обозначается через Kn .
Пусть G и H — два графа. Рассмотрим операцию !=“ш,!…, !K!
графа G графом H (или, операцию !K!…%г% !=“ш,!…, ), состоящую в
том, что каждому ребру графа G ставится в соответствие копия графа H,
после чего обе вершины в G, инцидентные выбранному ребру, соединяются со всеми вершинами соответствующей копии H. Обозначим полученный граф через G◊H . Пусть A, b и D — соответственно матрицы смежности, инцидентности и степеней вершин графа G. Как обычно,
PG ( λ ) = det ( A − λI ) обозначает . =!=*2!,“2,ч“*,L м…%г%чл… графа G
[1].
Характеристический многочлен графа G◊K1 был получен Д. Цветко-
вичем [2] в 1975 году. В 1980 году первым из авторов данной работы был
найден [3,4] характеристический многочлен графа G◊Kn . Здесь эти результаты усиливаются для случая реберного расширения графа G произвольным графом H. Ее основным результатом является следующая теорема.
Теорема. Пусть G – произвольный (n,m)-граф, а H – произвольный
s-регулярный граф на k вершинах. Тогда справедливо тождество
(
PG◊H ( λ ) = ( λ − s) PHm ( λ ) det λ ( s − λ ) I + ( λ − s + k ) A + kD) .
−n
Напомним, что два неизоморфных графа с одинаковыми спектрами
называются *%“C*2!=ль…/м,. Поиск семейств коспектральных графов
является одной из классических проблем спектральной теории графов
[1,5]. Следствием теоремы является характеризация одного из таких семейств.
Следствие 1. Пусть G – произвольный граф. Если графы F и H коспектральны, то коспектральными будут и реберные расширения G◊H и
G◊H .
203
Известия ТРТУ
Специальный выпуск
Следствие 2. Если граф G регулярен степени r, то
PG◊H ( λ ) = 1 +


 λ2 − λs − kr 
k  m
.
 PH ( λ ) PG 
λ − s
 λ −s+ k 
n
В частности, если r=k-s, то
λ
n
− r m
 PH ( λ ) PG ( λ − k ) .
 λ − s
PG◊H ( λ ) = 
В 1970 году Ф. Харари была поставлена задача описания графов,
имеющих целочисленный спектр (условимся далее называть такие графы
цл/м,).
Следствие 3. Пусть G – целый r-регулярный граф, а H – целый sрегулярный граф на r+s вершинах. Тогда граф G◊H является целым.
Следствие 3 позволяет конструировать новые целые графы из уже
известных. В частности, если G — кубический целый граф, то для построения нового целого графа его достаточно реберно расширить, например, одним из двух 6-вершинных целых кубических графов.
Предположим теперь, что из графа G◊H удалены все ребра, принадлежащие G. Обозначим полученный граф через G ° H . Заметим, что
если H имеет одну вершину, то G ° H совпадает с реберным подразбиением, спектр которого исследовался в работах [1]-[3], [5], [6]. Усилением
полученных в них результатов является следствие 4.
Следствие 4. Если Н – к-вершинный s-регулярный граф, то
(
)
PG◊H ( λ ) = ( λ − s) PHm ( λ ) det λ ( s − λ ) I + kA + kD .
−n
В частности, если G регулярен степени r, то
 λ2 − λs − kr 
k  m
.
 PH ( λ ) PG 
 λ − s
k


PG◊H ( λ ) = 

n
khŠep`Šrp`
1.
0"2*%", ч d.l., d3K l., g=.“ u. qC*2!/ г!=-%" - 2%!, , C!,л%›…, .
j,": m=3*%"= d3м*=,1982.
204
Секция математики
2. Cvetkovic D.M. Spectra of graphs, formrd by some unary operations. //Publs.
Inst. Math.,1975,1 1,p. 37-41.
3. l…3., … b.a. qC*2!/ г!=-%" C!, …*%2%!/. 3…=!…/. %C!=ц, . .
//m*%2%!/ 2%C%л%г,ч“*, , *%мK,…=2%!…/ “"%L“2"= г!=-%". j,": h …-2.
м=2. `m r qqp,1980. q. 38-44.
4. l…3., … b.a. n "%““2=…%"л…,, м…%г%чл…%" г!=-=. //27 Internat. Wiss. K oll.
TH Ilmenau. Ilmenau,1982,p. 87-90.
5. Cvetkovic D.M., Doob M., Gutman I., Torgasev A. Recent Results in the Theory of
Graph Spectra. N.-Y.,1988.
6. Shinodo Shoji. On the characteristic polynomial of the adjacency matrix of the
subdivision graph of a graph. // Discrete Appl. Math.,1980,vol. 2,p. 349-351.
УДК 517.4
А.А. Афонин
МОДЕЛИРОВАНИЕ ЗАДАЧИ ЛИНЕЙНОЙ СТАЦИОНАРНОЙ
ФИЛЬТРАЦИИ СО СВОБОДНОЙ ГРАНИЦЕЙ. ПРОБЛЕМА
СУЩЕСТВОВАНИЯ И ЕДИНСТВЕННОСТИ
Задача линейной стационарной фильтрации впервые строго поставлена и решена в работах [1,2] в случае прямоугольной области (дамбы) с
использованием теории вариационных неравенств, причем доказано существование решения; вопрос единственности оставлен открытым. Позже, в работе [3], доказано существование решения задачи для общей области, причем решение получено как минимум семейства суперрешений.
В настоящей работе представлены математическая модель и конструктивное доказательство существования и единственности решения задачи для
области общего вида.
S3≡Г
Пусть дамба представляет
S3≡Г
собой ограниченную область
Ω ⊂ R 3 ( 2 ) , граница которой
представляет собой совокупS1≡Г
ность
трех
частей
∂ Ω = S1 U S 2 U S 3 . Здесь S1 —
дно дамбы, являющееся непроницаемым для жидкости; S 2 — часть ∂ Ω ,
находящаяся в контакте с атмосферой; S 3 — часть ∂ Ω , которая находится в контакте с водным резервуаром.
Ставится задача: найти область A ⊂ Ω , которая является важной
частью Ω и функцию u , определенную в A (u = u(x) — давление), такую,
что
1) граница ∂ A состоит из 4 частей:
∂ A = Γ1 U Γ2 U Γ3 U Γ4 , где
Γ1 ⊂ S1 , Γ1 — непроницаемая для жидкости часть ∂ A ;
c
3
3
1
205
Документ
Категория
Без категории
Просмотров
4
Размер файла
298 Кб
Теги
реберном, спектр, расширению, граф
1/--страниц
Пожаловаться на содержимое документа