Специальные матрицы графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Беляевский, Владимир Васильевич АВТОР
кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ
Минск МЕСТО ЗАЩИТЫ
1992 ГОД ЗАЩИТЫ
   
01.01.09 КОД ВАК РФ
Автореферат по математике на тему «Специальные матрицы графов»
 
Автореферат диссертации на тему "Специальные матрицы графов"

АКАДЕМИЯ НАУК БЕЛАРУСИ ИНСТИТУТ МАТЕМАТИКИ

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

БЕЛЯЕВСКИй Владимир Васильевич

СПЕЦИАЛЬНЫЕ МАТРИЦЫ ГРАФОВ Специальность 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Минск 1992

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

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

профессор Лепешинский Николай Андреевич.

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

профессор Тышкевич Регина Иосифовна; - кандидат физико-математических наук Тюрин Владимир Львович.

Ведущая организация - Институт математики СО Российской . АН.

Защита состоится " ю " шурела._1992,г.

в часов на заседании специализированного совета К 006.19.01 по присуждению ученой степени кандидата физико-математических наук в Институте математики АН Беларуси по адресу :

220072, г. Минск, ул. Сурганова, 11

С. диссертацией можно ознакомиться в библиотеке Института математики АН Беларуси.

Автореферат разослан " ю " дкхрпцх_1992 г.

Ученый секретарь специализированного совета

кандидат физ.-мат. наук -ЯЯс— А. И. Астровский

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

'"" ^£1У5:№Ность_проблемы^ Известно немало практических задач и ■еоретических проблем в математике, физике, химии, которые сводят-:я к изучению спектра матрицы специального вида. В теории графов »та проблематика активно изучается после появления работ Л. М. Лих--енбаума (1956), Л.Коллаца и У. Синоговица (1957). Одним из стиму-!ов ее развития является, в частности, постоянное совершенствова-ше и математизация теории молекулярных орбиталей в химии.

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

юзволили сформулировать основные вопросы этого раздела математи-

* )

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

Значительный вклад в развитие спектральной теории графов внесли Л.Бабаи, Н.Бигс, Р. Боуз, Ф. Буссемакер, С. Годсил, И.Гутман, М. Дуб, Ю. Зайдель, X. Захс, Р.Камерон, Ю.Ван Линт, А. Мовиовиц, В. Хе~ мерс, Б. Татт, Д. Хигман, А. Хофман, Д. Цаеткович, А. Швенк и другие.

Большинство работ этих авторов саязано с рассмотрением характеристического многочлена графа (т.е. характеристического многочлена его матрицы смежности), который является важным инвариантом для описания и исследования структурных свойств графов. Построение Л.Коллацем и У. Синоговицем в 1957 году неизоморфных коспектральных графов привело к изучению характеристических многочленов других матриц, однозначно задающих граф. К таким матрицам относятся матрицы Зайделя, Кирхгофа и другие. Естественно возникает вопрос о взаимосвязях различных спектров графов. Для его решения перспективным является исследование •обобщенной матрицы смежности, введенной Х.Юбо (1975) под другим названием и которую использовали' для исследований другие авторы.

Важность конструирования коспектральных графов раскрыта

ф I

Cvetkovic D. Some possible directions In further investigations of graph spectra // Algebraic Methods in Graph Theory. - Vol I. Colloq. Math. Soc. - Amsterdam, 1981. - P. 47-67.

ft )

Д. Цветковичем, М. Дубом, X. Захсом . В контексте этого обоснована еше более значительный интерес представляют вопросы построения не изоморфных графов с одинаковыми обобщенными характеристические; многочленами (такие графы будем называть бикоспектральными >. В литературе этот вопрос специально не рассматривался, хотя некоторьк известные .классы графов, как оказалось, таковыми являются. Сильн< регулярные графы (Р. Боуз, 1963), полярные графы (Р. И. Тышкевич, 1980), а также операции прямой суммы и полного произведения гра фов, введенные А.А.Зыковым, являются перспективными объектами для построения семейств бикоспектральных графов.

Известная гипотеза Улама (точнее, гипотеза Келли-Улама) сост< ит в том, что граф с числом вершин п>3 может быть восстановлен по набору, состоящему из п его (п-1 )-вершинных порожденных подграфов полученных из исходного удалением каждой его вершийы. Эта гипотеза, как'известно, подтверждена только для отдельных классов графо] и тесно связана с одной из центральных проблем теории графов -изоморфизме. Сложность вопроса, поставленного в гипотезе Келли Улама привела к рассмотрению ее спектрального варианта (И.Гутман, Д.Цветкович, 1975, А.Швенк, 1979) - по набору характеристических многочленов (п-1 )-вершнных порожденных подграфов восстановить характеристический многочлен графа, который в настоящее время также не подтверзден в общем случае.- Б связи с этим, определенный интерес представляет спектральный вариант гипотезы, сформулированный в терминах обобщенных характеристических многочленов.

Цв£Ё5?_Е§521Ь1 является выявление взаимосвязей между обобщенны ми характеристическими многочленами и модифицированными (в том чи еле, известными) характеристическими многочленами графа; конструи рование бикоспектрапьных графов; реконструкция обобщенного характеристического многочлена n-вершинного граф- по набору обобщенных характеристических многочленов его (п-1>-вершиннык порожденных подграфов.

Лаучная_новизча работы заключается в. следующем: - исследован новый класс бикоспектральных графов, построены их бесконечные¡серии;

--i---

*г1вегкович Д.,'Дуб М. , Захс X. Спектры графов. Теория и применени //Киев: Наукоэа думка, 1984. Пер. с англ.: D. Cvetkovic, M.Daob H.Sachs. Spectra of Graph. Theory and Application. Berlin, 1980.

- положительно рекен один из спектральных аналогов гипотезы .{елли-Улама, сформулированный а терминах обоблданных характеристических многочленов n-вершинного графа и < h-1 )-вершинных г^ррожден-* шх подграфов.

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

П^бликацин^ По теме диссертации опубликовано 4 работы.

Ап£обация_£§боты^ Результаты диссертации докладывались на IV Всесоюзном совещании "Методы и программы решения оптимизационных задач на графах и сетях" (Новосибирск, 1989), научной конференции "Актуальные проблемы социально-гуманитарных и естественных наук", посвященной 70-летию университета (Минск, 1991), городском семинаре по теории графов под рук. Р.И.Тыяхевич (Минск, 1986-1990 ), семинаре лаборатории математической кибернетики ИМ АН Беларуси (Минск, 1991), семинаре "Кетоды и программы решения оптимизационных задач на графах и сетях" (Новосибирск, 1991).

Об;ьем_|>аботы^ Диссертация изложена на 111 страницах и состоит из введения, трех глав, списка цитируемой литературы, содержащего 94 наименования.

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

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

ГЛАБА_Г посвящена исследованию обобщенного характеристического многочлена графа и носит вспомогательный характер. В первом параграфе даны необходимые.определения и понятия, отличные от общепринятых. Среди них '

Определение 1.1. Пусть вершины графа G занумерованы числами 1,2,...,п. Тогда матрица A(x,y,z> размера пхп с элементами если

если 1 и j смежны, если i и J несмежны.

ai.

ai, Г2'

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

Определение 1.2. Обобщенным характеристическим многочленом графа в называется определитель его обобщенной матрицы смежности ЬеЬАд( х,у,г ).

При некоторых фиксированных значениях переменных в определениях 1.1 и 1.2 рассматриваемые объекты ("модифицированные" матрицы смежности и "модифицированные" характеристические многочлены! изучались ранее. В частности, А(0,1,0) - обычная матрица смежности, СеЪА<х,-1,0)=Р(х) -обычный характеристический многочлен графа.

Установлено, что обобщенный характеристический многочлен, кап инвариант графа не слабее любого модифицированного характеристического многочлена. Приводится таблица коэффициентов характеристических многочленов коспектральных деревьев с чийлом вершин дс десяти й коэффициентов характеристических многочленов дополнены* этих деревьев,' на основании которой делается вывод, что обобщенны? характеристический многочлен является полным инвариантом для деревьев с числом вершин по крайней мере до десяти (утверждение 1.1).

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

Теорема 2.2. Для любого п-вершинного графа б с обобщенной матрицей смежности А(х+а^,у,2 ), у*з имеет место

( у-2 г уг0-гу~ (х+й.Ъ )( ул -я. )+уи1 -гу. -------г—---¿-.ЮеЪАС-----А----¿--1---------1>У1,*1> ~

где У1,г1,у2

уг.-гу. (х+<31Ь)(у2-г2 )+у22-2у2

-------^еЬАС------------------------У2'г2)

<У2"*г2 у-2 .1

- константы, такие, что У^ъ^г у1г2"!у2г:1

Здесь A(x+d1t>y,a)=A(x,/>z kd1>t, где )- пхп-матрица,

о которой k~ символ Кронекера, dj- степень вершины i, t- неза-йисимая переменная. ■ '

В частном случае, при y1=z2=-l, у^г^О, имеет место результат, доказанный А.Kau*'. Теорема 2.2 имеет ряд важных применений. Первое из них отмечено в следствии 2.1. Второе заключается в возможности представления произвольного модифицированного характерна стического многочлена двумя заданными модифицированными характеристическими многочленами. Эту возможность иллюстрируют, например, следствия 2.2-2.5 для наиболее распостраненных характеристических многочленов графов. Теорема 2.2 также широко используется в аналитических преобразованиях а глазах II, III.

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

Теорема 3.1. Для п-вершинного регулярного степени к графа а с обобщенной матрицей смежности A(x,y,z), y*z имеет место

DetA( X,y,2 >=----Ff---Trri?TrT---r^rr7--TDetAC---ff^T"---.У0'а0

где f <y.z )=<y-s >/(yjj-ZQ а Уд»^- константы, такие, что у^*zq.

Доказанный А.Кац результат относится к случаю yQ=-l,zg=0.

Возможные применения теоремы 3.1 проиллюстрированы следствиями 3.1-3.2, устанавливавшими соотношения между различными спектрами регулярного графа. Результат следствия 3.1 известен и первоначально доказан X. Захсом**5 более сложным путем (см. также-теорему 2.6 монографии ).

На основании простейших свойств 3.1-3.3 сильно регулярных —_ . . Кац А.О. Об одном классе полиномиальных инвариантов графа //

•Латв. мат. ежегодник. -19S0. - Н 3. - С. 137-146. >м<)

Sachs Н. Beziehcinren zwischen den in einem Graphen enthalten kreisen und seinem charakteristischen Polynom // Publ. Math. -December 1964. - H. 11. - S. 119-134.

"^^Цветкович Д. , Дуб M. , Захс X. Спектры графов. Теория и применение. - Киев: Наукова думка, 1984. - С. 58.

графов установлены рекуррентные формулы для элементов 1-ой степен» обобщенной матрицы смежности через элементы 1-1 степени это{ матрицы (лемма 3.1). Доказана

Теорема 3.3. Для сильно регулярного графа с с параметрам!

Р £

СеЪА( %,у, г )=( х-г+кС у-г )+пг )(х-г+г(у-г )) ( х-г+э! у-г ) где т и е - кратности второго и третьего собственных значений г и, э (к<г<с) характеристического многочлена графа б.

Варьируя значениями переменных х,у,и в модифицированной матрице смежности сильно регулярного графа этой матрице можно придат; дополнительное "хорошее" свойство. Так, например, модифицировании; матрицы смежности рассматриваемого графа А( х,< -л+к-г >г/( -к-г ),г) 1 А( х, (-п+к-з/(к-е), в) при любых и, имеют ровно два различны собственных значения. Этот прием используется при' доказательств* теоремы"5.2. В следствии 3.5(3.6) отражены наборыпеременных когд; модифицированная матрица смежности сильно регулярного графа явля еТся ортогональной (идемпотентной).

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

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

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

Рассмотрены полные и дополнения к полным графам (утверждет 4.1, 4.3), граф приема гостей и его дополнение (утверждение 4.Е простой цикл ¡(утверждение 4.6), простой путь (утверждение 4Л

Важную роль играют ут ерждения 4.2 и 4.7, названные соответственно принципом двойственности и обобщением теоремы Ф.Кларка.

Утверждение 4.2 (принцип двойственности). Пусть DetA„(x,y,3),

- обобщенный характеристический многочлен графа G. Тогда

DetАр;( х, у, з )=DetA_( х,у, z ) -обобщенный характеристический многочлен ^ . ь

дополнения к графу G.

Утверждение 4.7 Пусть G - граф с веркинаии, занумерованными числами 1,2,...,п, G ^ - подграф, получзнный из графа G удалением i-ой вершины и инцидентных ей ребер. Тогда

Det\G<x,y,2)=-j:i2iDetAG (x,y,z).

В утверждении 4.9 установлены зависимости, выршгакядае обобщенный характеристический многочлен прямой суммы "и полного произведения графа G с m-вершинным полным графом К и его дополнением icm через обобщенный характеристический многочлен графа G, а в утверэденииг4.10 - прямой суммы и полного произведения произвольных двух графов через характеристические многочлены этих графов и их дополнений.

Далее вводятся новые унарные операции над графами - двудоли-зация D(G) и поляризация р(G) графа G я их разновидности.

Для определенности, пусть вершины G занумерованы числами 1,2,...,п. Тогда графы D(G) и P(G> имеют 2п вершин, занумерованный

числами 1,2,. . . ,2п. Две вершины i и j С 1=1,2,. . . ,п, j=n+l,n+2,------

2п) графа D(G> смежны тогда и только тогд&, когда вершины i и j-n графа G смежны. Граф P(G) кроме ребер графа D(G) содержит дополнительно ребра, соединяющие все веряины I и j при i,j<n, inj.

Легко заметить, что D(G) -двудольный, a P(G) -полярный графы.

Утверждение 4.11 выражает обобщенный характеристический многочлен двудолизации графа G в виде произведения обобщенного и модифицированного характеристических многочленов графа G, а .утверждение 4.12 - обобщенный характеристический многочлен поляризации сильно регулярного графа через обобщенный характеристический многочлен графа-операнда.

Наконец, утверждение 4.13 позволяет свести вычислен» обобщенного характеристического многочлена полярного соединения (Ge>Km) к вычислению определителя преобразованной обобщенной матрицы смежности х, у, 2 ),

Результаты, параграфов 1-4 используется в главе_11 при постро-

?

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

Теорема 5.2. Для любого п>7 существуют пары бикоспектральных тгвершинньгх графов.

Пусть G - сильно регулярный граф с множеством вершин v(G). Оказывается, что обобщенный характеристический многочлен подграфа G^ графа G, порожденного множеством вершин V(G^)nV(G> однозначно определяется обобщенным характеристическим многочленом подграфа в^ графа G, порожденного множеством вершин V<Go)=V(G)\V<G^). Взаимосвязь обобщенных характеристических многочленов графов G^ и G2 дается в виде теоремы 5.3,

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

Из теоремы Б.З получен ряд следствий 5.2-5.7, которые можно применить при построении пар бикоспектральных графов. Например, при удалении каждой вершины (каждой пары смежных вершин, каждой пары несмежных вершин) получаем классы графов, состоящие из п (кп/2, n( n-k-1)/2 ) бикоспектральных (возможно, изоморфных) графов. Приведен пример, иллюстрирующий применение теоремы 5.3 для построения восьмивершинных бикоспектральных графов из неизоморфных сильно регулярных гр&фов с параметрами 16,6,2,2.

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

Теорема 5.4. Пусть G и И - бикоспектральные графы, F -произвольный граф. Следующие графы попарно бикоспектрапьны :

G*F И Н^Г, G*F И HVF, GW И EVF, GW И HVF,

G©K И Н&К , • GffiK И Н©К , G®K И Н®К , (ЗФК И 0®К , П П П _П П П _п

D( в ) И D( Н ), D(G) И D(H), P(G) И Р(Н), Р( G) И Р(Н). — •

Haemers W. Н. Eigenvalue methods In algebraic graph theory // Thesis; Eindhoven, 1979 (Mat." Centr. Amsterdam, 1980). - P. 217.

Здесь - операци" прямой суммы графов; V - полного произведения; © - полярного соединения графов; о(р) - двудолизация графа Р(Р) - поляризация сильно регулярного графа г.

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

Глава_1Г1 посвящена изучению одного из спектральных аналогов известйой гипотезы Кйлли-Улама и состоит из двух параграфов.

В шестом параграфе рассмотрены свойства обобщенного характеристического многочлена ОеЪА(х,у,г> п-вершинного графа а и обобщенных характеристических многочленов БеЬА^Сх.у^) его (п-1 )-вер-шинных порожденных подграфов 1=1,2,...,п. Здесь ограничимся

рассмотрением случаев, когда граф (3 и его подграфы не являются полными или дополнениями к полным графам. Доказаны две леммы, накладывающие ограничения на коэффициенты 'модифицированных характеристических многоч.-енов графа в.

Лемма 6.1. Пусть А(х,у,г) - обобщенная патрица смежности графа й, СеЬА(0,у,2 СеЬЛ( х,1,0 jX•,;

СеЬАСх.ОД >=хп+Е^С)2ь^-Для коэффициентов рассматриваемых многочленов выполняются следующие равенства:

с

j=l,2,. . . ,п-1;

С0=Ь0;

здесь при ю<0 или ш>1.

Лемма 6.2. Пусть А<х,у,г ^ кхп_^укг,'_к - обобщен-

ный характеристический многочлен графа б. Тогда значения . . "п-^Е^о"^-^ к ' .И1.2»-• ■ не зависят от. структуры графа, постоянна при фиксированных значениях ,5 и п и выражаются формулами

зп__,=<-1 >-Н1(п'Т1>, .¡=0,1,... , п-1,

Э0 = (-1 )п_1<п-1

следующая теорема устанавливает соотношения между коэффициентами обобщенного характеристического многочлена п-вершинного графа <3 и обобщенных характеристических многочленов его <п-1)-вершинных

подграфов 1=1,2,...,п.

Теорема 6.1. Для обобщенного характеристического- многочлена ОеЬА( х,у, г ) п-вершинного графа в (б^К Дп_), п>3 и обобшенных харшстеристических многочленов ЮеЪА^х.у-.н) его (п-1 )-вершшных подграфов (1=1,2,...,п имеет место

ОеЬА(и,1,0 >+( -1 )П_1 йе^АС 1 —и,0,1 ) = Э""1*1'61^'1-".0.1 )Ое1А(и,1 ,0)+ОеЪА1(и,1,0)ОеЬА(1-и,0,1 ))

При доказательстве теоремы 6.1 использовались утверждение 4.9 теорема 2.2, лемма Боровских , техника преобразований определителей и обобщенных характеристических многочленов. Эта теорема играет важную роль для задачи, рассмотренной в следующем параграфе. Кроме того, соотношения в леммах 6.1 и 6.2 могут рассматриваться как необходимые условия для многочленов, которые являются соответствующими характеристическими многочленами графов.

Задача реконструкции обобщенного характеристического многочлена DetA(x,y,s) п-вершинного графа а по набору обобщенных характеристических многочленов йеЬАЛх,у,ъ') его п-вершинных порожденных подграфов <3^ 1=1,2,...,п рассмотрена в седьмом параграфе.

Исследованы четыре различных случая реконструкции обобщенного характеристического многочлена графа, в некоторых из них по дополнительной информации о структуре порожденного подграфа восстанавливается не только обобщенный характеристический многочлен ОеЬА^< х,у,%) графа а, но и сам граф а. Наиболее трудный для исследования случай 4 возникает, когда среди порожденных подграфов нет полных графов или дополнений к ним, степень (Зее1 удаляемой вершины 1 при получении из а не равна нулю или п-1, существуют хотя бы два графа Gi и для которых дее1*с!ее1. При доказательстве основного результата здесь используются теорема 6.1, обобщение теоремы Ф.Кларка (утверждение 4.7), свойства квадрата многочлена, зависимости между коэффициентами модифицированных характеристических многрчленов графа (лемма 6.1), выражение обобщенного

ф )

Колмыков В. А. Спектры графов IX (дифференцирование по ребру и по вершине). - Воронеж. - 1988. - 9 с. Рукопись предст. Воронеж, ун-том. Деп. в ВИНИТИ 3.06.88, Н5203-В88 Деп.

характеристического м огочлена графа fGVK^ ) через обобщенный

характеристический многочлен графа G (утверждение 4.9), техника преобразований обобщенных характеристических многочленов.

Основной результат главы III формулируется в виде теоремы 7.1 которая дает положительный ответ на вопрос Д. Цветковича о спектральном варианте гипотезы Келли-Улама, сформулированный в терминах обобщенных характеристических многочленов графов.

Теорема 7.1. Обобщенный характеристический многочлен п—нер— шинного графа G реконструируется по заданным обобщенным характеристическим многочленам его ( п-1)-вершинных порожденных подграфов G^ 1=1,2,. . . ,п.

При доказательстве теоремы 7.1 наиболее, акт„вно использовались два специально выбранных характеристических многочлена среди всех обощенных характеристических многочленов (п-1)-вершинных порожденных подграфов G^ графа G. Другие такие многочлены использованы лишь однажды при вычислении суммы всех многочленов. Таким образом, обобщенный характеристический многочлен нерегулярного графа реконструируется по сумме всех обобщенных характеристических многочленов его <п-1)-вериинных порозденных подграфов и двум специально выбранным из этих обобщенных характеристических многочленов (следствие 7.1), а в отдельных случаях для реконструкции достаточно информации о сумме, всех обобщенных характеристических многочленов порожденных подграфов и одному из этии характеристических многочленов.

В заключение параграфа сделано замечание о реконструкции n-вершинного графа G по набору его (п-1)-вершинных порожденных подграфов Gi»G2'"*"*Gn—"1 и известному значению обобщенного характеристического многочлена DetAß(к,у ) графа G. Контрпримером здесь является, в частности, одна из пар семиЬершинных бикоспектральиых графов. Способы получения бикоспектральных графов, описанные а пятом параграфе, позволяют легко получить контрпримеры для произвольного числа вершин п, п>7. '

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

работах:

1. Беляеоский В. В. , Бризгалова И.И. О характеристическом многочлене обобщенной матри. л смежности графа / Ред. журн. "Вестник Белорус, ун-та. Сер. 1, физ. , мат., мех." - Минск, 1984. -16 е.. ил. - Библиогр. 10 назв. - Леп. в БелНИШТИ 18.06.84, Н894Бе-84.

2. Беляевский В.В. О некоторых свойствах обобщенного характеристического многочлена графа // Яробл. вопросы автоматизации производства и обработки информации. - Минск: Университетское, 1987. - С. 243-246.

3. Беляевский В. В., Лепешинский H.A.. Викоепектральные графы // Методы и программы решения оптимизационных задач на графах и сетях. Ч. II. - Новосибирск, 1387. - С. 12-14.

4. Беляевский В.В. Об одном спектральном варианте гипотезы Келли-Улама // Актуальные проблемы социально-гуманитарных и естественных наук / Тез. докл. лаучн. конференции, поев. 70-летию университета. Минск, апрель 19Slr. - Минск, Вышэйшая школа, 1991. - С. 96-97.